Pierwiastek - jaki algorytm?

Jeśli chodzi o operacje na liczbach całkowitych to ten algorytm jest bardzo efektywny. Jedna krok iteracji na jeden bit liczby.

Paweł

Michał pisze:

To tak bardziej ogólnie, ale jeśli chodzi Ci o pierwiastek kwadratowy z a, to jest banalnie proste, masz tam zresztą przykład. Bierzesz pierwsze przybliżenie, niech będzie np. x1=a/2. Następnie liczysz kolejne x2=1/2*(x1 + a/x1) i tak dalej, za każdym razem wyliczając kolejne przybliżenie, na podstawie poprzedniego, dopóki róznica pomiędzy kolejnymi wartościami x stanie się mniejsza od zadanego błędu i już :)

Ale tu akurat jest znana postac pochodnej.

Algorytm jest swietny, zbiega sie rewelacyjnie - kazda iteracja praktycznie podwaja ilosc dokladnych bitow ... tylko wymaga dzielenia zmiennoprzecinkowego. Co jest dosc kosztowne na malych prockach.

Jeszcze chyba CORDIC sie nadaje do pierwiastkow.

J.

Ale to chyba masz na mysli metode polowienia przedzialu a nie kolejna liczbe ..

J.

Przedział zawsze dzieli się na pół. Jeśli algorytm ma w wyniku dać liczbę 64-bitową to musisz zawsze wykonać

64 iteracje. Niezależnie od tego z jakiej liczby chcesz wyciągnąć pierwiastek. W większych AVRach jest mnożenie. Więc podnoszenie liczby do kwadratu jest stosunkowo szybkie.

Paweł

Michał pisze:

Jeśli bardzo ważny jest czas wykonywania to można wstępnie oszacować wielkość liczby z jakiej chcesz wyciągnąć pierwiastek. Wystarczy w zapisie binarnym liczby policzyć na jakiej pozycji znajduje się najstarsza jedynka. Następnie w zależności od tego przyjąć środek przedziału od jakiego zaczyna się poszukiwanie wyniku. W takim przypadku policzenie pierwiastka z 9 będzie szybsze niż z jakieś dużej liczby.

Paweł

do pierwiastkow to nie, ale do modułu dwóch liczb tak.

Michał pisze:

Zachęcam do przeczytania 9 rozdziału "Root finding and nonlinear sets of equations" z książki pod tytułem "Numerical Recipes in C 2nd". Opisane jest tam kilka metod otrzymywania pierwiastków.

Jakbyś miał problem z dostępem do książki do daj znać na prv. IMO Lektura godna polecenia.

W dniu 2008-05-30 20:47, Michał pisze:

Nie wiem, czy podany niżej algorytm Ci się przyda, ale na coś takiego natknąłem się chyba nawet na tej grupie jakiś czas temu i zapisałem sobie "na później":

Aby obliczyć drugi pierwiastek z liczby całkowitej wykonujemy czynności.

1.)Cyfry pierwiastkowanej grupujemy po dwie, zaczynając od prawej strony (od cyfry jednostek) 2.)Szukamy największej jednocyfrowej liczby, której kwadrat nie przekracza liczby określonej pierwszą od poczatku (od lewej strony) grupą cyfr.Umieszczamy ją za znakiem równości, podpisujemy pod pierwszą grupą cyfr i odejmujemy od niej. 3) Do otrzymanej różnicy dopisujemy drygą grupę cyfr i otrzymujemy druga liczbę wyjściową.Szukamy teraz największej jednocyfrowej liczby, która po dopisaniu do podwojonej liczby stojacej za znakiem równości i pomnożeniu jej przez otrzymaną liczbę daje liczbę mniejszą od drugiej liczby wyjściowej.Znalezioną liczbę jenocyfrową dopisujemy do poprzedniej stojącej za znakiem równości jako jej następna cyfrę. Czynność 4 jest analogiczna do czynności 3 przy czym startujemy z kolejnej różnicy.Pierwiastkowanie kończymy po wyczrpaniu wszystkich grup cyfr.Jeżeli jednak ostatnia rózniaca jest różna od zera, to możemy algorytm kontynuować, uzyskując kolejne miejsca dziesiętne szukanego pierwiastka

Sam nie próbowałem, więc nie powiem jak sprawnie to działa.