Dlaczego pow (a, d, n) jest dużo szybsze niż a ** d% n?

Próbowałem zaimplementować test pierwszości Millera-Rabina i byłem zdziwiony, dlaczego trwa to tak długo (> 20 sekund) dla średnich liczb (~ 7 cyfr). Ostatecznie znalazłem następujący wiersz kodu jako źródło problemu:

x = a**d % n

(gdzie a,d i nsą podobne, ale nierówne, średnie liczby, **to operator potęgowanie i %jest operatorem modulo)

Następnie próbowałem zastąpić go następującym:

x = pow(a, d, n)

i to w porównaniu jest prawie natychmiastowe.

W kontekście, oto oryginalna funkcja:

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

Przykładowe obliczenia czasowe:

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

Wyjście (uruchom z PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

Dane wyjściowe (uruchomione z Pythonem 3.3.0, 2.7.2 zwraca bardzo podobne czasy):

2642565
time: 14.426975s
2642565
time: 0.000021s

I powiązane pytanie, dlaczego te obliczenia są prawie dwa razy szybsze, gdy są uruchamiane z Pythonem 2 lub 3 niż z PyPy, podczas gdy zwykle PyPy jest znacznie szybsze ?

Zobacz artykuł w Wikipedii dotyczący potęgowania modularnego . Zasadniczo, kiedy to zrobisz a**d % n, musisz obliczyć a**d, co może być dość duże. Ale są sposoby obliczania a**d % nbez konieczności obliczania a**dsamego siebie i tak właśnie powjest. **Operator nie może tego zrobić, ponieważ nie może „widzieć w przyszłości”, aby wiedzieć, że idziesz do natychmiastowego odbioru modułu.

BrenBarn odpowiedział na twoje główne pytanie. Poza tym:

dlaczego jest prawie dwa razy szybszy, gdy działa z Pythonem 2 lub 3 niż PyPy, podczas gdy zwykle PyPy jest znacznie szybszy?

Jeśli przeczytasz stronę wydajności PyPy , to jest dokładnie w tym rodzaju rzeczy, w których PyPy nie jest dobry - w rzeczywistości jest to pierwszy przykład, który podają:

Złe przykłady obejmują wykonywanie obliczeń z dużymi długimi wartościami - które są wykonywane przez nieoptymalizowany kod pomocniczy.

Teoretycznie, przekształcenie ogromnego potęgowania, po którym następuje mod, w modułowe potęgowanie (przynajmniej po pierwszym przejściu) jest transformacją, którą JIT może wykonać… ale nie JIT PyPy.

Na marginesie, jeśli musisz wykonywać obliczenia z dużymi liczbami całkowitymi, możesz spojrzeć na moduły innych firm, takie jak gmpy, które czasami mogą być znacznie szybsze niż natywna implementacja CPythona w niektórych przypadkach poza głównymi zastosowaniami, a także ma wiele dodatkowej funkcjonalności, którą w innym przypadku musiałbyś napisać samodzielnie, kosztem mniejszej wygody.

Istnieją skróty do wykonywania modularnego potęgowania: na przykład możesz znaleźć a**(2i) mod ndla każdego iod 1do log(d)i pomnożyć razem (mod n) potrzebne wyniki pośrednie. Dedykowana funkcja potęgowania modularnego, taka jak 3-argumentowa, pow()może wykorzystać takie sztuczki, ponieważ wie, że wykonujesz arytmetykę modularną. Parser Pythona nie może tego rozpoznać na podstawie samego wyrażenia a**d % n, więc wykona pełne obliczenie (co zajmie znacznie więcej czasu).

Sposób x = a**d % nobliczania to podniesienie ado dpotęgi, a następnie modulo to z n. Po pierwsze, jeśli ajest duża, tworzy to ogromną liczbę, która jest następnie obcięta. Jednak x = pow(a, d, n)najprawdopodobniej jest zoptymalizowany tak, że nśledzone są tylko ostatnie cyfry, które są wszystkim, co jest wymagane do obliczenia mnożenia modulo liczba.