NOTES ON BINARY DIVISION BY TEN:
Dividing by 10 is easy...
Move the decimal point one position to the left.
Unfortunately computers don't operate in base 10. They use base 2.
So shifting the binary point will only divide it by 2, not 10.
DIVISION BY REPEATED SUBTRACTION:
Unless speed is absolutely critical the easiest way to do it is simply revert
to what divide represents, repeated substraction.
Simply count the numberof times that you subtract 10 from the sum, and that's the quotient. Whatever is left over is the remainder.
For Example: Sum is 52. Start with q = 0:
Dividing by 10 is easy...
Move the decimal point one position to the left.
Unfortunately computers don't operate in base 10. They use base 2.
So shifting the binary point will only divide it by 2, not 10.
DIVISION BY REPEATED SUBTRACTION:
Unless speed is absolutely critical the easiest way to do it is simply revert
to what divide represents, repeated substraction.
Simply count the numberof times that you subtract 10 from the sum, and that's the quotient. Whatever is left over is the remainder.
For Example: Sum is 52. Start with q = 0:
| QUOTE |
- Subtract 10 and add one to the quotient: Sum = 42 q = 1 - Subtract 10 more Sum = 32 q = 2 - Subtract 10 more Sum = 22 q = 3 - Subtract 10 more Sum = 12 q = 4 - Subtract 10 more Sum = 2 q = 5 |
Since the sum is now less than 10, the divisor, we're now done.
The quotient is 5.
A FASTER WAY BINARY LONG DIVISION:
If speed is critical you can shortcut by taking the divisor and shift it
left one bit until it's just less than the dividend (sum in this case).
You then add the binary multiplier to the quotient and subtract the upshifted
divisor from the dividend.
For example say we expand our sum to 16 bits and the value is 60000.
From the previous example it'll take 6000 subtracts and increments to get the the quotient.
Now check out using the shift and subtract method.
| QUOTE |
| 1) We keep doubling the divisor (10) until the next shift would exceed the dividend (60000) 10>20>40>80>160>320>640>1280>2560>5120>10240>20480>40960. This is 13 shifts so the current multiplier is 4096 which is 2 to the 13 power. Also note that the next shift, to 81920 would exceed the original dividend. 2) We now subtract the expanded divisor from the dividend and add the multipler to the quotient. So afterwords the new dividend will be 19040 and the new quotient is 4096. 3) We then repeat. But instead of starting the 10 over and shifting it up, we simply take the current shifted divisor (40960) and shift it down until it becomes less than the current dividend. So we'd shift down twice 40960->20480->10240 and then update by subtracting the 10240 from the 19040 and add the 1024 (the current multipler) to the quotient. So the dividend becomes 8800 and the quotient becomes 5120 (4096+1024) 4) Repeat until the multipler is 0: |
| CODE |
divisor = 5120 dividend becomes 3680 quotient is 5120+512 -> 5632 divisor = 2560 dividend becomes 1120 quotient is 5632+256 -> 5888 divisor = 1280 dividend remains because the divisor is bigger than the dividend divisor = 640 dividend becomes 480 quotient is 5888+64 -> 5952 divisor = 320 dividend becomes 160 quotient is 5952+32 -> 5984 divisor = 160 dividend becomes 0 quotient is 5984+16 -> 6000 |
We could either stop here because the dividend is 0 or proceed until the
divisor (or the multipler) becomes 0.
Note that we get the same quotient however that instead of 6000 subtracts and increments it only takes 26 (max) shifts, 5 subtracts, and 5 additions which is at least 100 times faster than the original method.