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

110

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 ?

Lyallcooper
sumber

Jawaban:

164

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
sumber
14
+1 sebenarnya yang diimplikasikan oleh docstring>>> 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
Bergantung pada versi Python Anda, ini mungkin hanya benar dalam kondisi tertentu. IIRC, dalam 3.x dan 2.7, Anda hanya dapat menggunakan bentuk tiga argumen dengan tipe integral (dan daya non-negatif), dan Anda akan selalu mendapatkan eksponensial modular dengan inttipe asli , tetapi tidak harus dengan tipe integral lainnya. Tetapi di versi yang lebih lama ada aturan tentang menyesuaikan ke dalam C long, formulir tiga argumen diizinkan untuk float, 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.)
abarnert
13
Dari jawaban Anda, sepertinya tidak mungkin bagi kompiler untuk melihat ekspresi dan mengoptimalkannya, yang mana tidak benar. Ini hanya terjadi bahwa tidak ada kompiler Python saat melakukannya.
danielkza
5
@danielkza: Itu benar, saya tidak bermaksud mengatakan itu secara teoritis tidak mungkin. Mungkin "tidak melihat ke masa depan" akan lebih akurat daripada "tidak bisa melihat ke masa depan". Namun, perlu diketahui bahwa pengoptimalan bisa sangat sulit atau bahkan tidak mungkin secara umum. Untuk operan konstan, ini dapat dioptimalkan, tetapi dalam x ** y % n, xdapat 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.
BrenBarn
2
@danielkza: Juga, fungsi tidak memiliki domain yang sama: .3 ** .4 % .5adalah legal, tetapi jika compiler berubah yang menjadi pow(.3, .4, .5)yang akan menaikkan TypeError. Compiler akan harus mampu untuk mengetahui bahwa a, d, dan ndijamin akan nilai-nilai tipe integral (atau mungkin hanya khusus jenis int, karena transformasi tidak membantu sebaliknya), dan ddijamin 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.
abarnert
37

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.

abarnert
sumber
2
kerinduan diperbaiki. coba pypy 2.0 beta 1 (tidak akan lebih cepat dari CPython, tetapi juga tidak boleh lebih lambat). gmpy tidak memiliki cara untuk menangani MemoryError :(
fijal
@fijal: Ya, dan gmpyjuga 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.
abarnert
1
dan jika Anda tidak peduli jika nomor Anda besar membuat program Anda segfault
fijal
1
Itu adalah faktor yang membuat PyPy tidak menggunakan library GMP untuk waktu yang lama. Mungkin tidak masalah bagi Anda, tidak baik bagi pengembang VM Python. Malloc bisa gagal tanpa menggunakan banyak RAM, taruh saja jumlah yang sangat besar di sana. Perilaku GMP sejak saat itu tidak ditentukan dan Python tidak dapat mengizinkannya.
fijal
1
@fijal: Saya sepenuhnya setuju bahwa itu tidak boleh digunakan untuk mengimplementasikan tipe bawaan Python. Itu tidak berarti itu tidak boleh digunakan untuk apa pun.
abarnert
11

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

atomicinf
sumber
3

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.

Yuushi
sumber
6
"itu membutuhkan perkalian d untuk menghitung x ** d" - tidak benar. Anda dapat melakukannya dalam perkalian O (log d) (sangat lebar). Eksponensial dengan kuadrat dapat digunakan tanpa modul. Ukuran perkalian yang besar itulah yang memimpin di sini.
John Dvorak
@ JanDvorak Benar, saya tidak yakin mengapa saya pikir python tidak akan menggunakan algoritma eksponensial yang sama **seperti untuk pow.
Yuushi
5
Bukan angka "n" terakhir .. itu hanya membuat perhitungan dalam Z / nZ.
Thomas