Multiplication Algorithm

[saeddawoud]

Hello
what are the different algorithms for the binary multiplication in computer systems, if possible from the beginning to today's algorithm??
Regards

 

[A.Anand Srinivasan]

the main and the most simple one is repetitive addition.....
there are some more algorithms like booth multiplier, modified booth multiplier etc etc which on much more reduced number of clock cycles but are complex,,,,,

 

[saeddawoud]

hello
that is nice, but what are the algorithms(details)? any resources?
Regards

 

[A.Anand Srinivasan]

lots of algorithms and multipliers have been developed off late..... each progressively reducing the number of clock ticks used for multiplication.... refer ieee papers if possible......


visit this link.... it has not a detailed one but small info on some commonly used multipliers...
**broken link removed**

 

[neoaspilet11]

Most of modern arithmetic computing is done through either floating point or fixed point arithmetic.

Multiplications, particulary real numbers multiplication not just integer multiplications are primarily done by floating point multiplications.


Most of modern computing devices have hardware multipliers that basically performs repetitive binary additions in few clock cycles. These hardware multipliers are then used by multiplier softwares to perform specific multiplication algorithms.

There are a lot out there how arithmetic algorithms are carried out to fit into various computing devices architecture.

 

[sam536]

currently,in most of the processors are implementing modified Booths algorithm and Wallace mulitiplier algorithm . Algorithm slection depends on the latency and througput expected from the output of the circuit...

--Sam

 

[saeddawoud]

hello
actually, I need to understand the second version algorithm in Henessey and Patterson book: Computer Organization and Design: Hardware/Software Interface, 2nd edition, where the Multiplier register is 32 bits, the Multiplicand register is 32 bits, the ALU is 32 bits, and the Product register is 64 bits, here we shift right the Multiplier and the Product each iteration by one bit, but why? I couldn't understand it completely.
Regrads

 

[A.Anand Srinivasan]

it is just normal multiplication.... the shifting of product is to carry out the operation of our shift and add of the partial product...
see the example below it will be clear....
356
X 11
-------
356
356 <-shifting of partial product for the sake of addition
--------
3916


if the lsb of multiplier is a 1 then the multiplicand is added else nothing is added and multiplier is shifted so that the next number(msb next to it) can be checked