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

I was trying to implement a Miller-Rabin primality test, and was puzzled why it was taking so long (> 20 seconds) for midsize numbers (~7 digits). I eventually found the following line of code to be the source of the problem:

我正在尝试实现Miller-Rabin primality测试，我很奇怪为什么中型数字(~7位)需要这么长的时间(> 20秒)。我最终发现下面一行代码是问题的根源:

x = a**d % n

(where a, d, and n are all similar, but unequal, midsize numbers, ** is the exponentiation operator, and % is the modulo operator)

(a, d, n都是相似的，但不相等，中等大小，**是指数运算符，%是模运算符)

I then I tried replacing it with the following:

然后我试着将它替换为以下内容:

x = pow(a, d, n)

and it by comparison it is almost instantaneous.

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

For context, here is the original 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))

An example timed calculation:

一个例子的计算:

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)})

Output (run with PyPy 1.9.0):

输出(运行PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

Output (run with Python 3.3.0, 2.7.2 returns very similar times):

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

2642565
time: 14.426975s
2642565
time: 0.000021s

And a related question, why is this calculation almost twice as fast when run with Python 2 or 3 than with PyPy, when usually PyPy is much faster?

还有一个相关的问题，为什么在使用Python 2或3运行时，计算速度几乎是PyPy的两倍，而PyPy通常要快得多?

4 个解决方案

#1

156

See the Wikipedia article on modular exponentiation. Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large. But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does. The ** operator can't do this because it can't "see into the future" to know that you are going to immediately take the modulus.

参见*关于模块化指数的文章。基本上，当你计算**d % n时，你需要计算*d，它可能很大。但是有一些方法可以计算*d % n而不需要计算*d本身，pow就是这么做的。**运算符不能这样做，因为它不能“预见未来”，知道你马上要取模量。

#2

BrenBarn answered your main question. For your aside:

BrenBarn回答了你的主要问题。为你的旁白:

why is it almost twice as fast when run with Python 2 or 3 than PyPy, when usually PyPy is much faster?

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

If you read PyPy's performance page, this is exactly the kind of thing PyPy is not good at—in fact, the very first example they give:

如果你读过PyPy的性能页面，这正是PyPy不好的地方——事实上，他们给出的第一个例子是:

Bad examples include doing computations with large longs – which is performed by unoptimizable support code.

不好的例子包括使用大的长字符进行计算——这是由无法优化的支持代码执行的。

Theoretically, turning a huge exponentiation followed by a mod into a modular exponentiation (at least after the first pass) is a transformation a JIT might be able to make… but not PyPy's JIT.

从理论上讲，将一个巨大的指数转化为一个模指数(至少在第一次传递之后)是一个JIT可以实现的转换，但不是PyPy的JIT的JIT。

As a side note, if you need to do calculations with huge integers, you may want to look at third-party modules like gmpy, which can sometimes be much faster than CPython's native implementation in some cases outside the mainstream uses, and also has a lot of additional functionality that you'd otherwise have to write yourself, at the cost of being less convenient.

边注,如果你需要做计算与巨大的整数,你可能想看看像gmpy第三方模块,这有时是在某些情况下比CPython的快得多的本地实现主流之外的用途,也有很多额外的功能,否则你必须写自己,代价是不太方便。

#3

There are shortcuts to doing modular exponentiation: for instance, you can find a**(2i) mod n for every i from 1 to log(d) and multiply together (mod n) the intermediate results you need. A dedicated modular-exponentiation function like 3-argument pow() can leverage such tricks because it knows you're doing modular arithmetic. The Python parser can't recognize this given the bare expression a**d % n, so it will perform the full calculation (which will take much longer).

做模指数运算有捷径:例如，你可以找到**(2i)对从1到log(d)的每一个i取余n，然后把中间结果相乘(mod n)。一个专用的模块指数函数(如3参数pow())可以利用这些技巧，因为它知道您正在进行模块化运算。Python解析器不能识别这个表达式，因为它的表达式是**d % n，所以它将执行完整的计算(这将花费更长的时间)。

#4

The way x = a**d % n is calculated is to raise a to the d power, then modulo that with n. Firstly, if a is large, this creates a huge number which is then truncated. However, x = pow(a, d, n) is most likely optimized so that only the last n digits are tracked, which are all that are required for calculating multiplication modulo a number.

x = a**d % n的计算方法是将a提高到d次方，然后用n来表示。首先，如果a是大的，这就会产生一个很大的数，然后被截断。然而，x = pow(a, d, n)很可能是经过优化的，以便只跟踪最后的n位数字，这是计算一个数字的乘法模的全部要求。

#1

156

#2