Long Division - My Method


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:

Divide 13 into 1654 Binary: 1101 (Divisor) into 11001110110 (Dividend)
As with the traditional method we check to see if 1101 is greater than 1100 since it is not we assume 11001. In Binary we know the extra digit is going to be greater.
The Quotient is created by placing a one in the position where the 1101s are concatenated. The Divisor is multiplied by the Quotient and subtracted from the original Dividend giving a new Dividend.
The process then repeats until a result is less than the Divisor, this becomes the Remainder.
Subtract
(Dividend)
Addition
(Quotient)
Comments
11001 1101 10
-1101 1101 00
1100 0000 10
1 0001 00First Iteration
11000 0001 0
-1101 1101 0
1010 0100 0
1 0001 0Second Iteration
10100 1000
-1101 1101
110 1011
1 0001Third Iteration
1101011
-1101000
11
1000Fourth Iteration
When the digits are equal only a single Divisor can be used
11
1111111Final 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 09First Iteration
52 74972
-52 00000
74972
4 00000Second 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 0Third Iteration
93 22
-91 91
1 31
7 07Fourth Iteration
13 1
-13 0
1
1 0Fifth Iteration
When the result is identical to the trial digits the Divisor is not concatenated.
1
9496676Final 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 2First 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 1Second Iteration
Start over in the addition column
9 0 0 0 1
-9 0 0 0 0
1
1 0 0 0 0Third Iteration
The equal rule applies here
1
21111Final 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
Webmaster: Ulrich (Ulie) Sondermann usondermann@earthlink.net
© copyright 1996, 1997, 1998, 1999, 2000