[R.....y]

#programowanie #matematyka #naukaprogramowania
Zrobiłem kod w pythonie, który ma sprawdzać dwoma algorytmami czy liczba jest pierwsza.
Czemu algorytm probabilistyczny jest tak zajebiście wolny?
kod: https://hastebin.com/lavoxokube

trywialny algorytm zajmuje dla dość małej liczby pierwszej 1.5e-3s
probabilistyczny (który wydawało mi sie że powinien zapierniczać) potrzebuje 3.269e-1
200 krotna różnica, i wydaje się że rośnie wykładniczo

[R.....y]

xd to zle napisales fast exponentiation.

@sezzart: bruh
po pokazaniu że faktycznie jest wolniejsze od wbudowanej implementacji, mówisz że jednak miałem użyć wbudowanej implementacji

[sezzart]

@RedveKoronny: Najpierw napisałeś że jest wolniejsze niż oryginał, a potem że interpreter pythona używa optymalnej implementacji. Wnioskuje więc że mówisz o swoim oryginalnym sposobie bo nie mam pojęcia co interpreter miałby mieć do czynienia z konkretną funkcją pow() ?

[R.....y]

@sezzart: nie mam narzędzi żeby zajrzeć do tego co się dzieje pod spodem, ale po tym jak mirek wyżej zaproponował funkcję pow z modulo, wszystko zaczęło działać. Może faktycznie problemem była pamięć, ewentualnie mój kod chyba dalej wisi, więc można na nim eksperymentować

[sezzart]

@RedveKoronny: A co do wbudowanej implementacji, nie miałem pojęcia czy coś takiego istnieje. Chciałeś sposób na szybsze liczenie to dostałeś...