Wednesday, February 24, 2010

Egyptian division prolonged---fractions

Last time, we used Egyptian division to find a whole number quotient and a remainder for the division `1543 -: 21`, in the process formed the table

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

To calculate the fractional part in decimal form, we begin by subtracting the last row from the first, and append the result at the bottom:

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

In practice, of course, don't actually subtract, but just write the remainder we have already found, and that same remainder divided by the divisor in fractional form in the next column.

Now we take the divisor row, `[21, 1]`, halve it to get `[10.5, 0.5]`, and append at the bottom :

`\qquad\qquad\qquad[(1543, x),(21, 1),(168,8),(1344,64), (1533,73), (10, 10/21),(10.5, 0.5)]`.

We now continue, halving the bottom row and appending, halving the bottom row and appending, until the second number in the bottom row is comparable to the accuracy we require.  Suppose we want the fractional part of the quotient to be accurate to two decimal places, then :

`\qquad\qquad\qquad[(1543, x),(21, 1),(168,8),(1344,64), (1533,73), (10, 10/21),(10.5, 0.5), (5.25, 0.25), (2.625, 0.125), (1.3125,0.0625), (0.65625,0.03125), (0.328125,0.015625), (0.1640625, 0.0078125)]`.

We now make a sum as close as we can to the `10` in the target row `[10, 10/21]`, by adding together some of the rows below it.  `10.5` is larger than `10`, so we ignore that row.  `5.25` is smaller, so that row get used.  `10 - 5.25 = 4.75` left to account for. This is larger than `2.625`, so we use that row too, leaving `4.75 - 2.625 = 2.125` to account for.  Continuing, `2.125 - 1.3125 = 0.8125`; `0.8125 - 0.65625 = 0.15625`; skip `0.328125`.  For the last entry, we perform the subtraction, even though the result is negative, `0.15625 - 0.1640625 = -0.0078125`.  The reason is that it leaves an error `-0.0078125` that is smaller in magnitude than the error we would have without the subtraction, i.e. `0.1640625`. This gives us more accuracy than we expected.

Deleting (or striking out) the rows to be ignored, we get :

`\qquad\qquad\qquad [(1543, x),(21, 1),(168,8),(1344,64), (1533,73), (10, 10/21),(5.25, 0.25), (2.625, 0.125), (1.3125,0.0625), (0.65625,0.03125), (0.1640625, 0.0078125)]`.

Adding the contributing rows, we get

`5.25+2.625+1.3125+0.65625+0.1640625 = 10.0078125`,

(or, easier, `10 - -0.0078125 = 10.0078125`) and

`0.25+0.125+0.0625+0.03125+0.0078125 = 0.4765625`,

so the table finally becomes

`\qquad\qquad\qquad [(1543, x),(21, 1),(168,8),(1344,64), (1533,73), (10, 10/21),(5.25, 0.25), (2.625, 0.125), (1.3125,0.0625), (0.65625,0.03125), (0.1640625, 0.0078125),(10.0078125, 0.4765625)]`.

Since `10.0078125` is within a tenth of a percent of `10`, we must have that `0.4765625` is within a tenth of a percent of `10/21`, i.e. `10/21 \approx 0.477`, this compares well with the accurate answer of `0.476190...`  i.e. we have almost three decimal places of accuracy.

So `1543/71 \approx 73.477.`

Although it makes relatively few demands in terms of times tables, and this part requires only that we know how to halve decimal quantities, one has to put in considerable labor for each decimal place.

The method is much better adapted to binary fractions than to decimals.  These are sometimes useful, e.g. when one is working to sixteenths or thirty-seconds of an inch, say.  In binary fractions, the final table looks like this,

`\qquad\qquad\qquad [(1543, x),(21, 1),(168,8),(1344,64), (1533,73), (10, 10/21),(5 1/4, 1/4), (2 5/8, 1/8), (1 5/16, 1/16), (21/32,1/32), (21/64, 1/64),(21/128, 1/128),(10 1/128, 61/128)]`,

so that `1543/71 \approx 73 61/128.`

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.

Approximate division using a proportion table

Suppose we are trying to get a roughly estimate of how many times `21` goes into `1543`.  i.e. we are looking to approximate `1543/21`.

We can set this up as an incomplete proportion table :

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

Using the proportion table form of the Rule of Three, we can solve for `x` by multiplying the neighbors and dividing by the opposite corner :

`\qquad\qquad\qquad x = \frac{1543 xx 1}{21}`,

i.e., completing this proportion table correctly should indeed give us exactly the quantity we seek.  But we are not seeking an exact value, and are instead hoping to extract an approximate answer with less work.

First, we multiply the last row by ten and append, and repeat this until the number at the top left of the table is bracketed by the first values on the two last rows, i.e. `210<1543<2100` :

`\qquad\qquad\qquad[(1543, x),(21, 1),(210, 10),(2100, 100)]`.

