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.
Repeated addition would be a terrible 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.
e.g.
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 manitssas 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)
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
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
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.
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.
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.
To multiply two floating point numbers the following procedure is used:
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
Okay, here ya go. I wrote this a while back (1987!), so some things have changed while others remain the same...
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