Saya mencoba menerapkan tes primalitas Miller-Rabin , dan bingung mengapa butuh waktu begitu lama (> 20 detik) untuk bilangan menengah (~ 7 digit). Saya akhirnya menemukan baris kode berikut sebagai sumber masalah:
x = a**d % n
(di mana a
,, d
dan n
semuanya serupa, tetapi tidak sama, bilangan menengah, **
adalah operator eksponen, dan %
merupakan operator modulo)
Saya kemudian saya mencoba menggantinya dengan yang berikut:
x = pow(a, d, n)
dan sebagai perbandingan, itu hampir seketika.
Untuk konteks, inilah fungsi aslinya:
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))
Contoh penghitungan berjangka waktu:
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)})
Output (dijalankan dengan PyPy 1.9.0):
2642565
time: 23.785543s
2642565
time: 0.000030s
Output (dijalankan dengan Python 3.3.0, 2.7.2 mengembalikan waktu yang sangat mirip):
2642565
time: 14.426975s
2642565
time: 0.000021s
Dan pertanyaan terkait, mengapa perhitungan ini hampir dua kali lebih cepat saat dijalankan dengan Python 2 atau 3 dibandingkan dengan PyPy, padahal biasanya PyPy jauh lebih cepat ?
sumber
>>> 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
tipe asli , tetapi tidak harus dengan tipe integral lainnya. Tetapi di versi yang lebih lama ada aturan tentang menyesuaikan ke dalam Clong
, formulir tiga argumen diizinkan untukfloat
, dll. (Mudah-mudahan Anda tidak menggunakan 2.1 atau sebelumnya, dan tidak menggunakan tipe integral kustom dari modul C, jadi tidak ada hal ini penting bagi Anda.)x ** y % n
,x
dapat berupa objek yang mengimplementasikan__pow__
dan, berdasarkan nomor acak, mengembalikan salah satu dari beberapa objek yang berbeda yang menerapkan__mod__
dengan cara yang juga bergantung pada nomor acak, dll..3 ** .4 % .5
adalah legal, tetapi jika compiler berubah yang menjadipow(.3, .4, .5)
yang akan menaikkanTypeError
. Compiler akan harus mampu untuk mengetahui bahwaa
,d
, dann
dijamin akan nilai-nilai tipe integral (atau mungkin hanya khusus jenisint
, karena transformasi tidak membantu sebaliknya), dand
dijamin untuk menjadi non-negatif. Itu adalah sesuatu yang bisa dilakukan oleh JIT, tetapi kompiler statis untuk bahasa dengan tipe dinamis dan tanpa inferensi tidak bisa.BrenBarn menjawab pertanyaan utama Anda. Untuk sisi Anda:
Jika Anda membaca halaman kinerja PyPy , ini adalah hal yang tidak bisa dilakukan PyPy — sebenarnya, contoh pertama yang mereka berikan:
Secara teoritis, mengubah eksponen besar diikuti oleh mod menjadi eksponen modular (setidaknya setelah lintasan pertama) adalah transformasi yang mungkin dapat dilakukan JIT… tetapi tidak JIT PyPy.
Sebagai catatan tambahan, jika Anda perlu melakukan perhitungan dengan bilangan bulat besar, Anda mungkin ingin melihat modul pihak ketiga seperti
gmpy
, yang terkadang bisa jauh lebih cepat daripada implementasi asli CPython dalam beberapa kasus di luar penggunaan utama, dan juga memiliki banyak fungsi tambahan yang seharusnya Anda tulis sendiri, dengan biaya yang kurang nyaman.sumber
gmpy
juga lebih lambat daripada lebih cepat dalam beberapa kasus, dan membuat banyak hal sederhana menjadi kurang nyaman. Itu tidak selalu jawabannya — tapi terkadang memang begitu. Jadi ada baiknya melihat jika Anda berurusan dengan bilangan bulat besar dan tipe asli Python tampaknya tidak cukup cepat.Ada jalan pintas untuk melakukan eksponensial modular: misalnya, Anda dapat mencari
a**(2i) mod n
setiapi
dari1
hinggalog(d)
dan mengalikan (modn
) hasil antara yang Anda butuhkan. Fungsi eksponensial modular khusus seperti 3-argumenpow()
dapat memanfaatkan trik semacam itu karena ia tahu Anda melakukan aritmatika modular. Pengurai Python tidak dapat mengenali ini karena ekspresi kosongnyaa**d % n
, jadi ia akan melakukan penghitungan penuh (yang akan memakan waktu lebih lama).sumber
Cara
x = a**d % n
dihitung adalah untuk meningkatkana
ked
kekuasaan, maka modulo bahwa dengann
. Pertama, jikaa
besar, ini membuat bilangan besar yang kemudian dipotong. Namun,x = pow(a, d, n)
kemungkinan besar dioptimalkan sehingga hanyan
digit terakhir yang dilacak, yang semuanya diperlukan untuk menghitung perkalian modulo bilangan.sumber
**
seperti untukpow
.