Egyptian division and proportion tables

Let us repeat the problem of the last posting, but solve it exactly using Egyptian division.  Egyptian division employs two columns of numbers that form a proportion table.  It does not require knowledge of times tables---knowing how to double suffices.  Nor does it require guess and check estimation of multiplies usually employed with the standard long division algorithm.  The disadvantage is that the calculation is roughly three times as long as for the standard algorithm. 

We can start just as we did for approximate division in the last posting :

`\qquad\qquad\qquad[(1543, x),(21, 1)]`.

To this, double the last row and append, double the last row and append, continuing until the numbers at the bottom of the first column bracket `1543`, i.e. `1344 < 1543 < 2688` :

`\qquad\qquad\qquad[(1543, x),(21, 1),(42,2),(84,4),(168,8),(336,16),(672,32),(1344,64),(2688,128)]`.

Now we start add the bottom, succesively adding some rows but not others, trying to make `1543`.  `2688` is already too big, so we ignore it.  (In practice, we could usually forsee this and do not write that row in the first place.)  The next row up, led by `1344` is smaller than 1543, and contributes.

`\qquad\qquad\qquad[(1543, x),(21, 1),(42,2),(84,4),(168,8),(336,16),(672,32),(1344,64)]`.

The next row up, led by `1344` is smaller than `1543`, so that row contributes, as it always does. We still have `1543 - 1344 = 199` to account for.  `672` and `336` are both bigger than `199`, so those rows do not contribute, and can be ignored.  `168` is smaller, so it contributes, leaving `199 - 168 = 31` to account for. `84` and `42` are larger than `31`, so those rows do not contribute.  `21` is smaller, so that row contributes, and leaves a remainder is `31 - 21 = 10`.

On paper, we would strike out the rows to be ignored: here we delete them all.

`\qquad\qquad\qquad[(1543, x),(21, 1),(168,8),(1344,64)]`.

Now, we append the sum of the bottom three rows :

`\qquad\qquad\qquad[(1543, x),(21, 1),(168,8),(1344,64), (21+168+1344,1+8+64)] = [(1543, x),(21, 1),(168,8),(1344,64), (1533,73)]`.

In practice, again, we would not perform the sum `21 + 168 + 1344 =1533`.  We do not need it, and even if we did, it is more readily calculated by subtracting the remainder from our original dividend, `1543 - 10 = 1533`.

We do have to perform `1+8+64 = 73`, however, to get the quotient `73`.

So we have, `1543 -: 21 = 73 " remainder "10`.

So far, we have performed divmod division, i.e. found an integer quotient and a remainder.  (div and mod are two convenient computer arithmetic terms. div gives only the integer quotient, `1543 " div " 21 = 3`, while mod gives only the remainder,`1543 " mod " 21 = 10`.)

Using wiggle notation, we can write :

`\qquad\qquad1543 -: 21 = 73;_{21}10 = 73 10/21`.

where now we are looking at the result as a mixed fraction.

It is easy to extend Egyptian division so that it gives us a decimal fraction result to any desired degree of accuracy, as we shall see in the next post.