Kod: Zaznacz cały
http://www.deltami.edu.pl/temat/matematyka/algebra/2018/01/25/Pierwiastkowanie_pod_kreska/JK
Na czym polega pierwiastkowanie
-
Jan Kraszewski
- Administrator
- Posty: 34345
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Na czym polega pierwiastkowanie
JK
-
mdd
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
Re: Na czym polega pierwiastkowanie
Odpowiednie równania uogólnionego algorytmu CORDIC pozwalające obliczać wartość pierwiastka kwadratowego liczby \(\displaystyle{ a}\) otrzymać można obserwując dyskretne ruchy "punktu" położonego na hiperboli o równaniu: \(\displaystyle{ x^{2}-y^{2}=a}\).
Zabawę zaczynamy od położenia początkowego: \(\displaystyle{ \left( a+\frac{1}{4}, a-\frac{1}{4}\right)}\)
Następne położenia uzyskujemy obracając wektor wodzący "punktu" o pewne kąty, takie że wektor ten będzie się starał "kłaść" na osi OX, a koniec tego wektora będzie dążył do punktu \(\displaystyle{ \left( \sqrt{a}, 0\right) }\), oraz takie, że kolejne wartości tych kątów będą zapewniały zbieżność procesu. Okazuje się, że wartości kątów, dla których wartość funkcji tangens daje się wyrazić jako \(\displaystyle{ 2^{-i}}\) (liczbą naturalną \(\displaystyle{ i}\) numerujemy kolejne położenia wektora wodzącego) spełniają takie warunki.
\(\displaystyle{ y_{0}=a-1/4
\\
x_{0}=a+1/4
\\
d_{i}=\left\{\begin{matrix}
1 \quad \text{dla} \quad y_{i}< 0
\\
-1 \quad \text{dla} \quad y_{i}\geqslant 0
\end{matrix}\right.
\\
x_{i+1}=x_{i}+d_{i} \cdot \ 2^{-i} \cdot \ y_{i}
\\
y_{i+1}=y_{i}+d_{i} \cdot \ 2^{-i} \cdot \ x_{i}
\\
K_{i+1}=K_{i} \cdot \sqrt{1-2^{-2i}}}\)
Kilka uwag.
To nie punkt o współrzędnych \(\displaystyle{ \left( x_{i},y_{i}\right) }\) leży na wcześniej wspomnianej hiperboli, a punkt o współrzędnych \(\displaystyle{ \left( \frac{x_{i}}{K_{i}},\frac{y_{i}}{K_{i}}\right)}\).
Wartości \(\displaystyle{ K_{i}}\) nie liczy się za każdym razem, a jednorazowo liczy się ją dla odpowiednio dużego \(\displaystyle{ i}\) i zapamiętuje się wartość tej liczby (a właściwie jej odwrotność), tak żeby można się było do niej odwołać za każdym razem, kiedy zajdzie taka potrzeba. Odpowiednie wartości \(\displaystyle{ K_{i}}\) pozwalają, aby koniec wektora wodzącego poruszał się po naszej hiperboli.
Zakres wartości liczb pierwiastkowanych, dla którego opisany proces jest zbieżny, jest dość mały, dlatego przed pierwiastkowaniem wykonuje się proces "normalizacji" tej liczby, co opisane jest np. tutaj:
Zalety tej metody obliczania pierwiastka widać dopiero jeśli wykonujemy rachunki na liczbach zapisanych w systemie dwójkowym, wtedy mnożenie przez \(\displaystyle{ 2^{-i}}\) uzyskujemy przez przesunięcie przecinka.
Jeszcze raz polecam lekturę:
Wpis wykonany w ramach procesu samokształcenia. Nawet na stare lata warto się czegoś nowego nauczyć
Zabawę zaczynamy od położenia początkowego: \(\displaystyle{ \left( a+\frac{1}{4}, a-\frac{1}{4}\right)}\)
Następne położenia uzyskujemy obracając wektor wodzący "punktu" o pewne kąty, takie że wektor ten będzie się starał "kłaść" na osi OX, a koniec tego wektora będzie dążył do punktu \(\displaystyle{ \left( \sqrt{a}, 0\right) }\), oraz takie, że kolejne wartości tych kątów będą zapewniały zbieżność procesu. Okazuje się, że wartości kątów, dla których wartość funkcji tangens daje się wyrazić jako \(\displaystyle{ 2^{-i}}\) (liczbą naturalną \(\displaystyle{ i}\) numerujemy kolejne położenia wektora wodzącego) spełniają takie warunki.
\(\displaystyle{ y_{0}=a-1/4
\\
x_{0}=a+1/4
\\
d_{i}=\left\{\begin{matrix}
1 \quad \text{dla} \quad y_{i}< 0
\\
-1 \quad \text{dla} \quad y_{i}\geqslant 0
\end{matrix}\right.
\\
x_{i+1}=x_{i}+d_{i} \cdot \ 2^{-i} \cdot \ y_{i}
\\
y_{i+1}=y_{i}+d_{i} \cdot \ 2^{-i} \cdot \ x_{i}
\\
K_{i+1}=K_{i} \cdot \sqrt{1-2^{-2i}}}\)
Kilka uwag.
To nie punkt o współrzędnych \(\displaystyle{ \left( x_{i},y_{i}\right) }\) leży na wcześniej wspomnianej hiperboli, a punkt o współrzędnych \(\displaystyle{ \left( \frac{x_{i}}{K_{i}},\frac{y_{i}}{K_{i}}\right)}\).
Wartości \(\displaystyle{ K_{i}}\) nie liczy się za każdym razem, a jednorazowo liczy się ją dla odpowiednio dużego \(\displaystyle{ i}\) i zapamiętuje się wartość tej liczby (a właściwie jej odwrotność), tak żeby można się było do niej odwołać za każdym razem, kiedy zajdzie taka potrzeba. Odpowiednie wartości \(\displaystyle{ K_{i}}\) pozwalają, aby koniec wektora wodzącego poruszał się po naszej hiperboli.
Zakres wartości liczb pierwiastkowanych, dla którego opisany proces jest zbieżny, jest dość mały, dlatego przed pierwiastkowaniem wykonuje się proces "normalizacji" tej liczby, co opisane jest np. tutaj:
Kod: Zaznacz cały
https://www.mathworks.com/help/fixedpoint/ug/compute-square-root-using-cordic.html;jsessionid=7e97f28a972b059d5240295b2bd1#d122e84799Zalety tej metody obliczania pierwiastka widać dopiero jeśli wykonujemy rachunki na liczbach zapisanych w systemie dwójkowym, wtedy mnożenie przez \(\displaystyle{ 2^{-i}}\) uzyskujemy przez przesunięcie przecinka.
Jeszcze raz polecam lekturę:
Kod: Zaznacz cały
https://repositories.lib.utexas.edu/bitstream/handle/2152/1472/arbaughj20424.pdfWpis wykonany w ramach procesu samokształcenia. Nawet na stare lata warto się czegoś nowego nauczyć