Factorial solution

Discussion in 'VHDL' started by Bert_Paris, Apr 21, 2009.

  1. Bert_Paris

    Bert_Paris Guest

    -- Fact_rtl.vhd
    -- --------------------------------------------------
    -- Factorial Example - Synthesizable & efficient !
    -- --------------------------------------------------
    -- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
    -- Tested successfully with Quartus II v9.0.
    -- but it should be fine with any decent synthesizer.
    --
    -- Note : added registers in front and after to easily
    -- get the Tsu (Fmax) after synthesis
    -- Synthesis results : 10 LUTs for the Factorial, as expected !
    -- Timing : speed practically unlimited since 1 Logic Level (250Mhz on
    Cyclone III)

    Library IEEE;
    use IEEE.std_logic_1164.all;
    use IEEE.numeric_std.all;
    -- ---------------------------------------
    Entity Factorial is
    -- ---------------------------------------
    port ( Clk : in std_logic;
    Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
    ... 944
    Result : out std_logic_vector (9 downto 0) ); -- 0 .. 1023
    End Entity Factorial;

    -- ---------------------------------------
    Architecture RTL of Factorial is -- yes, this is perfect for
    synthesis !
    -- ---------------------------------------

    -- The usual recursive function
    function fact (d : natural) return natural is
    variable res : natural;
    begin
    if d=0 then
    res := 0;
    elsif d=1 then
    res := 1;
    else
    res := d * fact (d-1);
    end if;
    return res;
    end function fact;

    -- Constant table type
    type Table_t is array (0 to 7) of unsigned(result'range);

    -- Function to initialize a table with the factorial
    impure function Init_Table return Table_t is
    variable T : Table_t;
    begin
    for I in T'range loop
    T(I) := to_unsigned(fact(I),Result'length);
    end loop;
    return T;
    end function Init_Table;

    -- The Table itself, initialized at creation :
    signal Table : Table_t := Init_Table;
    -- note ;: this table will be smplified in a few Logic Elements

    signal Dinr : std_logic_vector (Din'range);
    ------\
    begin -- Architecture
    ------/
    Dinr <= Din when rising_edge(Clk); -- input FFs
    result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
    rising_edge(Clk);

    end RTL;

    ------------------------------------------
    -- Test Bench. Simulate -all
    ------------------------------------------
    -- synopsys translate_off
    library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
    Entity factorial_tb is end;
    Architecture test of factorial_tb is
    signal Clk : std_logic := '0';
    signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
    840
    signal Result : std_logic_vector (9 downto 0);
    begin
    assert Clk='0' or now < 500 ns report "Simulation has ended (not an
    error)." severity failure;
    Clk <= not Clk after 5 ns; -- 100 MHz clock
    Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
    uut: entity work.factorial port map (Clk,Din,Result);
    end architecture TEST;
    -- synopsys translate_on
     
    Bert_Paris, Apr 21, 2009
    #1
    1. Advertising

  2. Bert_Paris

    Bert_Paris Guest

    Hi Jonathan :)
    Some tools can reduce it to 6 LUTs, but my description without Flops
    and no async reset does help them too much ;-)
    We should stop doing the students' assignments in this forum (lol)
    I guess the next assignment will be the Ackermann's function (if the
    teachers keep an eye on this newsgroup) ?

    Bert

    > On Tue, 21 Apr 2009 09:41:37 +0200, Bert_Paris wrote:
    >
    >> Synthesis results : 10 LUTs for the Factorial, as expected !

    >
     
    Bert_Paris, Apr 21, 2009
    #2
    1. Advertising

  3. Bert_Paris

    Bert_Paris Guest

    Before anyone notices ;-)
    The previous version didn't handle the last value (7) correctly, which
    factorial is 5040 and thus requires a 13 bits output vector.
    Or maybe we should leave intentional errors for the teachers (lol) ?

    -- Fact_rtl.vhd
    -- --------------------------------------------------
    -- Factorial Example - Synthesizable & efficient !
    -- --------------------------------------------------
    -- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
    -- Version : 2.0, handles all values 0..7 -> 0 .. 5040
    -- Tested successfully with :
    -- * Altera Quartus II v9.0,
    -- * Actel Libero 8.5 (Synplify)
    -- * Xilinx ISE 10
    -- but it should be fine with any decent synthesizer
    --
    -- Note : added registers in front and after to easily
    -- get the Tsu (Fmax) after synthesis.
    -- Synthesis results : 8 LUTs for the Factorial !
    -- Timing : speed practically unlimited since only 1 Logic Level
    (250Mhz on Cyclone III)

    Library IEEE;
    use IEEE.std_logic_1164.all;
    use IEEE.numeric_std.all;
    -- ---------------------------------------
    Entity Factorial is
    -- ---------------------------------------
    port ( Clk : in std_logic;
    Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
    ... 5040
    Result : out std_logic_vector (12 downto 0) ); -- 0 .. 8191
    End Entity Factorial;

    -- ---------------------------------------
    Architecture RTL of Factorial is -- yes, this is perfect for
    synthesis !
    -- ---------------------------------------

    -- The usual recursive function
    function fact (d : natural) return natural is
    variable res : natural;
    begin
    if d=0 then
    res := 0;
    elsif d=1 then
    res := 1;
    else
    res := d * fact (d-1);
    end if;
    return res;
    end function fact;

    -- Constant table type
    type Table_t is array (0 to 7) of unsigned(result'range);

    -- Function to initialize a table with the factorial
    impure function Init_Table return Table_t is
    variable T : Table_t;
    begin
    for I in T'range loop
    T(I) := to_unsigned(fact(I),Result'length);
    end loop;
    return T;
    end function Init_Table;

    -- The Table itself, initialized at creation :
    signal Table : Table_t := Init_Table;
    -- note : this table will be simplified into a few LUTs

    signal Dinr : std_logic_vector (Din'range);

    ------\
    begin -- Architecture
    ------/
    Dinr <= Din when rising_edge(Clk); -- input FFs
    result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
    rising_edge(Clk);

    End architecture RTL;

    --------------------------------------------------
    -- Test Bench. Simulate -all, eyeball the results
    --------------------------------------------------
    -- synopsys translate_off
    library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
    Entity factorial_tb is end;
    Architecture TEST of factorial_tb is
    signal Clk : std_logic := '0';
    signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
    840
    signal Result : std_logic_vector (12 downto 0);
    begin
    assert Clk='0' or now < 500 ns report "Simulation has ended (not an
    error)." severity failure;
    Clk <= not Clk after 5 ns; -- 100 MHz clock
    Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
    uut: entity work.factorial port map (Clk,Din,Result);
    end architecture TEST;
    -- synopsys translate_on
     
    Bert_Paris, Apr 21, 2009
    #3
  4. On 21 avr, 08:09, Jonathan Bromley <>
    wrote:
    > On Tue, 21 Apr 2009 13:42:58 +0200, Bert_Paris wrote:
    > >Before anyone notices ;-)

    >
    > From Jonathan's Dictionary of Computing Terms:
    >
    > SEND BUTTON (n):
    > Powerful design review tool intended to improve
    > code quality by exposing authors of erroneous
    > code to public ridicule.  Unfortunately it can be
    > proven that this tool can only work retrospectively;
    > this is a consequence of Goedel's Incompleteness
    > Theorem and is a property shared with related
    > tools such as BOOK PUBLICATION and PRODUCT RELEASE.
    >
    > >Or maybe we should leave intentional errors for the teachers (lol) ?

    >
    > No, we make enough of our own :)
    > --
    > Jonathan Bromley, Consultant
    >
    > DOULOS - Developing Design Know-how
    > VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
    >
    > Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
    > ://www.MYCOMPANY.com
    >
    > The contents of this message may contain personal views which
    > are not the views of Doulos Ltd., unless specifically stated.


    I might not be as good as you guys are in VHDL and FPGAs, but there's
    an error in the code


    0! = 1

    Therefore, it should be corrected (it's not a big deal)
     
    Benjamin Couillard, Apr 21, 2009
    #4
  5. Bert_Paris

    Bert_Paris Guest

    Argh, I actually modified my code to implement 0!=0,
    but you're right : "By convention, 0! = 1".
    The code is now two lines shorter ;-)
    and I used an attribute for the Table length, so I guess
    the port could now use unconstrained vectors. Slick.

    -- Fact_rtl.vhd
    -- --------------------------------------------------
    -- Factorial Example - Synthesizable & efficient !
    -- --------------------------------------------------
    -- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
    -- Version : 2.1, handles all values 0..7 -> 0 .. 5040
    -- By convention, 0! = 1
    -- Tested successfully with :
    -- * Altera Quartus II v9.0,
    -- * Actel Libero 8.5 (Synplify)
    -- * Xilinx ISE 10
    -- but it should be fine with any decent synthesizer
    --
    -- Note : added registers in front and after to easily
    -- get the Tsu (Fmax) after synthesis.
    -- Synthesis results : 8 LUTs for the Factorial !
    -- Timing : speed practically unlimited since only 1 Logic Level
    (250Mhz on Cyclone III)

    Library IEEE;
    use IEEE.std_logic_1164.all;
    use IEEE.numeric_std.all;
    -- ---------------------------------------
    Entity Factorial is
    -- ---------------------------------------
    port ( Clk : in std_logic;
    Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
    ... 5040
    Result : out std_logic_vector (12 downto 0) ); -- 0 .. 8191
    End Entity Factorial;

    -- ---------------------------------------
    Architecture RTL of Factorial is -- yes, this is perfect for
    synthesis !
    -- ---------------------------------------

    -- The usual recursive function
    function fact (d : natural) return natural is
    variable res : natural;
    begin
    if d<2 then
    res := 1;
    else
    res := d * fact (d-1);
    end if;
    return res;
    end function fact;

    -- Constant table type
    type Table_t is array (0 to 2**Din'length - 1) of
    unsigned(result'range);

    -- Function to initialize a table with the factorial
    impure function Init_Table return Table_t is
    variable T : Table_t;
    begin
    for I in T'range loop
    T(I) := to_unsigned(fact(I),Result'length);
    end loop;
    return T;
    end function Init_Table;

    -- The Table itself, initialized at creation :
    signal Table : Table_t := Init_Table;
    -- note : this table will be simplified into a few LUTs

    signal Dinr : std_logic_vector (Din'range);

    ------\
    begin -- Architecture
    ------/
    Dinr <= Din when rising_edge(Clk); -- input FFs
    result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
    rising_edge(Clk);

    End architecture RTL;

    --------------------------------------------------
    -- Test Bench. Simulate -all, eyeball the results
    --------------------------------------------------
    -- synopsys translate_off
    library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
    Entity factorial_tb is end;
    Architecture TEST of factorial_tb is
    signal Clk : std_logic := '0';
    signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
    840
    signal Result : std_logic_vector (12 downto 0);
    begin
    assert Clk='0' or now < 500 ns report "Simulation has ended (not an
    error)." severity failure;
    Clk <= not Clk after 5 ns; -- 100 MHz clock
    Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
    uut: entity work.factorial port map (Clk,Din,Result);
    end architecture TEST;
    -- synopsys translate_on
     
    Bert_Paris, Apr 21, 2009
    #5
  6. Bert_Paris

    Bert_Paris Guest

    Factorial solution (final ?)

    I can't resist :)
    This is the unconstrained ports version, a breeze to parameterize.
    And it handles integers larger than 32 bits.


    -- Fact_rtl.vhd
    -- --------------------------------------------------
    -- Factorial Example - Synthesizable & efficient !
    -- --------------------------------------------------
    -- Author : (c) Bert Cuzeau. ALSE. http://www.alse-fr.com
    -- Version : 3.0, using unconstrained vectors.
    -- Handles numbers larger than 2**31
    --
    -- Synthesis results : 8 LUTs for (0! .. 7!)
    -- 32 LUTS for (0! .. 15! = 1307674368000)
    -- Tested with Quartus II v 9.0.
    -- Should be fine with any synthesis tool.
    --
    -- Make sure you synthesize "Wrapper" as the top level.

    Library IEEE;
    use IEEE.std_logic_1164.all;
    use IEEE.numeric_std.all;
    -- ---------------------------------------
    Entity Factorial is
    -- ---------------------------------------
    port ( Clk : in std_logic;
    Din : in std_logic_vector; -- Yep, unconstrained !
    Result : out std_logic_vector );
    End Entity Factorial;

    -- ---------------------------------------
    Architecture RTL of Factorial is -- yes, this is perfect for
    synthesis !
    -- ---------------------------------------

    -- The (almost) usual recursive function
    function fact (d : unsigned) return unsigned is
    variable res : unsigned (d'range);
    begin
    if d<2 then -- note that, by convention, 0! = 1
    res := to_unsigned(1,res'length);
    else
    res := "*" (d,fact (d-1))(res'range);
    end if;
    return res;
    end function fact;

    -- Constant table type
    type Table_t is array (0 to 2**Din'length - 1) of
    unsigned(Result'range);

    -- Function to initialize a table with the factorial
    impure function Init_Table return Table_t is
    variable T : Table_t;
    begin
    for I in T'range loop
    T(I) := fact(to_unsigned(I,Result'length));
    end loop;
    return T;
    end function Init_Table;

    -- The Table itself, initialized at creation :
    signal Table : Table_t := Init_Table;
    -- note : this table will be simplified into a few LUTs

    signal Dinr : std_logic_vector (Din'range);

    ------\
    Begin -- Architecture
    ------/
    Dinr <= Din when rising_edge(Clk); -- input FFs
    result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
    rising_edge(Clk);

    End architecture RTL;


    --------------------------------------------------------
    -- Wrapper for Synthesis (4 -> 41 bits implementation)
    --------------------------------------------------------
    Library IEEE; use IEEE.std_logic_1164.all;
    Entity Wrapper is -- For Synthesis of 4 bits -> 41 bits
    port ( Clk : in std_logic;
    Din : in std_logic_vector (3 downto 0); -- 0! .. 15! =
    13077775800hex
    Result : out std_logic_vector (40 downto 0) ); -- 41 bits
    result
    End Entity Wrapper;
    architecture Wrap of Wrapper is
    begin
    Fact : entity work.Factorial port map (Clk,Din,Result);
    end architecture Wrap;


    --------------------------------------------------
    -- Test Bench. Simulate -all, eyeball the results
    --------------------------------------------------
    -- synopsys translate_off
    library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
    Entity factorial_tb is end;
    Architecture TEST of factorial_tb is
    signal Clk : std_logic := '0';
    signal Din : std_logic_vector (3 downto 0) := (others=>'0'); -- 0!
    ... 15!
    signal Result : std_logic_vector (40 downto 0);
    begin
    assert Clk='0' or now < 800 ns report "Simulation has ended (not an
    error)." severity failure;
    Clk <= not Clk after 5 ns; -- 100 MHz clock
    Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
    uut: entity work.factorial port map (Clk,Din,Result);
    end architecture TEST;
    -- synopsys translate_on
     
    Bert_Paris, Apr 21, 2009
    #6
  7. Bert_Paris

    HT-Lab Guest

    Re: Factorial solution (final ?)

    "Bert_Paris" <> wrote in message
    news:49ede963$0$18750$...
    >I can't resist :)
    > This is the unconstrained ports version, a breeze to parameterize.
    > And it handles integers larger than 32 bits.

    ...snip

    nearly final, add a bit VHDL2008 goodness to remove the error/failure
    message....:)

    > --------------------------------------------------
    > -- Test Bench. Simulate -all, eyeball the results
    > --------------------------------------------------
    > -- synopsys translate_off
    > library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;


    library std;
    use std.env.all;

    > Entity factorial_tb is end;
    > Architecture TEST of factorial_tb is
    > signal Clk : std_logic := '0';
    > signal Din : std_logic_vector (3 downto 0) := (others=>'0'); -- 0! ..
    > 15!
    > signal Result : std_logic_vector (40 downto 0);
    > begin

    -- assert Clk='0' or now < 800 ns report "Simulation has ended (not an
    -- error)." severity failure;

    STOP(1);

    Hans
    www.ht-lab.com


    > Clk <= not Clk after 5 ns; -- 100 MHz clock
    > Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
    > uut: entity work.factorial port map (Clk,Din,Result);
    > end architecture TEST;
    > -- synopsys translate_on
    >
    >
     
    HT-Lab, Apr 21, 2009
    #7
  8. Bert_Paris

    Bert_Paris Guest

    VHDL 2008 ?

    HT-Lab a exprimé avec précision :
    > ... VHDL2008 goodness ...

    Isn't this an oxymoron ? ;-)

    For the purist who doesn't like the failure ending, it's easy to stop
    simulation using events starvation (stopping the clock) :
    Clk <= '0' when Done else not Clock after (Period / 2);
    Done <= true after 800 ns;
    I don't think your 2008 code works as is (without a process, and a
    wait)

    btw: Is anyone using or even still interested in VHDL 2008 ?
    I still wouldn't recommend using VHDL2008 yet, and I don't feel it's
    going to save the language, but maybe I'm wrong.
     
    Bert_Paris, Apr 21, 2009
    #8
  9. Bert_Paris

    HT-Lab Guest

    Re: VHDL 2008 ?

    "Bert_Paris" <> wrote in message
    news:49edf20f$0$21438$...
    > HT-Lab a exprimé avec précision :
    >> ... VHDL2008 goodness ...

    > Isn't this an oxymoron ? ;-)


    No it is a pleonasm :)

    >
    > For the purist who doesn't like the failure ending, it's easy to stop
    > simulation using events starvation (stopping the clock) :
    > Clk <= '0' when Done else not Clock after (Period / 2);
    > Done <= true after 800 ns;
    > I don't think your 2008 code works as is (without a process, and a wait)


    you are correct.

    >
    > btw: Is anyone using or even still interested in VHDL 2008 ?


    Using, no since I am still waiting for Mentor to support it. Interested,
    definitely yes since it has some nice additions.

    > I still wouldn't recommend using VHDL2008 yet, and I don't feel it's going
    > to save the language, but maybe I'm wrong.


    Saving the language from what? For verification I agree that the ship has
    sailed (although you can still see it in the distance) since SV/SC are
    simply to far ahead but for design VHDL will be use for a long long
    time.....(I hope)

    Hans
    www.ht-lab.com

    >
    >
     
    HT-Lab, Apr 21, 2009
    #9
  10. Bert_Paris

    JimLewis Guest

    Re: VHDL 2008 ?


    > > I still wouldn't recommend using VHDL2008 yet, and I don't feel it's going
    > > to save the language, but maybe I'm wrong.

    >
    > Saving the language from what? For verification I agree that the ship has
    > sailed (although you can still see it in the distance) since SV/SC are
    > simply to far ahead but for design VHDL will be use for a long long
    > time.....(I hope)


    I think you are listening too much to marketing people.

    For RTL, VHDL has better math capabilities (unsigned, signed,
    signed fixed point, unsigned fixed point, and float). Did SV
    even bother?

    Yes for verification SV has more built in language features, however,
    constrained random, functional coverage, and coverage driven
    verification can be achieved in VHDL by writing procedural code.
    See: http://www.synthworks.com/downloads/index.htm

    This is stuff we are have been teaching for several years in
    our VHDL Testbenches and Verification classes. I submitted a
    paper on it to DVCon for the last two years, however, they are
    so biased that they no longer accept VHDL papers. So if we
    want a VHDL conference, we will have to start our own or
    better yet, have more webinars.

    Best,
    Jim

    P.S.
    In the US at least, WRT job postings, there are more requests
    for VHDL (144) than Verilog (101). It has been this way for
    quite a while (even before the economy changes in October).
    If you further refine the search to
    VHDL and not Verilog: 79
    Verilog and not VHDL: 36
    VHDL and Verilog: 65

    So basically almost all of the job postings that have VHDL and
    Verilog would have to be for Verilog in order for Verilog to
    have a lead in the job market.

    Perhaps most of the VHDL users use free tools so the vendors
    don't count them?
     
    JimLewis, Apr 27, 2009
    #10
    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. Silver
    Replies:
    9
    Views:
    703
    red floyd
    Dec 5, 2003
  2. Replies:
    2
    Views:
    489
    marbac
    May 8, 2005
  3. aNt17017

    Long(er) Factorial

    aNt17017, Apr 21, 2006, in forum: C Programming
    Replies:
    35
    Views:
    981
    Keith Thompson
    Apr 26, 2006
  4. Replies:
    59
    Views:
    1,775
    Richard Heathfield
    Sep 21, 2006
  5. Hamburgpear

    Factorial using C

    Hamburgpear, Sep 12, 2005, in forum: C++
    Replies:
    6
    Views:
    567
    jacob navia
    Sep 13, 2005
Loading...

Share This Page