[alexsl 0]

Добрый день. При построении 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]

Добрый день. При построении 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]

Есть такая "штука", называется сплайн функция. Вычисление квадратного корня апроксимируется полиномом нужного (в зависимости от точности рассчета) порядка. Обычно третьего за глаза хватает. Формула на работе валяется...

Поделитесь пожалуйста. Заранее благодарен. :)

[1S49 0]

Может быть есть у кого реализация, позволяющая уложится в 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]

 

Число итераций около 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]

Есть на техасщине такая IQmath, дык там квадратный корень за 63 цикла с точностью 29 бит и размером программы 66 слов:

Спасибо :) Буду разбиратся.

[1S49 0]

Спасибо :) Буду разбиратся.

Пожалуйста. Но главным образом благодарите Соединенные Штаты Америки, породившие фирму TI , которая собрала неплохих программистов Америки, Индии, Китая и России и написавших эту библиотеку.

[Alex11 3]

Вот еще один вариант, целочисленный корень из лонга. Оптимизирован, правда, под 55хх серию. Там занимает 82 клока. В файлике код на .с для понимания алгоритма, .s55 - оптимизированный. SQRT.ZIP

[DS 0]

Странно, у меня вычисление на ADSP-21 занимает 23 такта при аппроксимации 5 порядком вместе с нормализацией/денормализацией.

[nicks80 0]

Странно, у меня вычисление на 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]

Поделитесь пожалуйста. Заранее благодарен. :)

Корень из суммы квадратов х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]

Слушайте, а как с этим делом на процах с FPU(TMS320F28335)?

IQMath она ведь только для фиксед поинт процов?

у FPU серии там должно быть всё в RTS Library уже оптимизировано, да?

[1S49 0]

Слушайте, а как с этим делом на процах с FPU(TMS320F28335)?

IQMath она ведь только для фиксед поинт процов?

у FPU серии там должно быть всё в RTS Library уже оптимизировано, да?

 

Оптимизировано. Но всегда хочется еще быстрее. sprc664 –это про RTS, sprc624 – это про “не ANSI, но быстро”.

[sigmaN 0]

Спасибо! sprc624 у меня есть, а вот sprc664 может быть очень полезен in general, так сказать ))

[SALKA 0]

а алгоритм извлечения корня из fixed-point произвольного формата, кто нибудь встречал?