Witam wszystkich Mam takie pytanie trochê nie zwi±zane z elektronik± a raczej z programowaniem. Zadaje pytanie na tej grupie bo z tym problemem w³a¶ciwie na du¿ych maszynach nikt siê nie przejmuje. Jak jest robiona operacja pierwiastkowania w C pod kompilatorem dla AVRów? Czy jest podnoszona do kwadratu kolejna liczba i porównywany jest wynik? Trochê to ma³o efektywne. Jest na to jaki¶ algorytm?
Pozdrawiam
Jeśli chodzi o operacje na liczbach całkowitych to ten algorytm jest bardzo efektywny. Jedna krok iteracji na jeden bit liczby.
Paweł
Czyli jak rozumie jak wynik zapisuje w 64 bitowej zmiennej uint64_t to maksymalnie bêdzie 64 cykle, a jak np. wyci±gnê pierwiastek z 9 to bêdzie znacznie mniej iteracji? Dobrze to rozumie?
64 operacje to jeszcze nie taki problem.Pozdrawiam
Dziêkujê za informacjê, ale w AVRach chyba tego nie wykorzystuj± ze wzglêdu na: "Wad± metody Newtona jest konieczno¶æ wyznaczania warto¶ci funkcji pochodnej, co w zastosowaniach komputerowych jest k³opotliwe gdy nie jest znana analityczna postaæ funkcji."
Pozdrawiam
U¿ytkownik "Micha³" snipped-for-privacy@wp.pl napisa³ w wiadomo¶ci news:g1pm0f$j8i$ snipped-for-privacy@achot.icm.edu.pl...
rzuc okiem na akapit "przyklad" i wszystko jasne. A postac analityczna funkcji pierwiastkujacej chyba jest znana dosc dobrze :) Metoda Newtona z tego co pamietam jest wykorzystywana w kalkulatorach - daje szereg przyblizen bardzo szybko zbiezny. A wiec pewnie w AVR-ach tez
MaW
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 pierwiastkaSam nie próbowałem, więc nie powiem jak sprawnie to działa.
Dziêkuje wszystkim za odpowiedzi! Przydadz± siê na pewno.
Pozdrawiam
Have something to add? Share your thoughts — no account required.
Ask the community — no account required