sqrt in HW

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

  1. 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.
    valentin tihomirov, Sep 12, 2004
    #1
    1. Advertising

  2. valentin tihomirov

    David Bishop Guest

    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:
    > 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.
    >
    >
    David Bishop, Sep 13, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Ward

    sqrt(negative)?

    Tim Ward, Dec 17, 2004, in forum: Java
    Replies:
    2
    Views:
    533
  2. Prune Tracy
    Replies:
    6
    Views:
    1,819
    Ioannis Vranos
    Oct 14, 2004
  3. Aric

    trouble sqrt in gcc

    Aric, Aug 26, 2003, in forum: C Programming
    Replies:
    7
    Views:
    536
    Greg P.
    Aug 27, 2003
  4. Michael McNeil Forbes

    how to overload sqrt in a module?

    Michael McNeil Forbes, Mar 3, 2006, in forum: Python
    Replies:
    14
    Views:
    485
    Steven D'Aprano
    Mar 5, 2006
  5. ostehamster

    SQRT in VHDL

    ostehamster, Sep 5, 2006, in forum: VHDL
    Replies:
    0
    Views:
    1,443
    ostehamster
    Sep 5, 2006
Loading...

Share This Page