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

            [1543x2111688134464153373].

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:

            [1543x2111688134464153373101021].

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 :

            [1543x211168813446415337310102110.50.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 :

            [1543x211168813446415337310102110.50.55.250.252.6250.1251.31250.06250.656250.031250.3281250.0156250.16406250.0078125].

We now make a sum as close as we can to the 10 in the target row [10,1021], 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 :

            [1543x21116881344641533731010215.250.252.6250.1251.31250.06250.656250.031250.16406250.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

            [1543x21116881344641533731010215.250.252.6250.1251.31250.06250.656250.031250.16406250.007812510.00781250.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 1021, i.e. 10210.477, this compares well with the accurate answer of 0.476190...  i.e. we have almost three decimal places of accuracy.

So 15437173.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,

            [1543x2111688134464153373101021514142581815161162132132216416421128112810112861128],

so that 1543717361128.

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 :

            [1543x211].

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 :

            [1543x211422844168833616672321344642688128].

Now we start add the bottom, succesively adding some rows but not others, trying to make 15432688 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.

            [1543x21142284416883361667232134464].

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.

            [1543x2111688134464].

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

            [1543x211168813446421+168+13441+8+64]=[1543x2111688134464153373].

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 :

        1543÷21=73;2110=731021.

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 154321.

We can set this up as an incomplete proportion table :

            [1543x211].

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 :

            x=1543×121,

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 :

            [1543x211210102100100].

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. 154321 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,

        [24594810186121527]        [24594810184810186121527].

or a column,

        [2459548101810612152715]        [2459548101810612152715].

or both :

        [24594810186121527]        [245954810181048101810612152715]

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 :

        [24594810186121527]        [2459481018612152760120150270].

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) :

        [24594810186121527]        [24595+948101810+18612152715+27],

                                        =     [24591448101828612152742].

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 :

        [24594810186121527]        [4 9818].

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 :

        [2459481018612152710202545]        [2    44    8]    [591018][6121020]    [15272545].

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 :

        [2459481018612152710202545]        [  291045]    [452025][  418  627]    [8101215].

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:

        [2459481018612152710202545]        [2    4    594    8    1018][6121020]    [15272545].

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 :

            [2    44    8]    [591018][6121020]    [15272545]    [    18    ]  [    42    ][    48    ]  [  112    ],

where the result can also be written

            [184248112].

Similarly,

            [  291045]    [452025][  418  627]    [8101215]    [66545545],

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 :

            [111111111111111111111111111111111111]    [123246369],

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 :

        [24594810186121527]        [24596121527481018],

or two columns, here the second and the fourth :

        [24594810186121527]         [29544181086271512].

Repeatedly transposing various pairs of rows can give every possible reordering (or permutation) of the rows :
 
        [24594810186121527]        [61215272459481018],

and similarly for arbitrary column permutations :

        [24594810186121527]        [59421018841527126].

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 :

        [24594810186121527]        [15271265942101884].

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×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.

        [24594810186121527]        [64212841510527189].

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×4 table into a 3×4 table, never into a 4×3 table, as this quarter turn has just done.

Of course, this quarter-turned table can now be permuted to give many 4×3 tables, all of which are equivalent up to permutation.  Indeed, there will be as many distinct 4×3 tables are there are distinct 3×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,

             [64212841510527189],

and

             [91827510154812246].

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

             [64212841510527189]        [91827510154812246],

and we also get

        [24594810186121527]         [27151261810849542].

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 :

        [24594810186121527]         [24648125101591827].
 
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.