[Rostislav78 0]

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

 

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

 

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 циклов.

Изменено 5 декабря, 2012 пользователем Rostislav

[alexeyv 0]

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

 

Для квадратов чисел верны следующие равенства:

1 = 1^2

1+3 = 2^2

1+3+5 = 3^2

и так далее.

 

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

Выполнено 3 действия, квадратный корень числа 9 равен 3.

 

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

 

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

[Rostislav78 0]

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

повтор цикла

 

Так?

Изменено 5 декабря, 2012 пользователем Rostislav

[Tanya 4]

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

Что Вас так забавляет?

Немного школьной арифметики...

Сумма арифметической прогрессии дает - сумма N нечетных чисел в точности равна N в квадрате.

Следующий разряд (после точки) можно вычислить как (половина остатка)/N.

[Rostislav78 0]

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

 

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

 

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);

Изменено 5 декабря, 2012 пользователем Rostislav

[MrYuran 17]

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

 

........b=b+(b+2)

просто b=b+2

a=a-b

 

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

[Rostislav78 0]

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

 

........b=b+(b+2)

просто b=b+2

a=a-b

 

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

 

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

 

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

Изменено 5 декабря, 2012 пользователем Rostislav

[skyvmicro 0]

 

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

Где ее лучше расположить это зависит от ресурсов CPU.

 

[Rostislav78 0]

Я использовал просто таблицу

 

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

[Lmx2315 3]

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

 

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

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

 

 

 

 

 

[MrYuran 17]

bibliofond_556017.rtf

 

Можно скомбинировать.

Таблицу для грубого определения и дальше уточнять.

[Rostislav78 0]

Можно скомбинировать.

Таблицу для грубого определения и дальше уточнять.

 

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

[sysel 0]

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

// Вычисление квадратного корня из 32х битного числа
int16 isqrt32 (int32 from){
  register int32 mask=0x40000000;
  register int32 sqr=0;
  do {
    register int32 temp = sqr | mask;
    sqr >>= 1;
    if (temp <= from){
      sqr |= mask;
      from -= temp;
    };
  } while (mask >>= 2);
  if (sqr < from) sqr++;
  return ((int16)sqr);
}

[skyvmicro 0]

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

 

Так и есть.

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

чтению ячейки массива.

[aser 0]

Вот функция корня по алгоритму 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;