Warum ist pow (a, d, n) so viel schneller als a ** d% n?

110

Ich habe versucht, einen Miller-Rabin-Primalitätstest durchzuführen , und war verwirrt, warum es für mittelgroße Zahlen (~ 7 Stellen) so lange (> 20 Sekunden) dauerte. Ich fand schließlich die folgende Codezeile als Ursache des Problems:

x = a**d % n

(wo a, dund nsind alle ähnlich, aber ungleich, midsize Zahlen, **ist der Exponential - Operator, und %ist der Modulo - Operator)

Ich habe dann versucht, es durch Folgendes zu ersetzen:

x = pow(a, d, n)

und im Vergleich dazu ist es fast augenblicklich.

Für den Kontext ist hier die ursprüngliche Funktion:

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

Ein Beispiel für eine zeitgesteuerte Berechnung:

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

Ausgabe (mit PyPy 1.9.0 ausführen):

2642565
time: 23.785543s
2642565
time: 0.000030s

Ausgabe (mit Python 3.3.0 ausgeführt, 2.7.2 liefert sehr ähnliche Zeiten):

2642565
time: 14.426975s
2642565
time: 0.000021s

Und eine verwandte Frage: Warum ist diese Berechnung mit Python 2 oder 3 fast doppelt so schnell wie mit PyPy, wenn PyPy normalerweise viel schneller ist ?

Lyallcooper
quelle

Antworten:

164

Siehe den Wikipedia-Artikel zur modularen Potenzierung . Grundsätzlich müssen a**d % nSie dann tatsächlich rechnen a**d, was ziemlich groß sein kann. Es gibt jedoch Möglichkeiten zum Rechnen, a**d % nohne sich selbst berechnen zu müssen a**d, und genau das powtut es. Der **Bediener kann dies nicht tun, weil er nicht "in die Zukunft sehen" kann, um zu wissen, dass Sie sofort den Modul nehmen werden.

