32

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.

lc.
  • 113,939
  • 20
  • 158
  • 187
ckv
  • 10,539
  • 20
  • 100
  • 144
  • 5
    of course not, check out [multiplication algorithm](http://en.wikipedia.org/wiki/Multiplication_algorithm) – Nick Dandoulakis Jun 17 '10 at 08:39
  • So you mean to say depending on the length or value of numbers different algorithms will be used. – ckv Jun 17 '10 at 08:40
  • [How modern X86 processors actually compute multiplications?](https://stackoverflow.com/q/26370287) - Dadda trees. https://en.wikipedia.org/wiki/Dadda_multiplier. Multiply of fixed-width integers (e.g. 32 or 64-bit) is constant-time in modern mainstream CPUs, e.g. 3 cycle latency fully pipelined (1 per clock) for scalar integer multiply on modern x86. [x86\_64: is IMUL faster than 2x SHL + 2x ADD?](https://stackoverflow.com/q/37925143) / [How many CPU cycles are needed for each assembly instruction?](https://stackoverflow.com/q/692718) – Peter Cordes Mar 02 '23 at 02:35

9 Answers9

40

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)
Community
  • 1
  • 1
David Sykes
  • 48,469
  • 17
  • 71
  • 80
17

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

Jack
  • 131,802
  • 30
  • 241
  • 343
  • So there is no one way or algorithm that is used in a processor in a computer. depending on the data different algorithm is selected. Please correct me if i am wrong. – ckv Jun 17 '10 at 08:43
  • Even in this way, you still have to multiply 100x5 twice isnt it ? – bragboy Jun 17 '10 at 08:46
  • In decimal you have to multiply 100*5 and 10*5, but in binary you multiply by 1 or 0, which means you add it or you don't. – David Sykes Jun 17 '10 at 09:26
6

One way is using long multiplication, in binary:

       01100100 <- 100
     * 00110111 <- 55
     ----------
       01100100
      01100100
     01100100
   01100100
  01100100
---------------
  1010101111100 <- 5500

This is sometimes called the shift and add method.

Steven Evers
  • 16,649
  • 19
  • 79
  • 126
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
5

Okay, here ya go. I wrote this a while back (1987!), so some things have changed while others remain the same...

http://moneybender.com/transactor_article.pdf

Don Branson
  • 13,631
  • 10
  • 59
  • 101
  • 1
    Nice article, very helpful – Nick Mar 04 '14 at 18:06
  • 2
    Please include a summary of the article in your response, links might break in the future. – JohannesB Aug 31 '20 at 02:05
  • 1
    It's a link to the article: "High-speed Integer Multiples and Divides" by Donald A. Branson. It appeared in The Transactor (Volume 8, Issue 01, Page 42) in July 1987. You can also find a copy here: https://archive.org/details/transactor-magazines-v8-i01/page/n43/mode/2up – Keeler Oct 02 '22 at 07:25
3

Computers use Booth's algorithm or other algorithms that do shifting and adding for arithmetic operations. If you had studied computer architecture courses, books on computer architecture should be a good place to study these algorithms.

vpit3833
  • 7,817
  • 2
  • 25
  • 25
2

To multiply two floating point numbers the following procedure is used:

  1. Multiply the mantissas
  2. Add the exponents
  3. Normalise the result (decimal point comes after first non zero digit)

So, in base 10 to multiply 5.1E3 and 2.6E-2

Multiply the mantissas => 5.1 * 2.6 = 13.26 (NB this can be done with integer multiplication as long as you track where the decimal point should be)

Add the exponents => 3 + -2 = 1

Gives us a result of 13.26E1

Normalise 13.26E1 => 1.326E2

JeremyP
  • 84,577
  • 15
  • 123
  • 161
1

Intuitively you can minimise repeated additions by also using shifting.

In terms of floats this article looks pretty relevant:

http://oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_14/CH14-1.html#HEADING1-19

Matt Mitchell
  • 40,943
  • 35
  • 118
  • 185
1

The answer is, it depends. As others have pointed out, you can use the same algorithm as we were taught in school, but using binary instead. But for small numbers there are other ways.
Say that you want to multiply two 8 bit numbers, this can be done with a big lookup table. You just concatenate the two 8 bit numbers to form a 16 bit number and use that nunber to index into a table with all the products.
Or, you can just have a big network of gates that computes the function in a direct way. These gate network tend to get quite unwieldy for multiplication of large numbers though.

augustss
  • 668
  • 4
  • 4
1

I just code a simple program multiply two number stored in 2 line in file using algorithm long multiplication. It can multiply two number which have more than 1 billion number in each other

Example: 

            23958233
            5830 ×
         ------------
            00000000  ( =      23,958,233 ×     0)
           71874699   ( =      23,958,233 ×    30)
          191665864   ( =      23,958,233 ×   800)
         119791165    ( =      23,958,233 × 5,000)

Source code:

Please review and give your comment http://code.google.com/p/juniormultiply/source/browse/#svn/trunk/src

NguyenDat
  • 4,129
  • 3
  • 46
  • 46