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

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

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

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

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

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

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

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

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

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

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

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

Так?

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

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

Что забавляет? Все)) Магия чисел в особенности))

Проверил работу алгоритма:

sqr (10000) = 13
Но sqr (9) = 3 !!!!!

Где-то ошибка(

i:=1;
b:=1;
a:=10000;
while 1=1 do begin
if (b > a) or (b = a) then break;
b:=b+(b+2);
i:=i+1;
end;
caption:=inttostr(i);

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

просто b=b+2
a=a-b

(эх и ужос этот ваш паскаль.. да ещё без тега code)

Кстати, детская арифметика заканчивается начиная с sqr (36). Результат 5!



Ага, спасибо, все заработало! В итоге sqr (10000) вычисляется за 100 шагов. Оптимизации не получилось. Можно попробовать изменить его под переменную базу. Сейчас мы прибавляем 2, а можно начинать, например, с 16 последовательно уменьшая это число в двое. Если конечно это сработает. Буду думать...



Ну да, вот так и мучаюсь всю жизнь!))

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

Я использовал просто таблицу, которую предварительно вычислял.
Где ее лучше расположить это зависит от ресурсов CPU.

А Вы можете привести пример? Мне нужно как-то оценить эффективность такого подхода. Сейчас я не могу сделать никаких выводов. Я знаю, что существуют табличные вычисления, но все нужно проверять в живую)

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

 bibliofond_556017.rtf ( 117.89 килобайт ) Кол-во скачиваний: 1040


Можно скомбинировать.
Таблицу для грубого определения и дальше уточнять.

Спасибо! Изучаю Вавилонский способ. Оказывается древние не только воевать умели) Я пока с комбинированием не хочу связываться. Нужно выжать максимум из того, что сейчас наработано. Мне кажется, что потенциал есть у обоих алгоритмов. А о комбинировании различных методов мысля уже проскальзывала, но хочется сделать монолитно-красиво)

Не знаю, как называется метод, но пашет:

Так и есть.
В этом случае операция вычисления (в принципе чего угодно) сводится к
чтению ячейки массива.

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