Problem obliczania pierwiastka kwadratowego oraz zwrotu wartości całkowitej został zaproponowany na portalu GeeksForGeeks 12 sierpnia 2025 roku. Zaproponowano 4 algorytmy: naiwny z mnożeniem, wyszukiwanie binarne, oraz dwa korzystające z biblioteki wbudowanej, np. Python.math.
Dołączyłem jeszcze dwa swoje: naiwny z dodawaniem +=(2p+1), wspomniany miesiąc temu przy podawaniu złożoności wielomianowego algorytmu faktoryzacji, oraz jego rozwinięcie wykorzystujące fakt, że każdy kwadrat mozna zapisać jako 1 0 0 w systemie o pewnej podstawie p. Kod ostatniego niemiły, zaczyna działać dopiero dla wartości większych niż 100 w systemie dziesiętnym.
10*p + k, gdzie k wyznaczane z krotności możliwości konwersji przycięcia liczby N_p -> N_{p+k} do odpowiedniej długości względem p, jedna cyfra p na dwie cyfry z N = N[n]...N[1] N[0] w dziesiętnym
2p+1 < 100*reszta+10*N[b+1]+N[b]
Użyłem bardzo dużej liczby: 27997833911221327870829467638722601621070446786955428537560009929
26128400107609345671052955360856061822351910951365788637105954482
006576775098580557613579098734950144178863178946295187237869221823983
Algorytmy miały działać w parę sekund - tego testu naiwe nie przeszły.
Te, które w teorii były najszybsze, złożoności stałej O(1) zarówno pamięci jak i czasu, czyli
int(math.sqrt(n))
int(math.exp(0.5*math.log(n)))
podały błędne wyniki -- wystąpiła propagacja błędu obliczeń liczb zmiennoprzecinkowych, uzyskałem np. wartość
52912979420196447 944286770683838014
89465575494900455707262162396795715834972575453540520946581897216
Na portalu wspomniano, że wynik może być niezbyt dokładny, dokładniej nieco zaniżony. A okazał się znacznie zawyżony.
Poprawny wynik dały zaledwie dwa algorytmy z sześciu bez czekania:
52912979420196447 553235400217339415 00571661886712719898054010160087776775983652376577898717296799172
Zgodność z 'najszybszym' tylko na siedemnastu cyfrach dziesiętnych.
Jak to trzeba sprawdzać zakres stosowania bibliotek...
Brak komentarzy:
Prześlij komentarz