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 :

${\displaystyle \left[\begin{array}{cc}1543& x\\ 21& 1\end{array}\right]}$.

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 ${\displaystyle 1543}$, i.e. :

${\displaystyle \left[\begin{array}{cc}1543& x\\ 21& 1\\ 42& 2\\ 84& 4\\ 168& 8\\ 336& 16\\ 672& 32\\ 1344& 64\\ 2688& 128\end{array}\right]}$.

Now we start add the bottom, succesively adding some rows but not others, trying to make ${\displaystyle 1543}$.  ${\displaystyle 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 ${\displaystyle 1344}$ is smaller than 1543, and contributes.

${\displaystyle \left[\begin{array}{cc}1543& x\\ 21& 1\\ 42& 2\\ 84& 4\\ 168& 8\\ 336& 16\\ 672& 32\\ 1344& 64\end{array}\right]}$.

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

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

${\displaystyle \left[\begin{array}{cc}1543& x\\ 21& 1\\ 168& 8\\ 1344& 64\end{array}\right]}$.

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

${\displaystyle \left[\begin{array}{cc}1543& x\\ 21& 1\\ 168& 8\\ 1344& 64\\ 21+168+1344& 1+8+64\end{array}\right]=\left[\begin{array}{cc}1543& x\\ 21& 1\\ 168& 8\\ 1344& 64\\ 1533& 73\end{array}\right]}$.

In practice, again, we would not perform the sum ${\displaystyle 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, ${\displaystyle 1543-10=1533}$.

We do have to perform ${\displaystyle 1+8+64=73}$, however, to get the quotient ${\displaystyle 73}$.

So we have, .

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, , while mod gives only the remainder,.)

Using wiggle notation, we can write :

${\displaystyle 1543÷21=73{;}_{21}10=73\frac{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.