+ Post New Thread
Results 1 to 14 of 14

2nd December 2019, 14:51 #1
 Join Date
 Mar 2003
 Posts
 309
 Helped
 21 / 21
 Points
 4,983
 Level
 16
fastest multiplication alghorithms
Hi,
What do you think is the fastest multiplication alghorithms in the world?

Advertisement

2nd December 2019, 14:56 #2

2nd December 2019, 16:48 #3
 Join Date
 Mar 2003
 Posts
 309
 Helped
 21 / 21
 Points
 4,983
 Level
 16

2nd December 2019, 16:54 #4
Awards:
 Join Date
 Apr 2014
 Posts
 16,019
 Helped
 3631 / 3631
 Points
 78,950
 Level
 68
Re: fastest multiplication alghorithms
Hi,
I vote for a big lookup table.
KlausPlease don´t contact me via PM, because there is no time to respond to them. No friend requests. Thank you.

Advertisement

2nd December 2019, 17:15 #5
 Join Date
 Dec 2017
 Location
 Bydgoszcz  Poland
 Posts
 151
 Helped
 21 / 21
 Points
 1,176
 Level
 7
Re: fastest multiplication alghorithms
Hello,
i agree with @KlausST. If you are looking for theoretical information see links to these algorithms:
https://en.wikipedia.org/wiki/Karatsuba_algorithm
https://en.wikipedia.org/wiki/Toom%E...multiplication
https://en.wikipedia.org/wiki/Sch%C3...ssen_algorithm
https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm
If you wanna fast multiplication operation using FPGA just use "hardware multipliers" or "DSP blocks" from FPGA fabric.
RegardsLast edited by FlyingDutch; 2nd December 2019 at 17:20.
1 members found this post helpful.

2nd December 2019, 20:27 #6
 Join Date
 Mar 2003
 Posts
 309
 Helped
 21 / 21
 Points
 4,983
 Level
 16
Re: fastest multiplication alghorithms
I am looking for fast ASIC implementation. Booth looks good.
But I want a 4 step pipelined multiplier.
   Updated   
Really I want a fast pipelined implementation of 24 bit multiplier for 32 bit floating point multiplication. I prefer four or six stage pipelined multiplier.

Advertisement

2nd December 2019, 21:53 #7
Awards:
 Join Date
 Apr 2014
 Posts
 16,019
 Helped
 3631 / 3631
 Points
 78,950
 Level
 68
Re: fastest multiplication alghorithms
Hi,
Do you recognize that you jump from one requirenent to the other.
unsigned 8 bit24 bit multiplier32 bit floating pointI want a 4 step pipelined multiplier.four or six stage pipelined multiplier.
KlausPlease don´t contact me via PM, because there is no time to respond to them. No friend requests. Thank you.

3rd December 2019, 07:54 #8
 Join Date
 Mar 2003
 Posts
 309
 Helped
 21 / 21
 Points
 4,983
 Level
 16
Re: fastest multiplication alghorithms
I am so sorry. You are right.
But i was thinking about difference ways to multiply two 32bit floating point. And its the effect of different solutions.
Actually in 32bit floating point multiplication, we should multiply two mantissa and add two exponent. so the bottleneck of speed is multiplication of two mantissa. Initially i was looking for a fast multiplication algorithm. but later i thought about a pipelined multiplication algorithm to increase clock ratio in some sequential independent multiplication.
What is you idea?

3rd December 2019, 08:09 #9
 Join Date
 Feb 2016
 Posts
 684
 Helped
 1 / 1
 Points
 3,557
 Level
 14
Re: fastest multiplication alghorithms
See my multiplication implementation in verilog
https://github.com/promach/multiply

Advertisement

3rd December 2019, 13:58 #10
Awards:
 Join Date
 Apr 2014
 Posts
 16,019
 Helped
 3631 / 3631
 Points
 78,950
 Level
 68
Re: fastest multiplication alghorithms
Hi,
I think there is a big difference whether you do 8x8 bit integer multiplication or 32bit x 32bit floating point multiplication.
One is the lower end, the other is the higher end ( or at least good middle range)
the one has a dynamic of 1:256, the other about 1:144700000000000000000000000000000000000000000000 000000000000000000000000000
(dont know whether there is a zero too much or too less)
So it´s something totally different.
*********************************
If I understand you right, then you don´t need "fast" code, but code with high "throughput".
(pipelined code is not fast (input to output) but it has high throughput (maybe one calculation per clock cycle))
KlausPlease don´t contact me via PM, because there is no time to respond to them. No friend requests. Thank you.

4th December 2019, 09:20 #11
 Join Date
 Mar 2003
 Posts
 309
 Helped
 21 / 21
 Points
 4,983
 Level
 16

4th December 2019, 13:02 #12
 Join Date
 Nov 2012
 Posts
 3,237
 Helped
 806 / 806
 Points
 17,748
 Level
 32
Re: fastest multiplication alghorithms
I vote for a big lookup table...
For the slowest method (school book way) it is just 8 shifts and 8 additions.

4th December 2019, 17:18 #13
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,375
 Helped
 1730 / 1730
 Points
 31,868
 Level
 43
Re: fastest multiplication alghorithms
...and every stage of that shift and add can be pipelined to run at very high clock frequencies. Depending on how much pipelining is done you will have increased latency for the first output but you will get all successive outputs on every clock cycle.
Also unlike the RAM this is scalable in an FPGA, i.e. a 32x32 multiply no problem just more pipeline latency. a look up table for 2^32x2^32 bits won't fit in any FPGA.
   Updated   
One of the methods to reduce the latency of a multiplier is to perform radix lookups for multiple bits of the calculation. This is primarily how most of the hard IP multipliers are designed in processors along with pipelining the multiplier.
That is how the original Pentium multiplication error was introduced due to a miscalculated Radix4 entry.
1 members found this post helpful.

Today, 03:59 #14
 Join Date
 Nov 2012
 Posts
 3,237
 Helped
 806 / 806
 Points
 17,748
 Level
 32
Re: fastest multiplication alghorithms
That is how the original Pentium multiplication error was introduced...
Wikipedia has a nontechnical article: https://en.wikipedia.org/wiki/Pentium_FDIV_bug
+ Post New Thread
Please login