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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.