118

我试图实施Miller-Rabin primality test，并且对为什么中型数字（约 7 位数）需要这么长时间（> 20 秒）感到困惑。我最终发现以下代码行是问题的根源：

x = a**d % n

（其中a、d和n都是相似但不相等的中等大小的数字，**是幂运算符，并且%是模运算符）

然后我尝试用以下内容替换它：

x = pow(a, d, n)

相比之下，它几乎是瞬时的。

对于上下文，这是原始函数：

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更快？

4

4 回答 4

171

请参阅有关模幂运算的 Wikipedia 文章。基本上，当你这样做时a**d % n，你实际上必须计算a**d，这可能非常大。但是有一些计算方法a**d % n不需要自己计算a**d，这就是pow它的作用。操作员不能这样做，**因为它无法“预见未来”知道您将立即取模。

于 2013-01-03T06:03:13.917 回答
37

BrenBarn 回答了您的主要问题。在你身边：

为什么使用 Python 2 或 3 运行时它的速度几乎是 PyPy 的两倍，而通常 PyPy 的速度要快得多？

如果你阅读 PyPy 的性能页面，这正是 PyPy 不擅长的事情——事实上，他们给出的第一个例子：

不好的例子包括使用大的 long 进行计算——这是由不可优化的支持代码执行的。

从理论上讲，将一个巨大的幂运算后跟一个 mod 转换为模幂运算（至少在第一遍之后）是 JIT 可能能够进行的转换……但 PyPy 的 JIT 不行。

附带说明一下，如果您需要使用大整数进行计算，您可能需要查看第三方模块，例如gmpy，在某些情况下，在主流用途之外，它有时可能比 CPython 的本机实现快得多，而且还有很多额外的功能，否则您必须自己编写，但代价是不那么方便。

于 2013-01-03T06:17:16.927 回答
13

进行模幂运算有一些捷径：例如，您可以找到a**(2i) mod n每个ifrom 1to并将所需的中间结果log(d)相乘 (mod )。n像 3-argument 这样的专用模幂函数pow()可以利用这些技巧，因为它知道您正在做模运算。Python 解析器无法识别这个给定的裸表达式a**d % n，因此它将执行完整的计算（这将花费更长的时间）。

于 2013-01-03T06:07:30.083 回答
3

计算的方法x = a**d % n是乘以幂，然后用a取模。首先，如果很大，这会创建一个巨大的数字，然后将其截断。但是，最有可能进行了优化，以便仅跟踪最后一位数字，这是计算模数乘法所需的全部内容。dnax = pow(a, d, n)n

于 2013-01-03T06:08:17.120 回答