Очень нужна помощь в оптимизации алгоритма извлечения квадратного корня Опции

[Rostislav]

Ребята, всем привет! Помогите, пожалуйста оптимизировать алгоритм извлечения корня. А то что-то до фига получается циклов вычисления. Заранее огромное спасибо всем откликнувшимся!

Алгоритм простой, основан на методе последовательного приближения. Собственно вот он (без шелухи):

bprev:=bprev div 2;
if (b+bprev)*(b+bprev) > a then
b:=b-bprev
else
if (b+bprev)*(b+bprev) < a then
b:=b+bprev
else
выход;
повтор цикла....

Полный текст:

a:word;
b:word;
bprev:word;
cnt:word;

a:=strtoint(edit1.Text); // подкоренное выражение
b:=a; // в b хранится результат
bprev:=a;
cnt:=0;
while 1=1 do begin
cnt:=cnt+1; // Счетчик циклов
bprev:=bprev div 2;
if bprev=0 then begin
bprev:=1;
if ((b+1)*(b+1) > a) and ((b+0)*(b+0) < a) then break;
end;
if (b+bprev)*(b+bprev) > a then
b:=b-bprev
else
if (b+bprev)*(b+bprev) < a then
b:=b+bprev
else
break;
end;
b:=b+bprev;
Form1.Caption:='результат: '+inttostr(b)+' циклов: '+inttostr(cnt);

Результаты замера следующие:
sqr (1) - 2 цикла;
sqr (10) - 5 циклов;
sqr (100) - 5 циклов;
sqr (1000) - 13 циклов;
sqr (10000) - 38 циклов;
sqr (32000) - 73 цикла;
...

Алгоритм предложенный alexeyv:

i:=1; // результат в i
b:=1;
a:=10000; // подкоренное выражение
while 1=1 do begin
if (b > a) or (b = a) then break;
b:=b+2;
a:=a-b;
i:=i+1;
end;
caption:=inttostr(i);

sqr (10000) - 100 циклов.

Сообщение отредактировал Rostislav - Dec 5 2012, 07:35

[анатолий]

Вот функция корня по алгоритму CORDIC

Код

function SQROOT(x1:integer) return integer is
        variable m,n,i, a, x,y,b: INTEGER;      
        constant bn:integer:=28;
            begin                
        y:=x1;     x:=x1;
        m:=1;    n:=bn/2;
        L1: for i in 1 to n loop
            a:=4*x;     
            exit L1 when a>=2**(bn);    
            y:=2*y;    x:=a;
        end loop;    
        L2:for i in 1 to n-1 loop
            b:=x+x/2**m;
            a:=b+b/2**m;
            if a<2**(bn) then
                x:=a;
                y:=y+y/2**m;
            end if;    
            m:=m+1;
        end loop;        
        return y/(2**n);
    end;

[Rostislav]

Вот функция корня по алгоритму CORDIC

Код

....
    b:=x+x/2**m;
....

Анатолий, спасибо огромное! Изучаю алогоритмик. Только вот я не понял, что означает в программе '**'? Степень числа?

[анатолий]

что означает в программе '**'? Степень числа?

Это степень числа, язык VHDL. Cинтезируется в логическую схему.