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

[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

[ASN]

Rostislav
С какой практической точностью нужно вычислять выражение ?
На какой целевой платформе выполняется прикладная программа?
Если вычислительная система поддерживает вычисления с плавающей точкой , то лучше воспользоваться арифметическим сопроцессором (типа сопроцессора для i386) или специальными командами самого процессора (как в TMS320C55).
Если требуется целочисленная арифметика, то проще и быстрее заранее вычисленной таблицы в памяти что-то предложить сложно.

[Rostislav]

С какой практической точностью нужно вычислять выражение ?

Уважаемый ASN! Мне придумалась еще одна идея. Более простого алгоритма я придумать не смог (кстати, не понятно, почему этот вариант мне раньше не пришел в голову). Но все же отвечу на Ваши вопросы))

Меня интересует целочисленный результат.

На какой целевой платформе выполняется прикладная программа?
Если вычислительная система поддерживает вычисления с плавающей точкой , то лучше воспользоваться арифметическим сопроцессором (типа сопроцессора для i386) или специальными командами самого процессора (как в TMS320C55).

Меня интересовал вариант, который мог бы выполнятся на микроконтроллерах с простой архитектурой (типа PIC12).

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

Таблицы сразу не понравились. Для них нужна память.

----

Итак, мое заднее)))) предложение:

Код

  a : Word;  // подкоренное выражение
  b : Word;  // результат
  n : Byte;

  a := 121;
  b := 0;

  // начало
  for n := 15 downto 0 do   // Счет от 15 до 0   // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1)
   begin
     if ((b + 1 shl n) * (b + 1 shl n) < a) or         // shl - побитовый сдвиг влево на n бит
        ((b + 1 shl n) * (b + 1 shl n) = a) then
      begin
        b := b + 1 shl n;
      end;
   end;
  // конец

  Form1.Caption := IntToStr (b);    // b = 11

  Циклов для 16-ти разрядного числа 16!!!
         для 32-х  разрядного числа 32!!!!!!

По-моему, получилось красиво))) Операции умножения можно заменить на бинарное сложение столбиком с предварительным смещением бит влево. Если более оптимального алгоритма наука)) еще не придумала, то тему можно закрывать. Теперь возьмусь за вычисление тригонометрических функций)))) Всем спасибо!!!!!

Сообщение отредактировал Rostislav - Dec 20 2012, 21:57

[beaRTS]

[code] a : Word; // подкоренное выражение
b : Word; // результат
n : Byte;

a := 121;
b := 0;

// начало
for n := 15 downto 0 do // Счет от 15 до 0 // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1)
begin
if ((b + 1 shl n) * (b + 1 shl n) < a) or // shl - побитовый сдвиг влево на n бит
((b + 1 shl n) * (b + 1 shl n) = a) then
begin
b := b + 1 shl n;
end;
end;
// конец

Form1.Caption := IntToStr (; // b = 11
[code]

По-моему, получилось красиво)))

Может, я чего-то не понимаю... но в цикле for явно не красота красуется. Вы 5 раз вычисляете одно и тоже выражение b + 1 shl n !! Дык, зачем это делать?. один раз вычислите, присвойте результат какой-нибудь временной переменной и таскайте ее за собой везде. что-то типа:

for n := 15 downto 0 do // Счет от 15 до 0 // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1)
begin
temp := b + 1 shl n;
if (temp * temp < a) or // А ТАК НЕЛЬЗЯ???? (temp * temp <= a )
(temp * temp = a) then
begin
b := temp
end;
end;
// конец

Сообщение отредактировал beaRTS - Dec 21 2012, 02:10

[Rostislav]

temp := b + 1 shl n;
if (temp * temp < a) or //А ТАК НЕЛЬЗЯ????

Да нее, Вы все правильно понимаете)))))))) Просто я не стал делать очевидное, то, что лежит на поверхности. Ну конечно же, мне известны некоторые трюки программирования. Умножение на 2 (и деление), например, легко можно заменить на побитовый сдвиг и т.п. А Ваш вариант оптимизации сделает, скорее всего, компилятор. Меня (и не только меня, наверное) больше всего интересовала суть. Суть я и изложил. Поэтому, спасибо Вам за участие и с наступающим Новым Годом!!!!!!!)))))))))

Сообщение отредактировал Rostislav - Dec 21 2012, 05:58

[beaRTS]

Да нее, Вы все правильно понимаете)))))))) Просто я не стал делать очевидное, то, что лежит на поверхности. Ну конечно же, мне известны некоторые трюки программирования. Умножение на 2 (и деление), например, легко можно заменить на побитовый сдвиг и т.п. А Ваш вариант оптимизации сделает, скорее всего, компилятор. Меня (и не только меня, наверное) больше всего интересовала суть. Суть я и изложил. Поэтому, спасибо Вам за участие и с наступающим Новым Годом!!!!!!!)))))))))

а, ну тогда добро, добро. я тут тоже начал над своим вариантом извлечения корня биться. Ну как своим - комбинирую два метода. посмотрим что получится

[Rostislav]

а, ну тогда добро, добро. я тут тоже начал над своим вариантом извлечения корня биться. Ну как своим - комбинирую два метода. посмотрим что получится

Здорово!!!))) Выкладывайте Ваши идеи!!!!!! Очень интересно!!!)))

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