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

问题:

我试图实现一个Miller-Rabin primality test,并且为什么中档号码(〜7位数字)花费了这么长的时间(> 20秒)是困惑的。我最终发现以下代码行是问题的根源:

x = a**d % n

(其中adn都是相似的,但不等的中等数字,**是求幂运算符,%是模运算符)
然后我尝试用以下代替:

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运行Python Py或PyPy时,这个计算速度几乎是PyPy的两倍,当PyPy通常是much faster

回答:

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

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Why is pow(a, d, n) so much faster than a**d % n?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

79 + = 89