Czy są znane algorytmy subkwadratowe do obliczania wartości pierwiastka kwadratowego z n
liczby całkowitej?
Naiwny algorytm byłby podobny
def sqrt(x):
r = 0
i = x.bit_length() // 2
while i >= 0:
inc = (r << (i+1)) + (1 << (i*2))
if inc <= x:
x -= inc
r += 1 << i
i -= 1
return r
Wymaga to O(n)
iteracji, z których każda wiąże się z dodatkami, które są O(n)
czasem, więc O(n^2)
czas ogólnie. Czy jest coś szybciej? Wiem, że w przypadku mnożenia istnieją specjalne algorytmy, które działają lepiej niż czas kwadratowy, ale nie mogę znaleźć niczego dla pierwiastków kwadratowych.
algorithms
numerical-algorithms
Antymon
źródło
źródło
Odpowiedzi:
Możesz użyć metody Newtona lub dowolnej z wielu innych metod do znalezienia aproksymacji do pierwiastków wielomianu .p ( x ) =x2)- c
Szybkość zbieżności dla metody Newtona będzie kwadratowa, co oznacza, że liczba poprawnych bitów podwaja się w każdej iteracji. Oznacza to, że wystarczą iteracje metody Newtona.O ( lgn )
Każda iteracja metody Newtona jest obliczana
Złożoność bitowa mnożenia wynosi , aby pomnożyć dwaO (blgb) b -bit liczby całkowite (ignorowanie lglgb czynniki). Złożoność bitowa dla podziału (nab bitów precyzji) jest taki sam. Dlatego każdą iterację można obliczyć wO (nlgn) operacje. Mnożenie przezO(lgn) iteracje, okazuje się, że całkowity czas działania do obliczenia pierwiastka kwadratowego n precyzja jest O (n(lgn)2) . To jest subkwadratowe.
Myślę, że dokładniejsza analiza pokazuje, że można to poprawićO (nlgn) czas działania (biorąc pod uwagę, że musimy tylko znać każdy z nich xj w ciągu około j fragmenty precyzji, a nie n fragmenty precyzji). Jednak nawet bardziej podstawowa analiza już pokazuje czas działania, który jest wyraźnie subkwadratowy.
źródło
Jednym z problemów związanych z metodą Newtona jest to, że wymaga ona operacji dzielenia w każdej iteracji, która jest najwolniejszą podstawową operacją na liczbach całkowitych.
Jednak metoda Newtona dla odwrotnego pierwiastka kwadratowego nie. Gdybyx to numer, dla którego chcesz znaleźć 1x√ , iteruj:
Jest to często wyrażane jako:
To trzy operacje mnożenia. Podział na dwa można zastosować jako przesunięcie w prawo.
Problem w tym, żer nie jest liczbą całkowitą. Można jednak nim manipulować, wprowadzając ręcznie zmiennoprzecinkowe i wykonując kilka operacji przesunięcia, aby skompensować w razie potrzeby.
Najpierw przeskalujmyx :
gdzie chcielibyśmyx′ być większym, ale blisko, 1 . Jeśli uruchomimy powyższy algorytmx′ zamiast x , znaleźliśmy r=1x√′ . Następnie,x−−√=2erx′ .
Teraz podzielmy sięr w mantysę i wykładnik potęgi:
gdzier′i jest liczbą całkowitą. Intuicyjnie,ei reprezentują precyzję odpowiedzi.
Wiemy, że metoda Newtona z grubsza podwaja liczbę dokładnych cyfr znaczących. Możemy więc wybrać:
Przy odrobinie manipulacji znajdujemy:
Przy każdej iteracji:
Jako przykład spróbujmy obliczyć pierwiastek kwadratowy zx=263 . Wiemy, że odpowiedź brzmi2312–√ . Odwrotnym pierwiastkiem kwadratowym jest12√2−31 , więc ustawimy e=31 (to jest skala problemu) i na nasze początkowe przypuszczenia wybierzemy r′0=3 i e0=2 . (To znaczy, wybieramy34 dla naszego wstępnego oszacowania na 12√ .)
Następnie:
Możemy ustalić, kiedy przerwać iterację, porównującei do e ; jeśli poprawnie obliczyłem,ei>2e powinno być wystarczająco dobre. Zatrzymamy się tutaj i znajdziemy:
Prawidłowy pierwiastek kwadratowy z liczby całkowitej to3037000499 , więc jesteśmy bardzo blisko. Możemy wykonać kolejną iterację lub zoptymalizować iterację końcową, która się nie podwajaei . Szczegóły pozostawia się jako ćwiczenie.
Aby przeanalizować złożoność tej metody, zwróć uwagę, że pomnożenie dwóchb -bit liczba całkowita bierze O(blogb) operacje. Jednak tak to ułożyliśmyr′i<2ei . Więc mnożenie do obliczeniawi mnoży dwa ei -bitowe liczby, aby wygenerować ei+1 -bit liczba, a pozostałe dwa mnożenia mnożą dwa ei+1 -bitowe liczby, aby wygenerować 2ei+1 -bitowa liczba.
W każdym przypadku liczba operacji na iterację wynosiO(eilogei) , i tu są O(loge) wymagane iteracje. Ostateczne pomnożenie jest rzęduO(2elog2e) operacje. Ogólna złożoność jestO(elog2e) operacje, które są podkwadratowe pod względem liczby bitów w x . To zaznacza wszystkie pola.
W tej analizie kryje się jednak ważna zasada, o której powinni pamiętać wszyscy pracujący z dużymi liczbami całkowitymi: ponieważ mnożenie jest liczbą superliniową pod względem liczby bitów, wszelkie operacje mnożenia należy wykonywać tylko na liczbach całkowitych o przybliżonej wielkości bieżącej precyzji (i , Mógłbym dodać, powinieneś spróbować pomnożyć razem liczby, które mają podobny rząd wielkości). Używanie liczb całkowitych większych niż to strata wysiłku. Czynniki stałe są ważne, a dla dużych liczb całkowitych mają one duże znaczenie.
W końcowej obserwacji dwa z mnożenia mają formęab2c . Najwyraźniej nie ma sensu obliczać wszystkich bitówab tylko rzucić c z nich z przesunięciem w prawo. Wdrożenie inteligentnej metody mnożenia, która bierze to pod uwagę, również pozostawia się jako ćwiczenie.
źródło