алгоритмы извлечения квадратного корня Опции

[vovan1313]

Подскажите пожалуйста ламеру какой-нибудь из алгоритмов извлечения квадратного корня (еще лучше привести соответствующий код на VHDL).

Сообщение отредактировал vovan1313 - Oct 13 2007, 07:12

[petrov]

http://www.google.ru/search?complete=1&...1%D0%BA&lr=

[PSP]

Сам я VHDL не использую, но вот есть исходник из какой-то статьи в архивах.


--^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- FILE: SQROOT.VHD
-- PROJECT: Square Root Unit
-- AUTHOR: Anatoli Sergyienko
-- Email: aser@comsys.ntu-kpi.kiev.ua
--
-- FUNCTION: - calculating the square root function
-- from the positive integer data.
-- CONSTRAINTS: the input data bit number is less than
-- 2**(bit_num), where bit_num<28 is a generic value,
-- the output data bit number is less than 2**(bit_num/2),
-- respectively. Maximum error is equal to 1 l.s.b.
--^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
library IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_ARITH.all ;

entity SQRT is

generic (bit_num: integer:=16);
port (
ARGUM: in INTEGER range 0 to 2**(bit_num)-1;
SQRT: out INTEGER range 0 to 2**(bit_num/2)-1;
RESET: in STD_LOGIC;
CLK: in STD_LOGIC
);
end SQRT;


architecture SQRT of SQRT is
signal SQRT2 : INTEGER range 0 to 2**(bit_num/2)-1;
signal arg: integer range 0 to 2**(bit_num)-1;
function SQROOT(x1:integer; bn:integer) return integer is
variable m,n,i : INTEGER range 0 to 15;
variable a, b, x : INTEGER range 0 to 2**(bn+2)-1;
variable y : INTEGER range 0 to 2**(bn+1)-1;
begin
y:=x1; x:=x1;
m:=0; n:=bn/2;
ROOT: for i in 1 to n loop
a:=2**2*x;
exit ROOT when a>=2**(bn+1);
y:=2*y; x:=a;
end loop;
ROOT2:for i in 1 to n-1 loop
m:=m+1;
b:=x+x/2**m;
a:=b+b/2**m;
if a>=2**(bn+1) then
x:=x; y:=y;
else
x:=a; y:=y+y/2**m;
end if;
end loop;
y:=y+2**(n-1);
return y/2**n;
end;

begin
process(RESET,CLK,ARGUM)
begin
if RESET ='1' then
ARG<=0;
SQRT<=0;
elsif CLK='1' and CLK'event then
ARG<=ARGUM;
SQRT<= SQROOT(ARG, bit_num);
end if;
end process;
end SQRT;

[Doka]

от точности всё зависит, и от того сколько тактов вы можете себе позволить..
cordic наверное посмотреть можно (кажется он умел извлекать корень)

а если вам для оценки мощности квадратурного сигнала, то можно так:
SQRT(I^2 + Q^2) ~ 0.828427*(I+Q) - 0.3431452*I*Q

[Alex255]

Подскажите пожалуйста ламеру какой-нибудь из алгоритмов извлечения квадратного корня (еще лучше привести соответствующий код на VHDL).

Когда то баловался...
Xn+1=Xn+Y/Xn; Y - это то, из чего корень извлекают. X0 - скажем Y/2.

[SergVZ]

Xn+1=(Xn+Y/Xn)/2; Y - это то, из чего корень извлекают. X0 - скажем Y/2.
Формулу отAlex255 чуток поправил.

[vovan1313]

Xn+1=(Xn+Y/Xn)/2; Y - это то, из чего корень извлекают. X0 - скажем Y/2.
Формулу отAlex255 чуток поправил.

SergVZ, а сколько итераций надо сделать, чтобы точность была ну, хотя бы 5-10%?

[GetSmart]

у меня с двух итераций получилась точность 0.175%
с трёх итераций точность 0.00015% !!!

[SergVZ]

GetSmart, Вам похоже повезло с цифрами, возьмите для примера числа :100000 или 10е-6
vovan1313, Вы не указали диапозон аргумента и его тип. Попробуйте по-экспериментировать на калькуляторе число шагов с минимальным (если аргумент вещественный-наиболее его близким к нулю), несколько средних (по порядку) значениями и максимальным.
Я с ПЛИСами не работал (Вы же просили верилоговский сырец дать)-тут совет не дам.
Не забудьте проверить, что извлекаете корень из неотрицательного числа и сделать проверку на ноль, иначе Вам на "0" придеться делить.
На процах (МК) , при юзаньи этого алгоритма ("Ньютона") я всегда число итераций ограничиваю сверху из значения, полученного на кулькуляторе +1, и сравниваю разность между значениями соседних иттераций, она (разность) по модулю больше абсолютной ошибки.
Можете попробовать пару методов, на основе рядов Тейлора:
F(X)=.. или F(X0+dX)= , число членов оценивайте по калькулятору, но тут не придется делить на добные числа.

[SergVZ]

К сожалению, уже потерял право на релактирование своего поста.
Ловите добавку к нему:
Можно составить табличку: первые цифры(одна- две) аргумента-ответ, плюс поправка, наподобие таблиц Брадиса (ими раньше в школах пользовались).

[GetSmart]

Понятно. Чем дальше логарифмически аргумент находится от 1 тем больше итераций нужно делать. Вчера мои оптимистичные результаты были для корня из 8.

[vovan1313]

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

Сообщение отредактировал vovan1313 - Oct 19 2007, 12:38

[JBM]

Код

///////////////////////////////////////////////////////////////////////////
// Carmack from ID Software's unusual square root routine for
// the quake engine
inline float q_sqrt(float number)
{
    long i;
    float x, y;
    const float f = 1.5F;
    
    x = number * 0.5F;
    y  = number;
    i  = * (long*) &y;
    i  = 0x5f3759df - (i >> 1);
    y  = * (float * ) &i;
    y  = y * (f - (x * y * y));
    y  = y * (f - (x * y * y));
    
    return number *y;
}

[LordVader]

JBM, эта процедурка для 1/sqrt(x), вообще-то. О чём гугл говорит, а также много другого (искать по шестнадцатеричной константе).

[Serhiy_UA]

Есть несколько устройств и алгоритмы прямого извлечения корня в
http://electronix.ru/forum/index.php?showtopic=46469&hl=

Конечный выбор определяется исходными требованиями. Основные из них: время выполнения на операция и аппаратурные затраты, а также на чем это выполнять.

[Палыч]

Xn+1=(Xn+Y/Xn)/2; Y - это то, из чего корень извлекают. X0 - скажем Y/2.

Брать за Х0 число Y/2 - не самый лучший вариант...
Когда-то давно самому пришлось писать функцию вычисления корня квадратного. Программулину ту что-то найти не удаётся... По-памяти:
Если вспомнить, что вещественные числа в памяти хранятся в виде 2^N*M, то квадратный корень от числа будет равен 2^(N/2)*sqtr(M). Плохо то, что N может быть нечётным, да и корень от мантисы взять неоткуда... Но за X0 очень хорошо взять число хотя бы со степенью N/2, тем более, что получить его, обычно, очень просто - сдвигом вправо на 1 разряд. При этом получаем промежуточный результат с 1-2 верными первыми десятичными цифрами.
Ну, а дальше - Ньютон: каждая итерация добавляет ещё 1-2 верные цифры. Правда, если итерация дала 2 верные цифры, то следующая скорее всего даст только одну. Для получения шести верных первых цифр всегда достаточно взять Х0 по правилу изложенному выше и сделать 3 итерации.