ATNEL tech-forum
https://forum.atnel.pl/

Obliczanie pierwiastka kwadratowego dla Fixed-point math
https://forum.atnel.pl/topic22637.html
Strona 1 z 1

Autor:  abel11 [ 25 paź 2019, o 17:49 ]
Tytuł:  Obliczanie pierwiastka kwadratowego dla Fixed-point math

Witam

Czy ktoś z forumowiczów mierzył się kiedyś z problemem obliczania pierwiastka kwadratowego dla obliczeń stałoprzecinkowych (fractionali) ?
Potrzebne mi jest obliczanie pierwiastka z liczby Q9.31 optymalnie by było zrobić to bez dzielenia albo z możliwie małą liczbą dzieleń, niestety znany mi algorytm Newtona-Raphsona wymaga jednego dzielenia na każdą cyfrę wyniku. Dzielenie w moim uC wymaga 18 cykli zegara więc dla 40 znaków otrzymuje 720 instrukcji na same operacje dzielenia dla liczb 16 bitowych, a pierwiastkować będę liczby 40 bitowe więc wygląda to na całą wieczność i jeszcze trochę.
Myślałem o algorytmie cyfra po cyfrze (digit-by-digit), tyle że nie chciał bym zabrnąć w jakąś ślepą uliczkę, może ktoś już przerabiał ten problem?

Autor:  abel11 [ 26 paź 2019, o 07:30 ]
Tytuł:  Re: Obliczanie pierwiastka kwadratowego dla Fixed-point math

Kolacz napisał(a):
Do tego jest stworzone FPU.

FPU jest stworzone do obliczeń zmiennoprzecinkowych (floating) point, mi potrzebne są obliczenia stałoprzecinkowe (fixed point).
Większość dsp pracuje na fixed point, idea polega na wykonywaniu działań na liczbach niecałkowitych, zazwyczaj na wartościach znormalizowanych. Dlatego binarnie Q0.15 i int są nie do odróżnienia, po prostu przecinek jest domniemany np. zaraz za MSB , czyli de facto wykonuje się obliczenia na int tyle, że liczby są inaczej interpretowane. Rezultatem jest tańszy procesor i niewielki spadek dokładności obliczeń przy dużej ich szybkości. Najlepsze w tym jest to, że nawet 8 bitowiec może tu dość wydajnie zasuwać z obliczeniami dla wartości znormalizowanych.

Autor:  micky [ 26 paź 2019, o 09:40 ]
Tytuł:  Re: Obliczanie pierwiastka kwadratowego dla Fixed-point math

Jaki masz zakres liczb, które chcesz pierwiastkowac i z jaką rozdzielczością i dokładnością? Może wrzucenie wyników do tablicy by Ci pomogło?

Autor:  abel11 [ 26 paź 2019, o 10:36 ]
Tytuł:  Re: Obliczanie pierwiastka kwadratowego dla Fixed-point math

Pierwiastkowane liczby będą w zakresie od 0 do 0.999969482, wynik powinien zachować minimalną rozdzielczość 12b czyli krok równy 0.0000244140625 i 4096 słów w pamięci na tablice. Niestety, aż tyle miejsca nie mam w pamięci, a dołączania zewnętrznej wole uniknąć.
Może idąc Twoim tropem, spróbuję stablicować wynik zgrubnie, powiedzmy tablice 256/512 bitową co da krok 0.00390625 lub 0.001953425 i tą wartość wykorzystam jako początkową w obliczaniu pierwiastka, co powinno pozwolić na zmniejszenie liczby iteracji.
Dzięki za podsunięcie pomysłu!

Autor:  micky [ 26 paź 2019, o 10:39 ]
Tytuł:  Re: Obliczanie pierwiastka kwadratowego dla Fixed-point math

Proszę uprzejmie :) Możesz zrobić mniej kroków a pomiędzy krokami aproksymować żeby przyspieszyć obliczanie.

Strona 1 z 1 Strefa czasowa: UTC + 1
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/