Algorytm precyzji pierwiastka kwadratowego?

9

Czy są znane algorytmy subkwadratowe do obliczania wartości pierwiastka kwadratowego z nliczby 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.

Antymon
źródło
Moja odpowiedź na coś związanego może pomóc cs.stackexchange.com/a/37338/12052 . Jedynym problemem jest część niezbędnego równania, które trzeba znaleźć empirycznie, aby poprawić jego dokładność.
Francesco Gramano
@FrancescoGramano: Przepraszam, nie sądzę, że to pomaga.
Aryabhata
btw, czy to wymaganie subkwadratowe stanowi część większego problemu? Ponieważ różnica między prostym kwadratowym i skomplikowanym subkwadratowym może nie być tak duża w praktyce. Czy może to tylko teoretyczne zainteresowanie?
Aryabhata
@Aryabhata Przepraszamy, nie widziałem wcześniej Twojego komentarza. Nie, to nie jest część większego problemu, tylko ciekawość.
Antymon

Odpowiedzi:

5

Możesz użyć metody Newtona lub dowolnej z wielu innych metod do znalezienia aproksymacji do pierwiastków wielomianu .p(x)=x2c

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

xj+1=xj(xj2c)/(2xj)=0.5xj+c2xj.

Złożoność bitowa mnożenia wynosi , aby pomnożyć dwaO (blgb)b-bit liczby całkowite (ignorowanie lglgbczynniki). Złożoność bitowa dla podziału (nabbitó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 nfragmenty precyzji). Jednak nawet bardziej podstawowa analiza już pokazuje czas działania, który jest wyraźnie subkwadratowy.

DW
źródło
W systemie binarnym można również zgadywać początkowo, używając tożsamości x1/2=21/2log2x. Zamiast obliczać dziennik, można go przybliżaćlog2x jako liczba cyfr w x. Na przykład,log21010116.
Nick Alger
@DW: Ale czy nie szukamy pierwiastka z liczby całkowitej? Jeśli wykonujesz iterację metody Newtona, używając tylko arytmetyki liczb całkowitych, potrzebujemy dodatkowego uzasadnienia dlaO(logn)twierdzimy, prawda? W przeciwnym razie zakładamy już wystarczająco dużą precyzję ... Przepraszam, jeśli coś oczywistego mi brakuje.
Aryabhata
@DW: „Szybkość konwergencji dla metody Newtona” nie będzie kwadratowa, jeśli c=0i nie wiem, co się stanie dla wartości c które nie są rzeczywistością nieujemną. Twoje oszacowanie złożoności bitowej mnożenia jest dokładniejsze niż sugeruje poniższa uwaga . Ponadto „musimy znać każdego z nich xj w ciągu około „ 2j „kawałki precyzji”.
@Aryabhata: Nie do końca „szukamy pierwiastka kwadratowego z liczby całkowitej”; szukamy „podłogi pierwiastka kwadratowego”. Masz rację w kwestii arytmetyki liczb całkowitych, chociaż te same złożoności bitów dotyczą operacji zmiennoprzecinkowych.
1
@RickyDemer, tak, c=0 jest szczególnym przypadkiem, ponieważ wtedy root p(x) ma wielokrotność 2, ale kiedy c>0Korzeń zawiera wielokrotność 1 więc metoda Newtona nie ma kwadratowego zbieżności. Zakładam, że nikt nie użyłby metody Newtona do obliczenia pierwiastka kwadratowego zc=0(ponieważ pierwiastek kwadratowy zera jest oczywiście zerowy). Więc co próbujesz powiedzieć? Czy twój komentarz jest trywialny, na który można odpowiedzieć, dodając do mojej odpowiedzi coś, co mówi „szczególny przypadek pierwiastek kwadratowy zera”, czy też jest coś głębszego, czego mi brakuje?
DW
7

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:

ri+1=12ri(3xri2)

Jest to często wyrażane jako:

wi=ri2
di=1wix
ri+1=ri+ridi2

To trzy operacje mnożenia. Podział na dwa można zastosować jako przesunięcie w prawo.

Problem w tym, że rnie 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 przeskalujmy x:

x=22ex

gdzie chcielibyśmy x 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:

ri=2eiri

gdzie rijest 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ć:

ei+1=2ei

Przy odrobinie manipulacji znajdujemy:

ei+1=2ei
wi=ri2
xi=x22eei+1
di=2ei+1wixi2ei+1
ri+1=2eiriridi2ei+1

Przy każdej iteracji:

xrix2e+ei

Jako przykład spróbujmy obliczyć pierwiastek kwadratowy z x=263. Wiemy, że odpowiedź brzmi2312. Odwrotnym pierwiastkiem kwadratowym jest12231, więc ustawimy e=31 (to jest skala problemu) i na nasze początkowe przypuszczenia wybierzemy r0=3 i e0=2. (To znaczy, wybieramy34 dla naszego wstępnego oszacowania na 12.)

Następnie:

e1=4,r1=11
e2=8,r2=180
e3=16,r3=46338
e4=32,r4=3037000481

Możemy ustalić, kiedy przerwać iterację, porównując ei do e; jeśli poprawnie obliczyłem,ei>2epowinno być wystarczająco dobre. Zatrzymamy się tutaj i znajdziemy:

2633037000481×263231+32=3037000481

Prawidłowy pierwiastek kwadratowy z liczby całkowitej to 3037000499, 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óch b-bit liczba całkowita bierze O(blogb)operacje. Jednak tak to ułożyliśmyri<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ę wynosi O(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ć cz nich z przesunięciem w prawo. Wdrożenie inteligentnej metody mnożenia, która bierze to pod uwagę, również pozostawia się jako ćwiczenie.

Pseudonim
źródło
To świetne rzeczy. Jeden komentarz: czy złożoność bitowa podziału nie jest w przybliżeniu taka sama jak złożoność bitowa mnożenia? Mówisz więc o czymś, co daje ciągłą poprawę czynników, a nie poprawę asymptotyczną, prawda? To nie było całkowicie jasne z twojej odpowiedzi.
DW
Mówisz, że pomnożenie dwóch b-bit liczba całkowita bierze O(blgb)operacje bitowe. Myślę, że poprawna odpowiedź jest jakośO(blgb(lglgb)O(1))(dobrze?). Możesz wskazać, że ignorujesz czynniki poliblog (np. Umieszczając tyldę nad dużym O lub coś takiego).
DW
1
@DW: Nie, mówi, że „pomnożenie dwóch b-bit liczba całkowita bierze O(blogb) operacje ”. Słowo „bit” pojawia się tylko raz; inaczej bym już to zauważył.
Tak, to kwestia stałych czynników. Najlepsze algorytmy dzielenia dużych liczb całkowitych wykorzystują technikę bardzo podobną do całego algorytmu, taką jak iteracja Newtona-Raphsona i podwajanie efektywnej precyzji na każdej iteracji. Pętla Newtona-Raphsona w pętli Newtona-Raphsona opiera się na czynnikach stałych! Ricky Demer ma rację; Myślałem o słowie model RAM. Prawdopodobnie powinienem o tym wspomnieć.
pseudonim