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
, d
und n
sind 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 ?
quelle
>>> 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).
int
Typ, jedoch nicht unbedingt mit anderen integralen Typen. In älteren Versionen gab es jedoch Regeln für die Anpassung an ein Clong
, das Formular mit drei Argumentenfloat
usw. (Hoffentlich verwenden Sie nicht 2.1 oder früher und verwenden keine benutzerdefinierten Integraltypen aus C-Modulen, also keine davon ist dirx ** y % n
,x
kö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..3 ** .4 % .5
ist vollkommen legal, aber wenn der Compiler das inpow(.3, .4, .5)
das umwandelt , würde aTypeError
. Der Compiler müßte in der Lage sein , das zu wissena
,d
undn
sind garantiert Werte eines integralen Typs sein (oder vielleicht auch nur speziell vom Typint
, weil die Umwandlung nicht anders helfen), undd
garantiert 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.BrenBarn hat Ihre Hauptfrage beantwortet. Für Ihre Seite:
Wenn Sie die Leistungsseite von PyPy lesen , ist dies genau das, was PyPy nicht kann - in der Tat das allererste Beispiel, das sie geben:
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.quelle
gmpy
ist 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.Es gibt Abkürzungen für die modulare Exponentiation: Sie können beispielsweise
a**(2i) mod n
für jedesi
von1
bis dielog(d)
gewünschtenn
Zwischenergebnisse finden und miteinander multiplizieren (mod ). Eine dedizierte modulare Exponentiationsfunktion wie 3-Argumentepow()
kann solche Tricks nutzen, da sie weiß, dass Sie modulare Arithmetik ausführen. Der Python-Parser kann dies aufgrund des bloßen Ausdrucks nicht erkennena**d % n
und führt daher die vollständige Berechnung durch (was viel länger dauert).quelle
Der Weg, der
x = a**d % n
berechnet wird, besteht darin,a
auf died
Kraft zu erhöhen und dann das mit modulon
. Erstens, wenna
es groß ist, erzeugt dies eine große Zahl, die dann abgeschnitten wird. Es wird jedochx = pow(a, d, n)
höchstwahrscheinlich so optimiert, dass nur die letztenn
Ziffern verfolgt werden, die alles sind, was zur Berechnung des Multiplikationsmoduls einer Zahl erforderlich ist.quelle
**
wie fürpow
.