How does a computer multiply two numbers. For instance, if I give it the numbers 37 and 41 and asked it to multiply these together how would it accomplish this?

Question

e.mccormick · Answer

It depends on the numbers and their type.  Computers and calculators originally just added that many times.  Now, well, they use an assortment of tools. In general, it does simpler forms of multiplication, shifts the decimals as needed, and does addition.  Look into a shift register and binary multiplication for more on this.  But if I recall, there are differences when it comes to floating point numbers that are there to account for the binary inaccuracy and estimation.

Let me give an example for that inaccuracy.  I'll use base 10 numbers to start because you know them.

In decimal format with three places, $\dfrac{1}{3}$ rounds to .333 and $\dfrac{2}{3}$ rounds to .667.  Now lets do some addition $\dfrac{1}{3}+\dfrac{1}{3}=\dfrac{2}{3}$  but $.333+.333=.666\ne .667$.  So we have a problem because of the rounding error.

The same thing happens with binary number, or base 2.  Because of this, there are complexities in floating point multiplication that have to do with rounding errors that are compounded a second time through the translation from base 2 to base 10 decimals.

kainui · Answer

I suppose I should have been specific in that I'd like to know bit for bit what's happening during a multiplication. This is a little too vague I'm afraid.

Like for instance if I want to multiply by 2 I know I could just shift the bits to the left, but if I want to multiply by 3 I'm a little bit at a loss of how i might do that.

queelius · Answer

The same way you do long multiplication (except simpler), but with binary digits.

5 * 3 = 15

  101 
    11
  ---
  101
1010
-----
1111 = 15

queelius · Answer

There are, undoubtedly, many optimizations available, but the long multiplication (and long division) you learned in grade-school is a perfectly legitimate algorithm.

Note that this is also how arbitrary precision arithmetic (up to the memory limitations of the computer) is also done.

e.mccormick · Answer

Here is a more detailed example: http://www.eecg.toronto.edu/~ahouse/mirror/engi3861/multiplier_example_web.pdf