Jak efektywnie obliczać pierwiastek w języku C na maszynach AVR?

Fri May 30, 2008 7:47 pm   

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

Fri May 30, 2008 8:01 pm   

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

Paweł

Fri May 30, 2008 8:44 pm   

http://pl.wikipedia.org/wiki/Metoda_Newtona
RD

Fri May 30, 2008 8:49 pm   

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

Fri May 30, 2008 8:53 pm   

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

Fri May 30, 2008 9:11 pm   

Użytkownik "Michał" <sdfsdf@wp.pl> napisał w wiadomości
news:g1pm0f$j8i$1@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

Fri May 30, 2008 9:14 pm   

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ż
--
Pozdrawiam
Andrzej
www.album.radom.pl

Fri May 30, 2008 9:17 pm   

On Fri, 30 May 2008 21:53:50 +0200, Michał wrote:

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.

Fri May 30, 2008 9:19 pm   

On Fri, 30 May 2008 21:01:05 +0200, Paweł wrote:

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

J.

Fri May 30, 2008 10:13 pm   

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ł

Fri May 30, 2008 10:22 pm   

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ł

Sat May 31, 2008 9:30 am   

J.F. wrote:


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

--
pgw

Sat May 31, 2008 10:03 am   

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.

--
Piotr Piwko
http://www.embedded-engineering.pl/

Sat May 31, 2008 10:54 pm   

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.

--
Pozdrawiam,
Krzysiek

Sun Jun 01, 2008 1:35 pm   

Dziękuje wszystkim za odpowiedzi! Przydadzą się na pewno.

Pozdrawiam