V
valentin tihomirov
Guest
Please appreciate my function:
function simple_sqrt(constant SQUARE: std_logic_vector) return
std_logic_vector is
-- temporary area, it should fit 2xborder greater value than the area
specified n the argument
-- thus, let's take it is 1 bit longer
variable SQ: std_logic_vector(SQUARE'length downto 0) := (others =>
'0'); -- our temp area
variable BORDER: unsigned(SQUARE'length/2-1 downto 0) := (others =>
'0'); -- temp result(root)
constant ZEROES: std_logic_vector(BORDER'range) := (others => '0');
begin
-- (a+1)^2 = (a+1)*(a+1) = a^2 + (2a + 1), here 2a+1 is an arithmetic
progression we compute in the loop
-- Initial area and border are 0, let's increase them proportionally until
the area becomes higher than
-- the argument. At this point, we have gained result (border) rounded
to MIN.
while true loop
-- SQ <= SQ + 2xBorder + 1
SQ := SQ + (std_logic_vector(BORDER(BORDER'high downto 0)) & '0') + 1;
if SQ > SQUARE then
return std_logic_vector(BORDER);
end if;
BORDER := BORDER+1;
end loop;
end;
The function is based on a SW algorithm. Here is another one, a little more
compleicated but number of iterations is log2(x):
unsigned sqrt_cpu_newton(long L) {
unsigned rslt = (unsigned)L;
long div = L;
if (L <= 0) return 0;
while (l) {
div = (L / div + div) / 2;
if (rslt > div)
rslt = (unsigned)div;
else
return rslt; }
}
Not sure they are good for HW. I'm even not sure about resulting vector
width (will it twice shorter than the argument?). Please let me know if the
BORDER and intermediate SQUARE vectors have invalid lengths.
An attempt to "Synplify" the function by the architecture below throws an
error, the synthesier tells that the while loop in the SQRT function is
unterminated and recommends using a special terminating attibute. I have
analyzed the number of iterations for 64-bit argument (oh dear) -- it is
about 4G. The calculation is simple: 4Gx4G = 64bit; that is, a square with
32-bit sides has a 64-bit area). That is, we need 4G iterations to grow up
to the 64bit-area square. It is increadibly long to wait for such a long
analisys. How can I help the compiler, should the log2 iterations algorithm
be adopted? Actually, I intended the function for huge numbers, thouthands
of bits at the input.
package PKG is
constant ARG_LENGTH: Integer := 64; -- 2048
constant RES_LENGTH: Integer := ARG_LENGTH/2;
function simple_sqrt(constant SQUARE: std_logic_vector) return
std_logic_vector;
end package PKG;
entity SQRT_CONSTANT is
port( O: out std_logic_vector(RES_LENGTH-1 downto 0));
end SQRT_CONSTANT;
architecture RTL of SQRT_CONSTANT is
constant I_CONST: std_logic_vector(ARG_LENGTH-1 downto 0) := (others =>
'1');
begin
O <= simple_sqrt(I_CONST);
end RTL;
Thanks.
function simple_sqrt(constant SQUARE: std_logic_vector) return
std_logic_vector is
-- temporary area, it should fit 2xborder greater value than the area
specified n the argument
-- thus, let's take it is 1 bit longer
variable SQ: std_logic_vector(SQUARE'length downto 0) := (others =>
'0'); -- our temp area
variable BORDER: unsigned(SQUARE'length/2-1 downto 0) := (others =>
'0'); -- temp result(root)
constant ZEROES: std_logic_vector(BORDER'range) := (others => '0');
begin
-- (a+1)^2 = (a+1)*(a+1) = a^2 + (2a + 1), here 2a+1 is an arithmetic
progression we compute in the loop
-- Initial area and border are 0, let's increase them proportionally until
the area becomes higher than
-- the argument. At this point, we have gained result (border) rounded
to MIN.
while true loop
-- SQ <= SQ + 2xBorder + 1
SQ := SQ + (std_logic_vector(BORDER(BORDER'high downto 0)) & '0') + 1;
if SQ > SQUARE then
return std_logic_vector(BORDER);
end if;
BORDER := BORDER+1;
end loop;
end;
The function is based on a SW algorithm. Here is another one, a little more
compleicated but number of iterations is log2(x):
unsigned sqrt_cpu_newton(long L) {
unsigned rslt = (unsigned)L;
long div = L;
if (L <= 0) return 0;
while (l) {
div = (L / div + div) / 2;
if (rslt > div)
rslt = (unsigned)div;
else
return rslt; }
}
Not sure they are good for HW. I'm even not sure about resulting vector
width (will it twice shorter than the argument?). Please let me know if the
BORDER and intermediate SQUARE vectors have invalid lengths.
An attempt to "Synplify" the function by the architecture below throws an
error, the synthesier tells that the while loop in the SQRT function is
unterminated and recommends using a special terminating attibute. I have
analyzed the number of iterations for 64-bit argument (oh dear) -- it is
about 4G. The calculation is simple: 4Gx4G = 64bit; that is, a square with
32-bit sides has a 64-bit area). That is, we need 4G iterations to grow up
to the 64bit-area square. It is increadibly long to wait for such a long
analisys. How can I help the compiler, should the log2 iterations algorithm
be adopted? Actually, I intended the function for huge numbers, thouthands
of bits at the input.
package PKG is
constant ARG_LENGTH: Integer := 64; -- 2048
constant RES_LENGTH: Integer := ARG_LENGTH/2;
function simple_sqrt(constant SQUARE: std_logic_vector) return
std_logic_vector;
end package PKG;
entity SQRT_CONSTANT is
port( O: out std_logic_vector(RES_LENGTH-1 downto 0));
end SQRT_CONSTANT;
architecture RTL of SQRT_CONSTANT is
constant I_CONST: std_logic_vector(ARG_LENGTH-1 downto 0) := (others =>
'1');
begin
O <= simple_sqrt(I_CONST);
end RTL;
Thanks.