Montgomery reduction algorithm (Python) : Mi ezzel a baj?
Ezt a "pow"-t teszteltem, és lassúbb, mint a beépített, "gyári" pow(x,y,mod) függvény, pedig elvileg jóval gyorsabbnak kéne lennie a többezer jegyű számokkal, mert a hosszú maradékos osztás ki van küszöbölve (csak bittologatás).
A gyáriban biztos hogy ez nincs optimalizálva, hiszen a méret köbével arányos a futásidő.
Jó eredményt ad (ellenőriztem), de lassú. Miért? Mi ezzel a baj?
válasza:Nem kell feltalálni a meleg vizet újból.
A gmpy2 modul lesz a barátod. Natív kódba kioptimalizált kiegészítő modul.
"A GMP-t gondosan tervezték, hogy a lehető leggyorsabb legyen" ... [link]
pythonhoz modul : [link]
Telepítési "anomália" és megoldás : [link]
A pow ezzel az mpz típussal sokkal gyorsabban hatványoz mint a beépített int típussal.
Prím eldöntése az is_prime tagfüggvényével lehet.
Köszönöm!
Nagyon jónak tűnik.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!