Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Factorial solution

191 views
Skip to first unread message

Bert_Paris

unread,
Apr 21, 2009, 3:41:37 AM4/21/09
to
-- 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


Jonathan Bromley

unread,
Apr 21, 2009, 6:55:38 AM4/21/09
to
On Tue, 21 Apr 2009 09:41:37 +0200, Bert_Paris wrote:

> Synthesis results : 10 LUTs for the Factorial, as expected !

Very nice :-) and I suppose the corresponding design
for Ackermann's function [*] is left as an exercise for
the student.....

[*] For non-negative integer m,n:
A(0, n) = n+1
A(m, 0) = A(m-1, 1) for m>0
A(m,n) = A(m-1, A(m, n-1)) for m,n > 0

You don't need many bits for the inputs!
--
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
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

Bert_Paris

unread,
Apr 21, 2009, 7:26:56 AM4/21/09
to
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

Bert_Paris

unread,
Apr 21, 2009, 7:42:58 AM4/21/09
to
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;

-- 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);

Jonathan Bromley

unread,
Apr 21, 2009, 8:09:46 AM4/21/09
to
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 :-)

Benjamin Couillard

unread,
Apr 21, 2009, 10:51:09 AM4/21/09
to
On 21 avr, 08:09, Jonathan Bromley <jonathan.brom...@MYCOMPANY.com>
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
> jonathan.brom...@MYCOMPANY.comhttp://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)

Bert_Paris

unread,
Apr 21, 2009, 11:04:36 AM4/21/09
to
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);

Bert_Paris

unread,
Apr 21, 2009, 11:42:27 AM4/21/09
to
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

HT-Lab

unread,
Apr 21, 2009, 11:58:07 AM4/21/09
to

"Bert_Paris" <do_no...@me.com> wrote in message
news:49ede963$0$18750$426a...@news.free.fr...

>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

Bert_Paris

unread,
Apr 21, 2009, 12:19:26 PM4/21/09
to
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.


HT-Lab

unread,
Apr 21, 2009, 12:45:25 PM4/21/09
to

"Bert_Paris" <do_no...@me.com> wrote in message
news:49edf20f$0$21438$426a...@news.free.fr...

> 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

>
>


JimLewis

unread,
Apr 27, 2009, 10:30:42 AM4/27/09
to

> > 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?

0 new messages