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?

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.

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?

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!

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