Since in the first column `210<1543<2100`, we can conclude from the second column that `10 < x < 100`.

To sharpen this estimate a little, we can round `2100` to `2000` and `1543` to `1500`.  Now `1500` is three quarters of `2000`, so `x` is about three quarters of `100`, i.e. `1543/21` is roughly `75`.

Extending a proportion table

So far, we have rearranged proportion tables, we have deleted rows and/or columns, and we have cut proportion tables into smaller pieces.

Now we want to make larger tables.

One way to make a larger table is simply to duplicate a row,

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(4, 8, 10, 18),(6, 12, 15, 27)] `.

or a column,

`\qquad\qquad [(2, 4, 5, 9, 5),(4, 8, 10, 18, 10),(6, 12, 15, 27, 15)] \qquad->\qquad [(2, 4, 5, 9, 5),(4, 8, 10, 18, 10),(6, 12, 15, 27, 15)] `.

or both :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(2, 4, 5, 9, 5),(4, 8, 10, 18, 10),(4, 8, 10, 18, 10),(6, 12, 15, 27, 15)] `

Of course we can duplicate any row or column as many times as we like.  And we can do that to many distinct rows and many distinct columns.

Another way to augment a proportion table is by appending a row that is a multiple of another row.   A multiple of one row is necessarily a multiple (usually by different multipliers) of every row :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27),(60, 120, 150, 270)] `.

It should be clear that the result of appending a multiple row will always still be a proportion table, and mutatis mutandis for columns.

One can always append a column that is a sum of two or more other columns (and mutatis mutandis for rows) :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(2, 4, 5, 9, 5+9),(4, 8, 10, 18,10+18),(6, 12, 15, 27,15+27)] `,

`\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad =  \qquad [(2, 4, 5, 9, 14),(4, 8, 10, 18, 28),(6, 12, 15, 27, 42)]`.

More generally, the result of appending a sum or difference of existing  rows or of columns is another proportion table.

In the last posting, we dealt with subtables and amalgamation.  Amalgamating two rows is equivalent to appending their sum, and deleting the original two rows, and similarly for amalgamating two columns. Any amalgamation whatever of a table (i.e. over a tartanlike decomposition) can be constructed by a suitably chosen succession of amalgamations of pairs of rows and pairs of columns.

Suitable subtle subtables

We can delete, or just simply ignore, arbitrary rows and columns of a given table.  The result is a subtable.  Any subtable of a proportion table is also a proportion table.  Here, we delete the third row, and the first and third columns, of a table to get a subtable :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(4,  9),(8, 18)] `.

In general, making a subtable is a lossy operation---there is less table when we are done.

We can split a table into a complete, nonoverlapping collection of subtables.  For instance :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27), (10, 20, 25, 45)] \qquad->\qquad{: ([(2, \qquad4),(4, \qquad8)]\qquad [(5, 9),(10, 18)]), ([(6, 12),(10, 20)]\qquad [(15, 27),(25, 45)]) :} `.

The preceding patchwork of subtables was made by carving up the original table in an obvious way.  A nonoverlapping collection does not have to fit together like patchwork, however :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27), (10, 20, 25, 45)] \qquad->\qquad{: ([(\quad2, 9),(10, 45)]\qquad [(4, 5),(20, 25)]), ([(\quad4, 18),(\quad6, 27)]\qquad [(8, 10),(12, 15)]) :} `.

The subtables do not have to be square, or the same size, or deployed in a symmetrical pattern.  The most useful decompositions are those that are tartanlike, meaning that any split between cells belonging to distinct subtables goes all the way across the original table.

The two preceding decompositions are tartanlike.  This one is not:

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27), (10, 20, 25, 45)] \qquad->\qquad{: ([(2, \qquad4,\qquad5, 9),(4, \qquad8,\qquad10, 18)]), ([(6, 12),(10, 20)]\qquad [(15, 27),(25, 45)]) :} `.

We have arranged the subtables according to the position of its reference element---by convention its top left element---in the original table.  Using such a convention is no mere convenience, as we shall soon see.

Tartanlike decompositions can be aggregated, by adding together the elements in each subtable :

`\qquad\qquad\qquad{: ([(2, \qquad4),(4, \qquad8)]\qquad [(5, 9),(10, 18)]), ([(6, 12),(10, 20)]\qquad [(15, 27),(25, 45)]) :}\quad->\quad{: ([(),(\qquad18\qquad),()]\quad [(),(\qquad42\qquad),()]), ([(),(\qquad48\qquad),()]\quad [(),(\quad112\qquad),()]) :}`,

where the result can also be written

`\qquad\qquad\qquad[(18,42),(48,112)]`.

Similarly,

`\qquad\qquad\qquad{: ([(\quad2, 9),(10, 45)]\qquad [(4, 5),(20, 25)]), ([(\quad4, 18),(\quad6, 27)]\qquad [(8, 10),(12, 15)]) :}\quad->\quad[(66,54),(55,45)] `,

