alexsl 0 7 мая, 2008 Опубликовано 7 мая, 2008 (изменено) · Жалоба Добрый день. При построении FSK демодулятора встретился с проблемой. Очень долго вычисляется квадратный корень. Пробовал аппаратную реализацию, как самую быструю: unsigned int sqrt_user(unsigned long x){ unsigned long m = 0x40000000; unsigned long y = 0; unsigned long b; while(m){ b = y | m; y >>= 1; if( x >= b ){ x -= b; y |= m; } m >>= 2; } return y; } Получилось 400 циклов. Пробовал Cordic алгоритм. Еще больше получается. Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов? Изменено 7 мая, 2008 пользователем alexsl Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ATname 0 7 мая, 2008 Опубликовано 7 мая, 2008 · Жалоба Добрый день. При построении FSK демодулятора встретился с проблемой. Очень долго вычисляется квадратный корень. Пробовал аппаратную реализацию, как самую быструю: unsigned int sqrt_user(unsigned long x){ unsigned long m = 0x40000000; unsigned long y = 0; unsigned long b; while(m){ b = y | m; y >>= 1; if( x >= b ){ x -= b; y |= m; } m >>= 2; } return y; } Получилось 400 циклов. Пробовал Cordic алгоритм. Еще больше получается. Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов? Есть такая "штука", называется сплайн функция. Вычисление квадратного корня апроксимируется полиномом нужного (в зависимости от точности рассчета) порядка. Обычно третьего за глаза хватает. Формула на работе валяется... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alexsl 0 8 мая, 2008 Опубликовано 8 мая, 2008 · Жалоба Есть такая "штука", называется сплайн функция. Вычисление квадратного корня апроксимируется полиномом нужного (в зависимости от точности рассчета) порядка. Обычно третьего за глаза хватает. Формула на работе валяется... Поделитесь пожалуйста. Заранее благодарен. :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
1S49 0 8 мая, 2008 Опубликовано 8 мая, 2008 · Жалоба Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов? Есть на техасщине такая IQmath, дык там квадратный корень за 63 цикла с точностью 29 бит и размером программы 66 слов: Texas Instruments TMS320C28x IQmath Library is collection of highly optimized and high precision mathematical Function Library for C/C++ programmers to seamlessly port the floatingpoint algorithm into fixed point code on TMS320C28x devices. These routines are typically used in computationally intensive real-time applications where optimal execution speed & high accuracy is critical. By using these routines you can achieve execution speeds considerable faster than equivalent code written in standard ANSI C language. In addition, by providing readyto- use high precision functions, TI IQmath library can shorten significantly your DSP application development time. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Гость TSerg 8 мая, 2008 Опубликовано 8 мая, 2008 · Жалоба Число итераций около N = Ln( Value) Можно еще снизить число итераций подбором начального значения div_ function sqrt_newton(value: Int64; var cnt: integer): integer; var _div: int64; begin cnt := 0; Result := 0; if (value <= 0) then Exit; Result := value; _div := value; while (True) do begin Inc(cnt); _div := (value div _div + _div) div 2; if (Result > _div) then Result := _div else break; end; end; Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alexsl 0 9 мая, 2008 Опубликовано 9 мая, 2008 · Жалоба Есть на техасщине такая IQmath, дык там квадратный корень за 63 цикла с точностью 29 бит и размером программы 66 слов: Спасибо :) Буду разбиратся. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
1S49 0 9 мая, 2008 Опубликовано 9 мая, 2008 · Жалоба Спасибо :) Буду разбиратся. Пожалуйста. Но главным образом благодарите Соединенные Штаты Америки, породившие фирму TI , которая собрала неплохих программистов Америки, Индии, Китая и России и написавших эту библиотеку. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Alex11 5 9 мая, 2008 Опубликовано 9 мая, 2008 · Жалоба Вот еще один вариант, целочисленный корень из лонга. Оптимизирован, правда, под 55хх серию. Там занимает 82 клока. В файлике код на .с для понимания алгоритма, .s55 - оптимизированный. SQRT.ZIP Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DS 0 10 мая, 2008 Опубликовано 10 мая, 2008 · Жалоба Странно, у меня вычисление на ADSP-21 занимает 23 такта при аппроксимации 5 порядком вместе с нормализацией/денормализацией. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
nicks80 0 14 июня, 2008 Опубликовано 14 июня, 2008 (изменено) · Жалоба Странно, у меня вычисление на ADSP-21 занимает 23 такта при аппроксимации 5 порядком вместе с нормализацией/денормализацией. самое быстрое что пробовал. unsigned int isqrt(unsigned int x) --- этот тест не прошёл гдето опечатка { unsigned int s,g0,g1; if(x<=4224) if(x<=24) if(x<=3) return (x+3)>>2; else if(x<=8) return 2; else return (x>>4)+3; else if(x<=288) if(x<=80) s=3; else s=4; else if (x<=1088) x=5; else s=6; else if(x<=1024*1025-1) if(x<=257*257-1) if(x<=129*129-1) s=7; else s=8; else if(x<=513*513-1) s=9;else s=10; else if (x<= 4097*4097 -1) if (x<=2049*2049 -1) s=11;else s=12; else if(x<=16385*16385-1) if(x<=8193*8193-1) s=13; else s= 14; else if(x<=32769*32769-1)s=15;else s=16; g0=1<<s; g1 = (g0+(x>>s))>>1; while(g1<g0) { g0=g1; g1=(g0+(x/g0))>>1; }; return g0; } Пожалуйста. Но главным образом благодарите Соединенные Штаты Америки, породившие фирму TI , которая собрала неплохих программистов Америки, Индии, Китая и России и написавших эту библиотеку. Да вот это на арме летает просто!!! проверено в сравнении с sqrt на округление до 1650503060 все ок. unsigned int isqrt2(unsigned long src) - здесь время константное. самый быстрый что я пробовал метод { unsigned long wrk; unsigned int dst; int i; dst = 0x8000; wrk = 0x8000; for(i=0; i<16; i++) { if((long)dst*dst>src) dst &= ~wrk; wrk >>= 1; dst |= wrk; } return dst; } Изменено 14 июня, 2008 пользователем nicks80 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ATname 0 17 июня, 2008 Опубликовано 17 июня, 2008 · Жалоба Поделитесь пожалуйста. Заранее благодарен. :) Корень из суммы квадратов х1 и х2 апроксимация четвертого порядка, точность результата не хуже 0.007%. A*t^4 + D*t^3 + C*t^2 + D*t + E, где А = -0.011805615, В = -0.105819461, С = 0.535740269, D = -0.004076434, E = 1.000070802 t отношение х2 к х1 если х1>х2 или наоборот, т.е. t должно быть меньше единицы. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
sigmaN 0 25 июня, 2008 Опубликовано 25 июня, 2008 · Жалоба Слушайте, а как с этим делом на процах с FPU(TMS320F28335)? IQMath она ведь только для фиксед поинт процов? у FPU серии там должно быть всё в RTS Library уже оптимизировано, да? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
1S49 0 25 июня, 2008 Опубликовано 25 июня, 2008 · Жалоба Слушайте, а как с этим делом на процах с FPU(TMS320F28335)? IQMath она ведь только для фиксед поинт процов? у FPU серии там должно быть всё в RTS Library уже оптимизировано, да? Оптимизировано. Но всегда хочется еще быстрее. sprc664 –это про RTS, sprc624 – это про “не ANSI, но быстро”. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
sigmaN 0 27 июня, 2008 Опубликовано 27 июня, 2008 · Жалоба Спасибо! sprc624 у меня есть, а вот sprc664 может быть очень полезен in general, так сказать )) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SALKA 0 23 июля, 2008 Опубликовано 23 июля, 2008 · Жалоба а алгоритм извлечения корня из fixed-point произвольного формата, кто нибудь встречал? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться