[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

[kamilspl]

@RedveKoronny nie znam się na pythonie, ale ** to operator potęgowania?

[R.....y]

@kamilspl: tak

[hellfirehe]

@RedveKoronny: operator potęgowania dla tak dużych liczb działa tak długo.
Procesor nie ma instrukcji do operacji na tak dużych liczbach, zapewne pod spodem uruchamia się biblioteka do liczenia takich rzeczy która liczy to "na piechotę" w długich pętlach.

[kamilspl]

@RedveKoronny to pomyśl jak dużą liczbą jest 2^dużo (na oko tyle bitów ile dużo) i co się dzieje "pod spodem". Jest w pythonie odpowiednik sizeof z cpp?

[hellfirehe]

@RedveKoronny: prawdę mówiąc zastanawiam się dlaczego to działa aż tak szybko jak działa ;)

Jak się nad tym zastanowić to wynik operacji 2**n wymaga jednego bitu więcej niż wynosi n
Twoje n to 96790357, czyli wychodzi na to że dla zmieszczenia tej liczby trzeba mieć 12MB pamięci (na początku jedynka, potem same zera)
A potem na takim kolosie wykonać modulo (czyli dzielenie)

To w ogóle zwraca na pewno poprawny wynik?

[R.....y]

@hellfirehe: na liczbach które testowałem (3-20) działa

[R.....y]

@hellfirehe: @kamilspl: ok, pomysle nad innym testem, dzięki

[Saly]

@RedveKoronny: wez to wrzuc jeszcze raz, kurde jakiś martwy kod, komentarze z d--y

[kamilspl]

@RedveKoronny w zwykłej funkcji dodaj na początku kilka ifów (if%2, if%3 itd - przyspiesza).

[sezzart]

@RedveKoronny: nie inny test tylko uzyj fast exponentiation.

[R.....y]

@sezzart: jest jeszcze wolniej

[sezzart]

@RedveKoronny: xd to zle napisales fast exponentiation.

[vytah]

@RedveKoronny: W pythonie zamiast pisać x ** y % z, pisze się pow(x, y, z) i jest szybsze, bo nie musi potęgować olbrzymich liczb, tylko ciągle liczy modulo https://docs.python.org/3/library/functions.html#pow

pow(base, exp[, mod])

Return base to the power exp; if mod is present, return base to the power exp, modulo mod (computed more efficiently than pow(base, exp) % mod).

[R.....y]

@sezzart: albo po prostu interpreter pythona jest "nieco" sprytniejszy, i i tak używa bardziej optymalnych implementacji, niż for loop

[R.....y]

@vytah: no teraz to to za pier da la. Dzięki miras

[sezzart]

@RedveKoronny: Nie ma szans bo fast exponentiation to jest najszybszy sposób potegowania

[R.....y]

@sezzart: kurde, już wysyłam maila do autorów pythona, bo pewnie nie wpadli na to żeby go wykorzystywać domyślnie.

Ten algorytm jest fajny, ale nie bez powodu się go nie implementuje w każdym programie który używa potęgowania. Istniejące implementacje.

Ale zrobiłem testy, wg nich wbudowana funkcja jest zaledwie 3 razy szybsza

[R.....y]

@RedveKoronny: dodałem do testów operator \*\*
wynik porównywalny z funkcją pow, czyli dalej przewaga na niekorzyść algorytmu na szybkie potęgowanie

[R.....y]

Istniejące implementacje.

@RedveKoronny: ucięło komentarz
istniejące implementacje już są bardzo dobre, i zwykle będą lepsze, niż wynajdywanie koła na nowo

[sezzart]

@RedveKoronny: No ale porownujesz naiwne * do biblioteki która prawdopodobnie używa lepszego formatu liczb (i pewnie fast exp w środku). Widzisz że przy n wielkości 100k masZ 30 razy szybszy wynik niż w starym sposobie