- Joined
- Jul 10, 2007
- Messages
- 6,306
The following steps are always taken. This is a more general form of long division in which no guesses are taken. It is most likely you will guess too high, but that is fine.
At later points in the algorithm, if the length of the number on the left is less than the length of 31, which is 2, then add 0 to the quotient and put another digit from the dividend into the number. This is true until there are no digits remaining in the dividend, at which point the number on the left becomes the remainder. The running time of this algorithm is O(n^2).
edit
Here's an improved version of the algorithm that gets the number in regular form from the get-go
edit
If numerator < denominator, then answer is 0 remainder numerator. Not doing this will get you a negative remainder that's quite a bit larger than the denominator : P. You'd have to form more division in order to get the number to the correct answer.
At later points in the algorithm, if the length of the number on the left is less than the length of 31, which is 2, then add 0 to the quotient and put another digit from the dividend into the number. This is true until there are no digits remaining in the dividend, at which point the number on the left becomes the remainder. The running time of this algorithm is O(n^2).
Code:
Solve 18225/31
18225 / 31
Dividend Remaining Dividend Quotient
18225 18225
0 < 3? Yes
1 < 3? Yes 8225
18 < 3? No 225
18/3 = 6 6
6*31 = 186
len(18) = len(186)? No 25
len(182) = len(186)? Yes
182-186 = -4
-40 + 2 = -38 5
-3/3 = -1 -1
-1*31 = -31
-38 - -31 = -7
-70 + 5 = -65 _
-6/3 = -2 -2
-2*31 = -62
-68 - -62 = -3
No Digits Remaining r-3
Answer: 6,-1,-2,r-3
6 - 1 = 5
-1 + 10 = 9
5,9,-2,r-3
9 - 1 = 8
-2 + 10 = 8
5,8,8,r-3
8 - 1 = 7
-3 + 31 = 28
5,8,7,r28
Answer: 587r28
edit
Here's an improved version of the algorithm that gets the number in regular form from the get-go
Code:
18225 / 31
18/3 = 6*
6*31 = 186
182
186 -
-4
-4 < 0
6* - 1 = 5*
-4 + 31 = 27
27/3 = 9*
9*31 = 279
272 - 279 = -7
-7 < 0
9* - 1 = 8*
-7 + 31 = 24
24/3 = 8*
8*31 = 248
245 - 248 = -3
-3 < 0
8* - 1 = 7*
-3 + 31 = 28
No digits remaining,
587r28
edit
If numerator < denominator, then answer is 0 remainder numerator. Not doing this will get you a negative remainder that's quite a bit larger than the denominator : P. You'd have to form more division in order to get the number to the correct answer.
Last edited: