# sqrt in HW

Discussion in 'VHDL' started by valentin tihomirov, Sep 12, 2004.

1. ### valentin tihomirovGuest

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.

valentin tihomirov, Sep 12, 2004

2. ### David BishopGuest

Take a look at:
http://www.eda.org/vhdl-200x/vhdl-200x-ft/packages/files.html
These are the packages for the next release of VHDL (preliminary).
You will find a synthesizable square root routine in the floating
point packages, which was designed to be adaptable to a fixed point
routine. (You will also find a fixed point VHDL package there)

valentin tihomirov wrote:
>
> 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.
>
>

David Bishop, Sep 13, 2004