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

Question

我试图实施Miller-Rabin素性测试,并且很困惑为什么中等数字(~7位数)需要这么长时间(> 20秒).我最终发现以下代码行是问题的根源:

x = a**d % n

(where 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通常要快得多？

Answer 1

请参阅维基百科有关模幂运算的文章.基本上,当你这样做时a**d % n,你实际上必须计算a**d,这可能是非常大的.但是有一些计算方法,a**d % n而不必计算a**d自己,这就是做什么的pow.该**运营商不能做到这一点,因为它不能"预见未来"知道你要立即采取模数.

Answer 2

BrenBarn回答了你的主要问题.对你而言:

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

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

不好的例子包括使用大长度进行计算 - 这是由不可优化的支持代码执行的.

从理论上讲,将一个巨大的取幂,然后将mod转换为模幂运算(至少在第一次通过之后)是JIT可能做出的转换......但不是PyPy的JIT.

作为旁注,如果您需要使用大整数进行计算,您可能需要查看第三方模块gmpy,在某些情况下,在主流使用之外,有时可能比CPython的本机实现快得多,而且还有很多您不得不自己编写的附加功能,但代价是不方便.

Answer 3

有快捷方式做模幂:例如,你可以找到a**(2i) mod n每一个i从1以log(d)繁衍起来(MOD n),你需要的中间结果.像3参数pow()这样的专用模幂运算函数可以利用这些技巧,因为它知道你正在进行模运算.给定裸表达式时a**d % n,Python解析器无法识别它,因此它将执行完整计算(这将花费更长时间).