Mengapa pow (a, d, n) jauh lebih cepat daripada a ** d% n?

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,, ddan nsemuanya 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 ?

Lihat artikel Wikipedia tentang eksponen modular . Pada dasarnya, ketika Anda melakukannya a**d % n, Anda sebenarnya harus menghitung a**d, yang bisa jadi cukup besar. Tetapi ada cara komputasi a**d % ntanpa harus menghitung a**dsendiri, dan itulah yang powdilakukannya. The **Operator tidak bisa melakukan ini karena tidak dapat "melihat ke masa depan" untuk mengetahui bahwa Anda akan segera mengambil modulus.

BrenBarn menjawab pertanyaan utama Anda. Untuk sisi Anda:

mengapa hampir dua kali lebih cepat saat dijalankan dengan Python 2 atau 3 daripada PyPy, padahal biasanya PyPy jauh lebih cepat?

Jika Anda membaca halaman kinerja PyPy , ini adalah hal yang tidak bisa dilakukan PyPy — sebenarnya, contoh pertama yang mereka berikan:

Contoh buruk termasuk melakukan perhitungan dengan waktu yang lama - yang dilakukan oleh kode dukungan yang tidak dapat dioptimalkan.

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.

Ada jalan pintas untuk melakukan eksponensial modular: misalnya, Anda dapat mencari a**(2i) mod nsetiap idari 1hingga log(d)dan mengalikan (mod n) hasil antara yang Anda butuhkan. Fungsi eksponensial modular khusus seperti 3-argumen pow()dapat memanfaatkan trik semacam itu karena ia tahu Anda melakukan aritmatika modular. Pengurai Python tidak dapat mengenali ini karena ekspresi kosongnya a**d % n, jadi ia akan melakukan penghitungan penuh (yang akan memakan waktu lebih lama).

Cara x = a**d % ndihitung adalah untuk meningkatkan ake dkekuasaan, maka modulo bahwa dengan n. Pertama, jika abesar, ini membuat bilangan besar yang kemudian dipotong. Namun, x = pow(a, d, n)kemungkinan besar dioptimalkan sehingga hanya ndigit terakhir yang dilacak, yang semuanya diperlukan untuk menghitung perkalian modulo bilangan.