为什么pow（a，d，n）比a ** d％n快得多？
我试图实施一个米勒 – 拉宾素性testing ，并且对中型号码（〜7位数字）花费这么长时间（> 20秒）感到困惑。 我最终发现下面这行代码是问题的根源：
x = a**d % n （其中a ， d和n都是相似的，但不相等的中等数字， **是指数运算符， %是模运算符）
然后我尝试用以下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，否则你必须写自己，代价是不太方便。
有一些做模幂运算的捷径：比如你可以从1到log(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数字被跟踪，这些都是计算乘法模数乘所需要的。
