23* *ve sürüyordu neden şaşırmıştı bu kadar uzun (>bir uygulamaya çalışıyordum Orta ölçekli sayılar (~7 basamak) için 20 saniye). Sonunda aşağıdaki kod satırını sorunun kaynağı bulundu:

x = a**d % n

(a, d n hepsi benzer, ama eşit olmayan, orta ölçekli sayılar ** üs alma operatörü ve % mod işleç)

Ben o zaman ben aşağıdaki ile değiştirilmesi çalıştı:

x = pow(a, d, n)

ve kıyasla neredeyse anlık olduğunu.

Bağlam için, burada orijinal fonksiyonu

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

Örnek hesaplama zamanlı:

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

Çıkış (PyPy 1.9.0 ile çalıştırın):

2642565
time: 23.785543s
2642565
time: 0.000030s

Çıkış 3.3.0, Python 2.7.2 döner ile çalıştırmak çok benzer kez ():

2642565
time: 14.426975s
2642565
time: 0.000021s

Ve Python 2 ile çalıştırdığınızda neredeyse iki kat daha hızlı ya da 3 bu hesaplama PyPy ile daha nedenle, genellikle PyPy much faster zaman ile ilgili bir soru?

modular exponentiation Wikipedia makalesine bakın. Ne zaman temelde, a**d % n, aslında oldukça büyük olabilir a**d, hesaplamak zorunda. Ama a**d kendisi hesaplamak zorunda kalmadan a**d % n hesaplamanın yolu vardır, ve bu pow yapıyor. ** operatör "" hemen modüllü. almak için gidiyoruz bilmek geleceği göremez, çünkü bunu yapamam