How computer multiplies 2 numbers?

Question

How does a computer perform a multiplication on 2 numbers say 100 * 55.

My guess was that the computer did repeated addition to achieve multiplication. Of course this could be the case for integer numbers. However for floating point numbers there must be some other logic.

Note: This was asked in an interview.

Answer 1

Repeated addition would be a very inefficient way to multiply numbers, imagine multiplying 1298654825 by 85324154. Much quicker to just use long multiplication using binary.

1100100 0110111 ======= 0000000 -1100100 --1100100 ---0000000 ----1100100 -----1100100 ------1100100 ============== 1010101111100 

For floating point numbers scientific notation is used.

100 is 1 * 10^2 (10 to the power of 2 = 100) 55 is 5.5 * 10^1 (10 to the power of 1 = 10) 

To multiply them together multiply the mantissas and add the exponents

= 1 * 5.5 * 10^(2+1) = 5.5 * 1000 = 5500 

The computer does this using the binary equivalents

100 = 1.1001 * 2^6 55  = 1.10111* 2^5 -> 1.1001 * 1.10111 * 2^(6+5) 

Answer 2

The method that is usually used is called partial products like humans do, so for example having 100*55 it would do something like

  100 X    55  ----   500 +  500  ---- 

Basically old approaches used a shift-and-accumulate algorithm in which you keep the sum while shifting the partial products for every digit of the second number. The only problem of this approach is that numbers are stored in 2-complement so you can't do a plain bit per bit multiplication while shifing.

Nowaday most optimization are able to sum all the partials in just 1 cycle allowing you to have a faster calculation and a easier parallelization.

Take a look here: http://en.wikipedia.org/wiki/Binary_multiplier

In the end you can find some implementations like

• Wallace Tree
• Dadda Multiplier
• Booth Encoding