为什么pow(a,d,n)比a ** d%n快得多?

我试图实施一个米勒 – 拉宾素性testing ,并且对中型号码(〜7位数字)花费这么长时间(> 20秒)感到困惑。 我最终发现下面这行代码是问题的根源:

x = a**d % n 

(其中adn都是相似的,但不相等的中等数字, **是指数运算符, %是模运算符)

然后我尝试用以下replace它:

 x = pow(a, d, n) 

通过比较它几乎是瞬间的。

对于上下文,这里是原始的function:

 from random import randint def primalityTest(n, k): if n < 2: return False if n % 2 == 0: return False s = 0 d = n - 1 while d % 2 == 0: s += 1 d >>= 1 for i in range(k): rand = randint(2, n - 2) x = rand**d % n # offending line if x == 1 or x == n - 1: continue for r in range(s): toReturn = True x = pow(x, 2, n) if x == 1: return False if x == n - 1: toReturn = False break if toReturn: return False return True print(primalityTest(2700643,1)) 

一个例子计时计算:

 from timeit import timeit a = 2505626 d = 1520321 n = 2700643 def testA(): print(a**d % n) def testB(): print(pow(a, d, n)) print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)}) print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)}) 

输出(使用PyPy 1.9.0运行):

 2642565 time: 23.785543s 2642565 time: 0.000030s 

输出(使用Python 3.3.0运行,2.7.2返回非常相似的时间):

 2642565 time: 14.426975s 2642565 time: 0.000021s 

还有一个相关的问题,为什么当用Python 2或3运行时,这个计算几乎是PyPy的两倍,通常PyPy 要快得多 ?

请参阅维基百科有关模数求幂的文章。 基本上,当你做a**d % n ,你实际上必须计算a**d ,这可能相当大。 但是有一些计算a**d % n而不必计算a**d本身,这就是pow所做的事情。 **运营商不能这样做,因为它不能“看到未来”知道你要立即采取模数。

BrenBarn回答了你的主要问题。 为了您的身边:

为什么用Python 2或3运行的速度比PyPy快两倍,通常PyPy要快得多?

如果你阅读PyPy的性能页面 ,这就是PyPy不擅长的事情 – 事实上,他们给出的第一个例子是:

不好的例子包括做很长的计算 – 这是由不可优化的支持代码执行的。

从理论上讲,把一个巨大的幂指数变成一个模幂(至less在第一遍之后)是一个JIT可能能够做出的变换……但不是PyPy的JIT。

作为一个方面说明,如果你需要用大整数进行计算,你可能会想看看像gmpy这样的第三方模块,在某些情况下,它可能比CPython的本地实现快得多,很多额外的function,否则你必须写自己,代价是不太方便。

有一些做模幂运算的捷径:比如你可以从1log(d)finda**(2i) mod n ,然后把你需要的中间结果相乘(mod n )。 像3参数pow()这样的专用模幂函数可以利用这些技巧,因为它知道你在做模运算。 Pythonparsing器无法识别这个给定的裸expression式a**d % n ,所以它将执行完整的计算(这将需要更长的时间)。

计算x = a**d % n方法是将a提升到d次方,然后用n模。 首先,如果a很大,那么创build一个巨大的数字,然后截断。 然而, x = pow(a, d, n)最有可能是最优化的,所以只有最后n数字被跟踪,这些都是计算乘法模数乘所需要的。