+ Post New Thread
Results 1 to 13 of 13
  1. #1
    Full Member level 5
    Points: 4,983, Level: 16

    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?

  2. #2
    Full Member level 3
    Points: 1,175, Level: 7
    FlyingDutch's Avatar
    Join Date
    Dec 2017
    Location
    Bydgoszcz - Poland
    Posts
    151
    Helped
    21 / 21
    Points
    1,175
    Level
    7

    Re: fastest multiplication alghorithms

    Quote Originally Posted by Zerox100 View Post
    Hi,

    What do you think is the fastest multiplication alghorithms in the world?
    Hello,

    what datatype do you mean ?

    Regards
    Last edited by FlyingDutch; 2nd December 2019 at 15:19.



    •   AltAdvertisement

        
       

  3. #3
    Full Member level 5
    Points: 4,983, Level: 16

    Join Date
    Mar 2003
    Posts
    309
    Helped
    21 / 21
    Points
    4,983
    Level
    16

    Re: fastest multiplication alghorithms

    Quote Originally Posted by FlyingDutch View Post
    Hello,

    what datatype do you mean ?

    Regards
    unsigned 8 bit



  4. #4
    Super Moderator
    Points: 78,934, Level: 68
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster 3rd Helpful Member

    Join Date
    Apr 2014
    Posts
    16,017
    Helped
    3631 / 3631
    Points
    78,934
    Level
    68

    Re: fastest multiplication alghorithms

    Hi,

    I vote for a big lookup table.

    Klaus
    Please donīt contact me via PM, because there is no time to respond to them. No friend requests. Thank you.



    •   AltAdvertisement

        
       

  5. #5
    Full Member level 3
    Points: 1,175, Level: 7
    FlyingDutch's Avatar
    Join Date
    Dec 2017
    Location
    Bydgoszcz - Poland
    Posts
    151
    Helped
    21 / 21
    Points
    1,175
    Level
    7

    Re: fastest multiplication alghorithms

    Quote Originally Posted by KlausST View Post
    Hi,

    I vote for a big lookup table.

    Klaus
    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.

    Regards
    Last edited by FlyingDutch; 2nd December 2019 at 17:20.


    1 members found this post helpful.

    •   AltAdvertisement

        
       

  6. #6
    Full Member level 5
    Points: 4,983, Level: 16

    Join Date
    Mar 2003
    Posts
    309
    Helped
    21 / 21
    Points
    4,983
    Level
    16

    Re: fastest multiplication alghorithms

    Quote Originally Posted by FlyingDutch View Post
    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.

    Regards
    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.



  7. #7
    Super Moderator
    Points: 78,934, Level: 68
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster 3rd Helpful Member

    Join Date
    Apr 2014
    Posts
    16,017
    Helped
    3631 / 3631
    Points
    78,934
    Level
    68

    Re: fastest multiplication alghorithms

    Hi,

    Do you recognize that you jump from one requirenent to the other.
    unsigned 8 bit
    24 bit multiplier
    32 bit floating point
    I want a 4 step pipelined multiplier.
    four or six stage pipelined multiplier.
    I recommend to take some time to find a clear requirement.

    Klaus
    Please donīt contact me via PM, because there is no time to respond to them. No friend requests. Thank you.



  8. #8
    Full Member level 5
    Points: 4,983, Level: 16

    Join Date
    Mar 2003
    Posts
    309
    Helped
    21 / 21
    Points
    4,983
    Level
    16

    Re: fastest multiplication alghorithms

    Quote Originally Posted by KlausST View Post
    Hi,

    Do you recognize that you jump from one requirenent to the other.






    I recommend to take some time to find a clear requirement.

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



  9. #9
    Advanced Member level 2
    Points: 3,557, Level: 14

    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



  10. #10
    Super Moderator
    Points: 78,934, Level: 68
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster 3rd Helpful Member

    Join Date
    Apr 2014
    Posts
    16,017
    Helped
    3631 / 3631
    Points
    78,934
    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))


    Klaus
    Please donīt contact me via PM, because there is no time to respond to them. No friend requests. Thank you.



  11. #11
    Full Member level 5
    Points: 4,983, Level: 16

    Join Date
    Mar 2003
    Posts
    309
    Helped
    21 / 21
    Points
    4,983
    Level
    16

    Re: fastest multiplication alghorithms

    Quote Originally Posted by KlausST View Post
    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))


    Klaus

    Hi
    Thanks for your attention

    You are right. I was initially looking for fast multiplier. But Now i am looking for fast throughput pipelined multiplier.



    •   AltAdvertisement

        
       

  12. #12
    Advanced Member level 5
    Points: 17,748, Level: 32
    Achievements:
    7 years registered

    Join Date
    Nov 2012
    Posts
    3,236
    Helped
    806 / 806
    Points
    17,748
    Level
    32

    Re: fastest multiplication alghorithms

    I vote for a big lookup table...
    For 8 bit unsigned int, you will need a table 256X256 in size. The products shall need 16 bit storage.

    For the slowest method (school book way) it is just 8 shifts and 8 additions.



  13. #13
    Super Moderator
    Points: 31,868, Level: 43
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    7,375
    Helped
    1730 / 1730
    Points
    31,868
    Level
    43

    Re: fastest multiplication alghorithms

    Quote Originally Posted by c_mitra View Post
    For the slowest method (school book way) it is just 8 shifts and 8 additions.
    ...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 Radix-4 entry.


    1 members found this post helpful.

--[[ ]]--