where the convention we used before helps us keep the aggregated subtables in proportional relation.

A table filled entirely with ones is a proportion table.  By aggregating such a table of suitable size, we can construct any proportion table whatever that has only positive integer elements.  For instance :

`\qquad\qquad\qquad [(1,1,1,1,1,1),(1,1,1,1,1,1),(1,1,1,1,1,1),(1,1,1,1,1,1),(1,1,1,1,1,1),(1,1,1,1,1,1)]\quad->\quad[(1,2,3),(2,4,6),(3,6,9)],

where an appropriate tartanlike decomposition that leads from the first of these tables to the second should be obvious.

These three examples illustrate a general truth: aggregating a proportion table always gives another proportion table.

Turning tables

It is useful to have some operations that turn one proportion table into another.  In this posting, we deal with some operations that can be applied to many different kinds of table, not just proportion tables.

Let's start with the simple operation of swapping (or transposing) two rows, here the second and the third :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(2, 4, 5, 9),(6, 12, 15, 27),(4, 8, 10, 18)] `,

or two columns, here the second and the fourth :

`\qquad\qquad[(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)]  \qquad->\qquad [(2, 9, 5, 4),(4, 18, 10, 8),(6, 27, 15, 12)]`.

Repeatedly transposing various pairs of rows can give every possible reordering (or permutation) of the rows :
 
`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(6, 12, 15, 27),(2, 4, 5, 9),(4, 8, 10, 18)] `,

and similarly for arbitrary column permutations :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(5, 9, 4, 2),(10, 18, 8, 4),(15, 27, 12, 6)] `.

We can combine arbitrary row permutations and arbitrary column permutations to get arbitrary table permutations.  How the rows are reordered is independent of how the columns are reordered.  Combining the most recent row and column reorderings, we get :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(15, 27, 12, 6),(5, 9, 4, 2),(10, 18, 8, 4)] `.

All of the foregoing operations simply rearrange the proportion table to make a proportion table that contains exactly the same information.  When one can make table from another using only rearrangement, the tables are said to be equivalent up to rearrangment.  All of the tables in this posting are equivalent up to permutation---they are in a sense the same `3 xx 4` table, just displayed differently.

Does this account for reliable ways to convert a proportion table to a proportion table?  In much later postings, when we deal with group tables and have more restrictions, the answer will be yes.

Here, however, the answer is no---there are other possibilities.  One such possibility can be made by giving the table a quarter turn, e.g.

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad [(6, 4, 2),(12,8,4),(15,10,5),(27,18,9)] `.

It should be clear that in the rotated version, rows are proportional to rows and columns to columns, as before, i.e. that the rotated version of the original proportion table is also a proportion table.  We could not have made the rotated version from permutations alone or the original, either, because permutations only ever turn a `3 xx 4` table into a `3 xx 4` table, never into a `4 xx 3` table, as this quarter turn has just done.

Of course, this quarter-turned table can now be permuted to give many `4 xx 3` tables, all of which are equivalent up to permutation.  Indeed, there will be as many distinct `4 xx 3` tables are there are distinct `3 xx 4` tables.

Does this exhaust all the possibilities?  What if one makes a quarter turn in the other direction?  It turns out that the two different ways of quarter-turning the original table lead to two tables that differ by a half turn,

`\qquad\qquad\qquad  [(6, 4, 2),(12,8,4),(15,10,5),(27,18,9)] `,

and

`\qquad\qquad\qquad  [(9,18,27),(5,10,15),(4,8,12),(2, 4, 6)] `.

Unlike a quarter turn, a half turn can be made just from permutations:  reverse the order of the rows, and reverse the order of the columns.  In this way, we get

`\qquad\qquad\qquad  [(6, 4, 2),(12,8,4),(15,10,5),(27,18,9)] \qquad->\qquad [(9,18,27),(5,10,15),(4,8,12),(2, 4, 6)] `,

and we also get

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad  [(27,15,12,6),(18,10,8,4),(9,5,4,2)] `.

It should also be mentioned here that rotating by a quarter turn clockwise and reversing the order of the columns (or, alternatively, rotating a quarter of a turn anticlockwise and reversing the order of the rows) is often called transposing the table.

Transposing a table is like flipping a rectangular piece of paper while keeping the original top left corner at the top and left, going from portrait orientation to landscape orientation, or vice versa :

`\qquad\qquad [(2, 4, 5, 9),(4, 8, 10, 18),(6, 12, 15, 27)] \qquad->\qquad  [(2, 4, 6),(4,8,12),(5,10,15),(9,18,27)] `.
 
Transposing in this sense is a little different from transposition as introduced above.  Transposition swaps a pair of rows, or else a pair of columns. Transposing, on the other hand turns all the columns to rows and all the rows to columns, in particular way.

We shall actually have little use either for quarter turns or for transposing, while we are dealing with proportion tables.  Transposing become important when dealing with matrices, which come much later.