BrenBarn
quelle
14
+1 das ist eigentlich, was der Docstring impliziert>>> print pow.__doc__ pow(x, y[, z]) -> number With two arguments, equivalent to x**y. With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
Hedde van der Heide
6
Abhängig von Ihrer Python-Version kann dies nur unter bestimmten Bedingungen zutreffen. IIRC, in 3.x und 2.7, können Sie die Form mit drei Argumenten nur mit integralen Typen (und nicht negativer Potenz) verwenden, und Sie erhalten immer eine modulare Exponentiation mit dem nativen intTyp, jedoch nicht unbedingt mit anderen integralen Typen. In älteren Versionen gab es jedoch Regeln für die Anpassung an ein C long, das Formular mit drei Argumenten floatusw. (Hoffentlich verwenden Sie nicht 2.1 oder früher und verwenden keine benutzerdefinierten Integraltypen aus C-Modulen, also keine davon ist dir
wichtig
13
Aus Ihrer Antwort geht hervor, dass es für einen Compiler unmöglich ist, den Ausdruck zu sehen und zu optimieren, was nicht stimmt. Es kommt einfach vor, dass dies keine aktuellen Python-Compiler tun.
Danielkza
5
@danielkza: Das stimmt, ich wollte nicht implizieren, dass es theoretisch unmöglich ist. Vielleicht wäre "schaut nicht in die Zukunft" genauer als "kann nicht in die Zukunft sehen". Beachten Sie jedoch, dass die Optimierung im Allgemeinen äußerst schwierig oder sogar unmöglich sein kann. Für konstante Operanden kann es optimiert werden, aber in x ** y % n, xkönnte ein Ziel sein , dass Geräte __pow__und auf der Basis einer Zufallszahl, gibt eine von mehreren verschiedenen Objekten Umsetzung __mod__in einer Weise , die auch auf Zufallszahlen abhängen, usw.
BrenBarn
2
@danielkza: Auch die Funktionen haben nicht die gleiche Domain: .3 ** .4 % .5ist vollkommen legal, aber wenn der Compiler das in pow(.3, .4, .5)das umwandelt , würde a TypeError. Der Compiler müßte in der Lage sein , das zu wissen a, dund nsind garantiert Werte eines integralen Typs sein (oder vielleicht auch nur speziell vom Typ int, weil die Umwandlung nicht anders helfen), und dgarantiert nicht-negativ. Das könnte eine JIT tun, aber ein statischer Compiler für eine Sprache mit dynamischen Typen und ohne Inferenz kann das einfach nicht.
Abarnert
37

BrenBarn hat Ihre Hauptfrage beantwortet. Für Ihre Seite:

Warum ist es mit Python 2 oder 3 fast doppelt so schnell wie PyPy, wenn PyPy normalerweise viel schneller ist?

Wenn Sie die Leistungsseite von PyPy lesen , ist dies genau das, was PyPy nicht kann - in der Tat das allererste Beispiel, das sie geben:

Schlechte Beispiele sind Berechnungen mit großen Longs - die von nicht optimierbarem Support-Code ausgeführt werden.

Theoretisch ist die Umwandlung einer großen Potenzierung, gefolgt von einem Mod, in eine modulare Potenzierung (zumindest nach dem ersten Durchgang) eine Transformation, die eine JIT möglicherweise durchführen kann… aber nicht die JIT von PyPy.

Nebenbei bemerkt, wenn Sie Berechnungen mit großen Ganzzahlen durchführen müssen, sollten Sie sich Module von Drittanbietern ansehen gmpy, die manchmal viel schneller als die native Implementierung von CPython sind, in einigen Fällen außerhalb der Mainstream-Anwendungen, und auch viel haben von zusätzlichen Funktionen, die Sie sonst selbst schreiben müssten, auf Kosten der Bequemlichkeit.

abarnert
quelle
2
Sehnsüchte wurden behoben. Probieren Sie Pypy 2.0 Beta 1 aus (es ist nicht schneller als CPython, sollte aber auch nicht langsamer sein). gmpy hat keine Möglichkeit, mit MemoryError umzugehen :(
Fidschal
@fijal: Ja, und gmpyist in einigen Fällen auch langsamer statt schneller und macht viele einfache Dinge weniger bequem. Es ist nicht immer die Antwort - aber manchmal ist es das auch. Es lohnt sich also zu prüfen, ob es sich um große Ganzzahlen handelt und der native Typ von Python nicht schnell genug zu sein scheint.
Abarnert
1
und wenn es Ihnen egal ist, ob Ihre Zahlen groß sind, macht Ihr Programm Segfault
Fidschal
1
Dies ist der Faktor, der dazu geführt hat, dass PyPy die GMP-Bibliothek nicht für lange Zeit verwendet. Es könnte für Sie in Ordnung sein, es ist nicht in Ordnung für Python VM-Entwickler. Das Malloc kann ausfallen, ohne viel RAM zu verbrauchen. Geben Sie einfach eine sehr große Anzahl ein. Das Verhalten von GMP ab diesem Zeitpunkt ist undefiniert und Python kann dies nicht zulassen.
Fidschal
1
@fijal: Ich stimme vollkommen zu, dass es nicht für die Implementierung des integrierten Python-Typs verwendet werden sollte. Das bedeutet nicht, dass es niemals für irgendetwas verwendet werden sollte.
Abarnert
11

Es gibt Abkürzungen für die modulare Exponentiation: Sie können beispielsweise a**(2i) mod nfür jedes ivon 1bis die log(d)gewünschten nZwischenergebnisse finden und miteinander multiplizieren (mod ). Eine dedizierte modulare Exponentiationsfunktion wie 3-Argumente pow()kann solche Tricks nutzen, da sie weiß, dass Sie modulare Arithmetik ausführen. Der Python-Parser kann dies aufgrund des bloßen Ausdrucks nicht erkennen a**d % nund führt daher die vollständige Berechnung durch (was viel länger dauert).

atomicinf
quelle
3

Der Weg, der x = a**d % nberechnet wird, besteht darin, aauf die dKraft zu erhöhen und dann das mit modulo n. Erstens, wenn aes groß ist, erzeugt dies eine große Zahl, die dann abgeschnitten wird. Es wird jedoch x = pow(a, d, n)höchstwahrscheinlich so optimiert, dass nur die letzten nZiffern verfolgt werden, die alles sind, was zur Berechnung des Multiplikationsmoduls einer Zahl erforderlich ist.

Yuushi
quelle
6
"es erfordert d Multiplikationen, um x ** d zu berechnen" - nicht korrekt. Sie können dies in O (log d) (sehr breiten) Multiplikationen tun. Die Potenzierung durch Quadrieren kann ohne Modul verwendet werden. Die schiere Größe der Multiplikanden übernimmt hier die Führung.
John Dvorak
@ JanDvorak Stimmt, ich bin mir nicht sicher, warum ich dachte, Python würde nicht den gleichen Potenzierungsalgorithmus verwenden **wie für pow.
Yuushi
5
Nicht die letzten "n" Ziffern. Es werden nur Berechnungen in Z / nZ gespeichert.
Thomas