Multiplying and Dividing Computer Style

Date: 09/08/98 at 15:38:35
From: Anonymous
Subject: Dividing by Adding

I was wondering if you could tell me how to divide by adding. I know 
it is possible because the only math that the CPU of a computer can do 
is add. To subtract, it adds negative numbers. To multiply, (8 * 4), 
it adds (8 + 8 + 8 + 8). Somehow it also divides.

Date: 09/09/98 at 08:42:11
From: Doctor Rick
Subject: Re: Dividing by Adding

Hi. This is an interesting question. On the one hand, you are correct
that a CPU multiplies and divides using addition (almost) alone. On 
the other hand, a CPU multiplies and divides in exactly the same way
you were taught.

The reason both of these statements can be true is to be found in 
binary arithmetic. I am assuming you have learned how to do arithmetic 
in other bases, so I won't explain it in detail here. If you want more 
explanation, feel free to ask, or see our bases FAQ at:

  http://mathforum.org/dr.math/faq/faq.bases.html   

When you multiply, you multiply the multiplicand by one digit of the
multiplier at a time. You shift each partial product by one digit, 
then add them.

     483
    * 27
    ----
    3381
    966
   -----
   13041

A computer multiplies in binary. The only difference from what you 
learned is that the binary multiplication table is very simple:

   *|0 1
   -+---
   0|0 0
   1|0 1

That is, if you multiply by 0, the answer is 0. If you multiply by 1, 
the answer is the original number. That's it. So even though the 
computer multiplies normally, in a sense it doesn't multiply - it 
either does nothing (multiplying by 1), or gives 0 (multiplying by 0).

Here is how multiplication works in binary:

    13 = 1101
   * 9 = 1001
   ---   ----
         1101
           0
          0
      1101
      -------
      1110101 = 117

You see that while the computer in a sense multiplies by adding, it 
doesn't do so by adding 13 + 13 + 13 + 13 + 13 +13 + 13 + 13 + 13. 
That would be much slower. And the reason I said that the computer 
multiplies almost by addition alone is that it also uses the operation 
of shifting by one bit, which is the same as multiplying by 2 (just as 
shifting in decimal is the same as multiplying by 10).

Now for division. As with multiplication, the computer uses 
essentially the same algorithm that you learned as long division. 
(There may be some modifications for efficiency, but we don't need to 
go into that.) Here is an example:

             1101
        ---------
   1001 ) 1110101
          1001
          ----
           1011
           1001
           ----
             1001
             1001
             ----
 
Once again, the only difference from what you learned is that the
multiplication table is much simpler. In the case of division, this 
means that it is not necessary to make a guess, multiply it by the 
divisor, subtract it from the last remainder, and see if the result is 
non-negative and less than the divisor. All the computer does is:

    Subtract the divisor from the remainder

    If the result is non-negative, put a 1 in the quotient
    Otherwise, put a 0 in the quotient and undo the subtraction

Still, each bit requires one decision (an "if" statement, in software
terms), which is another operation besides addition and shifting.

All this may be a bit disappointing, because it isn't a different way 
to divide, after all. But it does help to explain the power of binary. 
And you might be a bit jealous of the computer because it didn't have 
to memorize a big multiplication table; but remember, a binary number 
has a lot more digits (bits) than the same number in decimal, so the 
computer still has quite a bit of work to do.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/