While trying to speed up binary division of very large numbers( 100+ digits), I tried several ideas and ended up with the one I am demonstrating here.
Example:
| Subtract (Dividend) | Addition (Quotient) | Comments |
|---|---|---|
| 11001 1101 10 -1101 1101 00 1100 0000 10 | 1 0001 00 | First Iteration |
| 11000 0001 0 -1101 1101 0 1010 0100 0 | 1 0001 0 | Second Iteration |
| 10100 1000 -1101 1101 110 1011 | 1 0001 | Third Iteration |
| 1101011 -1101000 11 | 1000 | Fourth Iteration When the digits are equal only a single Divisor can be used |
| 11 | 1111111 | Final Iteration Add all the digits in the Addition Column, this is the Quotient The Remainder is in the Subtract Column |
The end result is that 11001110110 divided by 1101 = 1111111 remainder 11.
This also works for any base. A few tricks must be observed for higher bases.
Example:
123456789 divided by 13
| Subtract (Dividend) | Addition (Quotient) | Comments |
|---|---|---|
| 123 45 67 89 -118 18 18 17 5 27 49 72 | 9 09 09 09 | First Iteration |
| 52 74972 -52 00000 74972 | 4 00000 | Second Iteration When the result is identical to the trial digits the Divisor is not concatenated. |
| 74 97 2 -65 65 0 9 32 2 | 5 05 0 | Third Iteration |
| 93 22 -91 91 1 31 | 7 07 | Fourth Iteration |
| 13 1 -13 0 1 | 1 0 | Fifth Iteration When the result is identical to the trial digits the Divisor is not concatenated. |
| 1 | 9496676 | Final Iteration Add all the digits in the Addition Column, this is the Quotient The Remainder is in the Subtract Column |
One more example to demonstrate a new rule. This only applies to bases greater than 2.
Example:
190000 divided by 9
| Subtract (Dividend) | Addition (Quotient) | Comments |
|---|---|---|
| 19 0 0 0 0 -19 9 9 9 8 - 00 9 9 9 8 | 2 2 2 2 2 | First Iteration It is possible here to get into negative numbers. The best approach is to decrease the quotient by 1 |
| 19 0 0 0 0 -9 9 9 9 9 9 0 0 0 1 | 1 1 1 1 1 | Second Iteration Start over in the addition column |
| 9 0 0 0 1 -9 0 0 0 0 1 | 1 0 0 0 0 | Third Iteration The equal rule applies here |
| 1 | 21111 | Final Iteration Add all the digits in the Addition Column, this is the Quotient The Remainder is in the Subtract Column |
My method requires less steps over the traditional long division method. This is very helpful when programming the manipulation of very large numbers with 100+ digits.
Last updated: 12/5/2000