[Rostislav78 0]

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

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

 

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

[Гость TSerg]

function intSqrt_(Val : Longword) : Longword;
var bitSqr : Longword;
begin
bitSqr := $40000000;
Result := 0;

While bitSqr <> 0 do
  begin
   if (Val >= bitSqr + Result) then begin
       Dec(Val, bitSqr + Result);
       Result := (Result shr 1) or bitSqr;
     end
   else
       Result := Result shr 1;
   bitSqr := bitSqr shr 2;
  end;
end;

 

Если сравнивать с уже упомянутой медленной функцией:

function Q(x: Longword): Longword;
var k: Longword;
begin
  Result := 0;
  k := 1;
  while (k <= x) do begin
    Dec(x,k);
    Inc(k,2);
    Inc(Result);
  end;
end;

 

то разница на писюках более чем в 20 раз лучше.

 

[akorud 0]

Есть возможность использовать floating-point? Может известный алгоритм быстрого инверсного корня из Quake III http://en.wikipedia.org/wiki/Fast_inverse_square_root и факт что sqrt(x) = x/sqrt(x) -> sqrt(x) = x * rsqrt(x)

[aser 0]

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

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

[VitekSVM 0]

http://algolist.manual.ru/maths/count_fast/index.php

[ASN 0]

Rostislav

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

На какой целевой платформе выполняется прикладная программа?

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

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

[Rostislav78 0]

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

 

Уважаемый 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!!!!!!

 

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

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

[beaRTS 0]

  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

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

// конец

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

[Rostislav78 0]

temp := b + 1 shl n;

if (temp * temp < a) or //А ТАК НЕЛЬЗЯ????

 

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

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

[beaRTS 0]

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

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

[Rostislav78 0]

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

 

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

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

[blackfin 16]

Сто раз уже обсуждали: ReAl.

[Rostislav78 0]

Сто раз уже обсуждали: ReAl.

 

Да, похоже, я не открыл Америку))))))))

[beaRTS 0]

Сто раз уже обсуждали:

повторение - мать учения.. к тому же поиск хренова-то работает на форуме. я эту ссылку первый раз вижу. Так что спасибо за "пароли, явки, адреса").

[Rostislav78 0]

...я эту ссылку первый раз вижу...

 

Присоединяюсь! К тому же, может быть "подует свежий ветер"!)))