Was tun x = x * x mod (p) in Python der effizienteste Weg ist: (Ich weiß, dass x < p)x * x mod (p) am effizientesten pythonischer Weg?
x = pow(a, 2, p)
oder
x = x*x % p
oder
x *= x
x %= p
(Ich denke, dass x * x ist das gleiche wie x ** 2, wenn durch Eficiency gemessen, wenn nein, mich zu reparieren).
Python hat ein timeit Modul zum Testen genau diese Art der Sache:
$ python -m timeit 'x = 2000; p = 2002; x = pow(x, 2, p)'
10000000 loops, best of 3: 0.115 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x = (x * x) % p'
10000000 loops, best of 3: 0.0542 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x *= x; x %= p'
10000000 loops, best of 3: 0.0614 usec per loop
Ihre Antwort ist, dass (x * x) % p und x *= x; x %= p etwa gleich sind, aber pow ist viel langsamer.
Danke! Kannst du deinen Code posten? – Tom
Das ist die ganze Sache! Das hier angegebene Bit wird aus einer Terminalsitzung kopiert. Die Bits in Anführungszeichen werden vom Modul 'timeit', das Teil der Standardbibliothek ist, 10M-mal ausgewertet. –
Die zweite oder dritte. Der erste hat einen beliebigen Exponenten und wird darum einige * Kontrollstrukturen * um ihn herum haben. Aber der Unterschied zwischen dem zweiten und dritten wird sehr klein sein. –
Ich nehme an, * a * sollte * x * sein. Und warum fragst du das, wenn du einfach selbst einen Test machen und die Zeit messen kannst, die es braucht, um jede Operation 1000000 mal zu wiederholen. – trincot
Python enthält eine [timeit] (https://docs.python.org/2/library/timetit.html) Funktion. Probier es aus. – TemporalWolf