oxygenium79 napisał(a):
Wiadomo, że spowalnia, już nie Operujesz na 64 bitowych rejestrach, tylko na bigintach, które generalnie są stringami.
Ale Pyton nie spowalnia? Dla C++ granicą jest liczba 18446744073709551557, potem musiałem użyć GMP co strasznie spowolniło.
Python jeszcze bardziej spowolni, zwłaszcza, że powyżej long max nie będzie tak łatwo użyć jit, dlatego dla takich liczb juz się stosuje inne algorytmy.
Np:
Fermat(wrażliwy na pseudo pierwsze):
def is_prime_fermat(n):
if n == 2:
return True
if not n & 1:
return False
return pow(2, n-1, n) == 1
Miller - Rabin:
from random import randrange
def is_prime_mr(n, k=20):
if n == 2:
return True
if not n & 1:
return False
def check(a, s, d, n):
x = pow(a, d, n)
if x == 1:
return True
for i in xrange(s - 1):
if x == n - 1:
return True
x = pow(x, 2, n)
return x == n - 1
s = 0
d = n - 1
while d % 2 == 0:
d >>= 1
s += 1
Jeszcze lepiej Miller - Rabin jest zaimplementowany w GMP - ma lepszy algorytm mnożenia. W Pythonie Karatsuba O(n^1.37), a w GMP mnożenie jest O(n).