Liczenie pierwiastka kwadratowego w asm

najprosciej chyba rozlozyc na szereg....

U¿ytkownik "Pawe³" snipped-for-privacy@elsat.com.pl> napisa³ w wiadomo¶ci news:19152-1073852910@213.17.228.73...

Witam

moge jedynie podpowiedziec, ze do liczenia pierwiastka kwadratowego z liczby calkowitej, moze byc uzyty iteracyjny algorytm, bazujacy na obliczeniu sumy szeregu liczb naturalnych: S=1+2+3+...+n=n(n+1)/2 Mozna stad wyznaczyc n^2 jako: n^2=2*S-n obliczenie pierwiastka polega wiec na porownaniu iteracyjnie wyznaczonej wartosci n^2 z wartoscia argumentu i przerwaniu obliczen, gdy ich roznica staje sie ujemna.

powodzenia

insane_______________

Wyzeruj zmienna 16-bitowa, po czym ustaw jej najstarszy bit i podnies do kwadratu. Jesli wynik wyszedl wiekszy, niz liczba pierwiastkowana, wyzeruj ustawiony bit. Powtarzaj tak z wszystkimi kolejnymi bitami (w porzadku malejacych indeksow).

Pozdrawiam Piotr Wyderski

"Pawe³" napisa³:

Jaki procesor? Ma sprzêtowe mno¿enie? Mam taki kawa³ek kodu...

Dziêki za pomoc. Jest to tak oczywiste, ¿e trudno na to wpa¶æ.

Pawe³

Prosze bardzo. BTW, sposob dziala z kazda ciagla funkcja roznowartosciowa.

Pozdrawiam Piotr Wyderski

I monotoniczna ! I pod warunkiem ze sie prosto sprawdza.

Do liczenia pierwiastka jest swietny wzor iteracyjny x{n+1}=(x{n}+W/x{n})/2 Ale niestety - dobry jest na zmiennym przecinku, i trzeba miec dzielenie.

P.S. Jesli nie masz szybkiego sprzetowego mnozenia, to jeszcze mozna skorzystac ze (x+y)^2=x^2+2xy+y^2. Jak y w postaci binarnej ma tylko jeden bit, to wzorek robi sie prosty, x^2 znasz z poprzedniego kroku..

J.

Popieram - wzór jest bardzo szybki, tak¿e na sta³oprzecinkowych - wystarcz± trzy a nawet tylko dwie iteracje, je¶li dobierze siê odpowiednio pierwsze przybli¿enie x{1}. Powinno to byæ 1 z tak± liczb± zer jak po³owa d³ugo¶ci binarnej liczby pierwiastkowanej . Algorytm zaczyna siê wiêc od policzenia jak daleko od najm³odszego bitu jest najstarsza "jedynka" w liczbie pierwiastkowanej. Dodatkowa zaleta przy sta³oprzecinkowych, ca³kowitych : we wzorze iteracyjnym dzielenie przez 2 to po prostu przesuniêcie logiczne w prawo o jedn± pozycjê.

Powodzenia Roman

Sun, 11 Jan 2004 23:59:06 +0100, na pl.misc.elektronika, Paweł napisał(a):

To się chyba nazywa metoda Newtona-Raphsona

Dokładny opis algorytmu i asm dla PICa znajdziesz tu:

Tam pisze ze to sie NIE nazywa Newtona-Raphsona :-)

J.

On praktycznie podwaja ilosc bitow dokladnych za kazdym razem. Ale przydaloby sie miec choc ze dwa dokladne w pierwszym przyblizeniu :-)

J.

Mon, 12 Jan 2004 14:03:48 +0100, na pl.misc.elektronika, J.F. napisał(a):

Holmesie - jesteś genialny. Faktycznie jest napisane na samym początku, ale kto by tam wstępy czytał - do tego w obcym języku :-)

pozdrawiam Watson

A nawet teoretycznie. :-) To jeden z najszybciej zbieznych szeregow aproksymujacych pierwiastek. Niestety ma ukryty duzy czynnik staly i korzysta z dosc skomplikowanych procedur, wiec inicjatorowi watku na niewiele sie zda.

Pozdrawiam Piotr Wyderski

To _nie_ jest metoda N-R. Zazwyczaj nazywa sie to sukcesywna aproksymacja -- bardzo szybki algorytm dla malych danych, dla wiekszych sa znane lepsze.

Pozdrawiam Piotr Wyderski

Na jedn± iteracjê : jedno dzielenie, jedno dodawanie i jedno dzielenie przez

Roman

Aby to miec po 3 iteracjach to trzeba miec od czego wystartowac. A przypominam, ze chodzi o mikrokontroler, tu poswiecenie kilkuset bajtow albo nawet kilkudziesieciu na lookup tabelke jest swietokradztwem. Poza tym nie jestem przekonany czy dla 16 bitow "moj" algorytm nie bedzie znacznie szybszy niz 3 dzielenia wielokrotnej precyzji. Tu nie chodzi o stworzenie algorytmu asymptotycznie optymalnego, lecz o mozliwie najwydajniejszy dla _konkretnego_ rozmiaru slowa. A 16 bitow to jeszcze jest malo.

Pozdrawiam Piotr Wyderski

W swoim pierwszym po¶cie poda³em algorytm obliczenia pierwszego dobrego przybli¿enia - bez tabelek, jedna pêtla, same przesuniêcia logiczne rejestrów.

Roman

szumne slowa "lookup table". Z mojego starego programu

; w=c*2^m, when c is in range 1..2 ; x1=1.19*2^(m/2) for even m (1.19 is to be sqrt(sqrt(1)*sqrt(2)) ; 1.68*2^( (m-1)/2 ) for odd m (1.68 is sqrt(sqrt(2)*(sqrt(4)) ; then apply formula 3 times, and result is accurate to 24 bit

Czyli nawet nie trzeba dwoch bitow sprawdzac :-) Ale to bylo dla zmiennego przecinka.

Duzo zalezy ile trwa dzielenie a ile mnozenie i reszty architektury. Moga byc procki gdzie policzenie ile jest zerowych bitow z przodu wraz wyliczeniem wartosci poczatkowej potrwa niewiele krocej niz obliczenie pierwiastka twoim pomyslem, a potem 3 dzielenia beda trwaly wiecznosc.. a na Z80 bym raczej stawial N-R.

J.