Factorial solution

B

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
 
On Tue, 21 Apr 2009 09:41:37 +0200, Bert_Paris wrote:

Synthesis results : 10 LUTs for the Factorial, as expected !
Click to expand...
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.bromley@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.
 
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 !
Click to expand...
 
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
 
On Tue, 21 Apr 2009 13:42:58 +0200, Bert_Paris wrote:

Before anyone notices ;-)
Click to expand...
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) ?
Click to expand...
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.bromley@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.
 
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
 
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" <do_not_spam@me.com> wrote in message
news:49ede963$0$18750$426a74cc@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
Click to expand...

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;
Click to expand...
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
Click to expand...
-- 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
Click to expand...
 
HT-Lab a exprimé avec précision :
... VHDL2008 goodness ...
Isn't this an oxymoron ? ;-)
Click to expand...

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" <do_not_spam@me.com> wrote in message
news:49edf20f$0$21438$426a74cc@news.free.fr...
HT-Lab a exprimé avec précision :
... VHDL2008 goodness ...
Isn't this an oxymoron ? ;-)
Click to expand...
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)
Click to expand...
you are correct.

btw: Is anyone using or even still interested in VHDL 2008 ?
Click to expand...
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.
Click to expand...
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

 
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.
Click to expand...
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)
 
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)
Click to expand...
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?
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top