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

[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

[alexeyv]

Если нужна только целая часть квадратного корня, то можно воспользоваться другим алгоритмом:

Для квадратов чисел верны следующие равенства:
1 = 1^2
1+3 = 2^2
1+3+5 = 3^2
и так далее.

То есть, узнать целую часть квадратного корня числа можно, вычитая из него все нечётные числа по порядку, пока остаток не станет меньше следующего вычитаемого числа или равен нулю, и посчитав количество выполненных действий. Например, так:
Выполнено 3 действия, квадратный корень числа 9 равен 3.

Недостатком такого способа является то, что если извлекаемый корень не является целым числом, то можно узнать только его целую часть, но не точнее. В то же время такой способ вполне доступен детям, решающим простейшие математические задачи, требующие извлечения квадратного корня.

Циклов конечно будет больше, зато время их выполнения гораздо меньше

[Rostislav]

1 = 1^2
1+3 = 2^2
1+3+5 = 3^2
и так далее.

Забавный алгоритм))

Т.е. если я Вас правильно понял, то программа должна выглядеть так:

a=подкоренное выражение
b=1
i=1

цикл
если b > a или b = a то
....выход (результат в i)
иначе
....b=b+(b+2)
....i=i+1
повтор цикла

Так?

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

[Tanya]

Забавный алгоритм))

Что Вас так забавляет?
Немного школьной арифметики...
Сумма арифметической прогрессии дает - сумма N нечетных чисел в точности равна N в квадрате.
Следующий разряд (после точки) можно вычислить как (половина остатка)/N.