Algorytm obliczania pierwiastka kwadratowego 32-bit w ASM dla AVR ? szukam procedury
Liczenie pierwiastka kwadratowego w asm
From: "Paweł" <pawelr_at_nospam_elsat.com.pl>
Subject: Liczenie pierwiastka kwadratowego w asm
Date: Sun, 11 Jan 2004 21:28:41 +0100
Witam !
Jaki jest algorytm obliczania pierwiastka kwadratowego z liczby całkowitej
32bit. Wynik ma być całkowity 16 bit.
Może ktoś dysponuje gotową procedurą w asm na procesor AVR.
Paweł
========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!news.man.poznan.pl!news.nask.pl!uw.edu.pl!news.pw.edu.pl!not-for-mai
From: "Greg" <xgrzes_at_nospam_poczta.onet.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Sun, 11 Jan 2004 21:35:51 +0100
najprosciej chyba rozlozyc na szereg....
========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!news2.icm.edu.pl!news.pw.edu.pl!not-for-mai
From: "insane" <not_at_nospam_here.com>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Sun, 11 Jan 2004 21:44:28 +0100
Użytkownik "Paweł" <pawelr_at_nospam_elsat.com.pl> napisał w wiadomości
news:19152-1073852910_at_nospam_213.17.228.73...
Witam !
Witam
Jaki jest algorytm obliczania pierwiastka kwadratowego z liczby całkowitej
32bit. Wynik ma być całkowity 16 bit.
Może ktoś dysponuje gotową procedurą w asm na procesor AVR.
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_______________
http://www.izi.republika.pl
========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!newsfeed.silweb.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_wp.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Sun, 11 Jan 2004 22:03:40 +0100
Paweł wrote:
Jaki jest algorytm obliczania pierwiastka kwadratowego z liczby całkowitej
32bit. Wynik ma być całkowity 16 bit.
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
========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!news.man.poznan.pl!news.internetia.pl!not-for-mai
From: "Paweł" <pawelr_at_nospam_elsat.com.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Sun, 11 Jan 2004 23:59:06 +0100
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).
Dzięki za pomoc.
Jest to tak oczywiste, że trudno na to wpaść.
Paweł
========
Path: news-archive.icm.edu.pl!mat.uni.torun.pl!news.man.torun.pl!news.man.poznan.pl!news.internetia.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_wp.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Mon, 12 Jan 2004 01:19:44 +0100
Paweł wrote:
Dzięki za pomoc.
Jest to tak oczywiste, że trudno na to wpaść.
Prosze bardzo. BTW, sposob dziala z kazda ciagla
funkcja roznowartosciowa.
Pozdrawiam
Piotr Wyderski
========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai
From: J.F. <jfox_nospam_at_nospam_poczta.onet.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Mon, 12 Jan 2004 02:14:13 +0100
On Mon, 12 Jan 2004 01:19:44 +0100, Piotr Wyderski wrote:
Dzięki za pomoc. Jest to tak oczywiste, że trudno na to wpaść.
Prosze bardzo. BTW, sposob dziala z kazda ciagla
funkcja roznowartosciowa.
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.
========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai
From: "Roman" <romantek_at_nospam_poczta.onet.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Mon, 12 Jan 2004 12:39:29 +0100
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.
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
========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai
From: J.F. <jfox_nospam_at_nospam_poczta.onet.pl>
Subject: Re: Liczenie pierwiastka kwadratowego w asm
Date: Mon, 12 Jan 2004 14:03:48 +0100
On Mon, 12 Jan 2004 12:39:29 +0100, Roman wrote:
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.
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}.
On praktycznie podwaja ilosc bitow dokladnych za kazdym razem.
Ale przydaloby sie miec choc ze dwa dokladne w pierwszym przyblizeniu
-)
J.
========
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!news.task.gda.pl!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai