First some vocabulary : when you divide a by b to get c, a is the dividend
, b is the divisor
and c is the quotient
. You may also have a remainder
PaynenDiaz's writeup is interesting, but there are I feel 2 things missing from it :
what happens when the divisor doesn't divide the dividend?
how to choose the rows to mark
The answer to the first question is easy. All that this method is doing is expressing the quotient
as the sum
s of 2, ie writing it out in base 2
. This means we are looking for numbers a,b,c,d ... that are 1 or 0 such that (a + 2b +4c +8d...) * divisor
In the case where the divisor
does not divide
there are no number a,b,c,d,... satisfying the above equality. What this boils down to is, no matter how you choose the rows to mark off, their sum will never
be the the dividend.
This makes the need for a systematic (and if possible fast) way to choose the rows necessary : If sometimes it isn't possible to choose the right rows we don't want to spend all day fiddling with them. I am going to propose a method and then explain why it works :
working from the bottom row up :
- Keep a note of the total of the marked rows.
if marking the current row would cause the sum of the marked rows to exceed the dividend, skip this row.
if not, mark it and move to the next row.
stop when the total is the dividend, or when you have run out of rows.
If at the end, the total of the marked rows is not the dividend, then the divisor did not divide the dividend. If it is, then you have your marked rows, and thus the quotient. To give a concrete example, i'll use PaynenDiaz's example of 13188 divided by 314
the rows are :
Note that we can verify PaynenDiaz
's comment that the bottom row is always marked, as we start with that row, and that it is less than the dividend by definition:
we mark 10048.
adding 5024 would put us over 15000 so we skip it.
adding 2512 is fine, we mark it, the total is now 12560.
adding 1256 would put us at 13816, so we skip it.
adding 628 puts us at 13188, which is fine, so we mark the row and stop there.
Now for why it works
The fundamental reason is the existance of a euclidean division for integers. What this means is that for any positive integers a and b, there exists a unique pair of integers q and r, with 0<=r<b such that a= bq +r.
But so what ?
Lets go back to what we are trying to do. In our example we start by seeing if 10048 is too big. What too big means is can I have 13188 = 1 * 10048 + r, with r obeying the conditions above. The answer is obviously yes, so what we have is
a=13188, b= 10048, r=3140
In the method I gave, you keep a running total of the marked rows. This is equivalent to subtracting the marked rows from the dividend at each step, except of course that addition is slightly easier than subtraction. The value of r is what you would have obtained had you done that subtraction.
And now ?
Do it again !
3140 = 0*5024 + 3140 b=0, don't mark the row
3140 = 1*2512 + 628 mark the row
628 = 0*1256 + 628 don't mark the row
628 = 1*628 + 0, mark the row and the remainder is 0 so stop
The marked rows are 10048, 2512 and 628
In a more abstract case, the euclidean division means that we will be able to keep on repeating these step with all the numbers on our rows (and the failure case is when after the last row the remainder is non null)
But why did the Egyptians bother with all this stuff ?
That's not what I was taught at school!
The method you were taught at school is basically the same. You take the divisor, take a certain number of digits off the dividend, and see how many times the divisor goes into it.
What makes the Egyptian method easy and our method difficult is that we are in base 10 and they are in base 2. This means that in our system the b in the euclidean division is anywhere between 0 and 9, whereas in their system b is always 0 or 1, and those are the easiest numbers to multiply by.
I have no idea if this is how the Egyptians actually did it, this is just what I came up with when I read the above writeup.