Tuesday, January 26, 2010

The reversed odometer

For simplicity, consider a vehicle with an old-style mechanical odometer, and a separate trip odometer with four digits, the lowest digit representing tenths of miles.  Reset the trip odometer so that it reads all zeroes, and drive a tenth of a mile backwards.  The odometer should now read `999.9`.  Let's ignore the decimal point, and work in distance units of a tenth of a mile.  Then the trip meter reads `9999` units.  What it should read is `-1` unit, or some equivalent to that.

It should be clear that the trip meter, if unreset, cycles after every `10000` units of travel.  It could measure the actual distance since it was last reset, or it could be any multiple of `10000` units out.  Anyway, if the thousands digit reads `9`, but the meter is too high by `10000` units, then to correct the problem, we can simply remove `10` thousand from `9` thousand.  This gives `-1` thousand, or `\bar{1}` thousand---i.e. the thousand digit might say `9` but it will be better for us to read it as `\bar{1}`.

We can put this in wiggle, and calculate

`\qquad\qquad\qquad \bar{1}999  =  \bar{1}_{10}9_{10}9_{10}9,`
`\qquad\qquad\qquad\qquad  =  \bar{1}_{1000}999,`
`\qquad\qquad\qquad\qquad  =  -1000 + 999,`
`\qquad\qquad\qquad\qquad  =  -1.`

Put another way, provided we read the high order digit in suitable way, as string of nines, or else a `-1` followed by a string of nines, can be reasonable way to express `-1`.

This particular notation for negatives is called tens complement.  In tens complement, as for the odometer driven in reverse :

`\qquad\qquad\qquad \ldots999  =  -1,`

`\qquad\qquad\qquad \ldots998  =  -2,`

`\qquad\qquad\qquad \ldots997  =  -3,`

`\qquad\qquad\qquad\qquad\qquad\qquad \vdots`

A second cut at negative quantities---complementary representations

Fashioning negative quantities in sign and magnitude form, as we did in the last post, requires negation, so called because it makes positive quantities negative.

This is probably not the best of names, because negation also makes negative quantities positive.  It also changes left to right, north to south, east to west, debit to credit, and vice versa in each case.  There is nothing inherently positive or negative about east and west, but they are clearly opposites, and negation turns the one into the other. 

So a better name might be something like turning, reversal, or flipping, but we are probably stuck with negation---the negative of east is west, and vice versa.

Here, however, we are dealing with quantities that do have a sign.

The negative in sign and magnitude form of my littlest's birthweight, with the magnitude expressed in mixed units, is :

`\qquad\qquad\qquad -(7" lb." + 12" oz.").`

Negating each of the terms separately, we get

`\qquad\qquad\qquad -(7" lb." + 12" oz.")  =  \bar{7}" lb."  +  \bar{12}" oz."`

This is what we would use in calculations.  It turns out, however, not to be the only form, or even the most convenient.

Complementary representations of negative quantities are particularly convenient for addition.  In a complementary representation, we allow only the amount of the largest unit to be negative, requiring all the other parts of the mixed quantity to follow the usual rules for standard form, including requiring them to be non-negative.  We get the complementary form of  `\bar{7}" lb."  +  \bar{12}" oz."` by borrowing (when already in debt...) :

`\qquad\qquad\qquad \bar{7}" lb."  +  \bar{12}" oz."  =  \bar{7}" lb."  -  1" lb."  +  16" oz."  +  \bar{12}" oz.,"`
`\qquad\qquad\qquad\qquad =  \bar{8}" lb."  +  4" oz."`

Now that we have the negative of my son's birthweight, in complementary form, we can use it to calculate his growth from birth at his other weighings.  Instead of subtracting his birthweight from his subsequent weights, we can add the negative of his birthweight in this form to these subsequent weights.

So my littlest's growth by Friday is

`\qquad\qquad\qquad (7" lb." +  8" oz.") + ( \bar{8}" lb."  +  4" oz."),`
`\qquad\qquad\qquad =  (7 - 8)" lb."  + (8 + 4)" oz."),`
`\qquad\qquad\qquad =  \bar{1}" lb." + 12" oz.",`

where the result is just a complementary form for `-4" oz."

His growth by today, on the other hand, is

`\qquad\qquad\qquad (8" lb." +  0" oz.") + ( \bar{8}" lb."  +  4" oz."),`
`\qquad\qquad\qquad =  (8 - 8)" lb."  + (0 + 4)" oz.),`
`\qquad\qquad\qquad =  0" lb." + 4" oz.".`

This method may look unnecessarily awkward for small and simple quantities such as we have here.  It is nevertheless extremely useful.  The usual method by which a computer represents a negative integer is as a complementary form in base two; the usual method of representing negative common logarithms uses complementary form; complementary form can be helpful in ordinary arithmetic.

Perhaps the most graphic example of complementary form mixes the old style mechanical odometer and the imagination.  But that is a topic for another post.

A first cut at negative quantities

One can subtract directly, as we did in the last posting, e.g.

my littlest son's weight today Tuesday - his weight at birth on Thursday = 4 oz.

Sometimes, however, such subtractions result in a negative answer, e.g.

his weight at his first doctor's visit on Friday - his weight at birth on Thursday = -4 oz.

The most familiar way to represent negative quantities is as the opposite, or negative, of a positive quantity.  This is convenient for many purposes, but it is not the only way, or even the most convenient, as we shall see.

8 pounds and grown by---how much?

Our littlest, born Thursday morning, and weighing  7 pounds, 12 ounces then, but 7 pounds, 6 ounces at his checkup late Friday afternoon, was weighed at his second checkup today.

It is common for newborns to lose weight and only come up to birthweight between one and two weeks, apparently, but that has not been the time scale with our children.  Today, our littlest weighed in at 8 pounds even.  (No, again, I am not faking the figures.  I am starting to wonder whether those who measure him round to the nearest quarter pound, but I don't think they do.)

This provides an opportunity to look at subtraction of mixed units, otherwise known as compound subtraction.  It is reasonably obvious that my newborn has experience net growth of four ounces between his birth weighing and today's weighing.

One way to subtract is to do it term by term, so that

`\qquad\qquad\qquad (8" lb."  +  0" oz.")  -  (7"  lb."  +  12" oz."),`
`\qquad\qquad\qquad\qquad =  (8 - 7)" lb."  +  (0 - 12)" oz.,"`
`\qquad\qquad\qquad\qquad =  1" lb."  + \bar{12}" oz.,"`

where the overbar represents negation, as before.  This result is true, but not in standard form.  We rectify by a subtractive kinds of carrying, known as borrowing :

`\qquad\qquad\qquad 1" lb."  + \bar{12}" oz."  =  0" lb."  +  16" oz."  + \bar{12}" oz.,"`
`\qquad\qquad\qquad\qquad =  0" lb."  +  (16 - 12)" oz.,"`
`\qquad\qquad\qquad\qquad =  4" oz."`

Converting fractional units into mixed units

We now present two different methods for unwrapping a fractional part into mixed units.

Suppose now that we wish to convert `5\frac{7}{9}` yards into yard, feet, and inches.

In the first method, we proceed by splitting into whole and fractional parts, and rewriting the fractional part in smaller units, e.g

`\qquad\qquad\qquad 5" yards"  +  7/9" yards"  =  5" yards"  +  7/3" feet",`
`\qquad\qquad\qquad\qquad =  5" yards"  +  2 1/3" feet,"`
`\qquad\qquad\qquad\qquad =  5" yards"  +  2" feet"  +  1/3" feet,"`
`\qquad\qquad\qquad\qquad =  5" yards"  +  2" feet"  +  4" inches."`

In the second method, we first multiply `5\frac{7}{9}`,  by `3` and by `12`, to get `208`, and then we use successive division as in the last posting.  We can even shorten this method by extracting the `5` first, multiplying just the `\frac{7}{9}` by `3` and by `12` to get `28`, and then dividing as before; this spares us the last division : `28  =  2_{12}4.`

Converting single unit expressions into mixed unit expressions in standard form

So far, we have looked at converting mixed units to a single unit, and also at performing addition while remaining in mixed units.  It is time to learn how to go from single units expressions to given mixed units.

Suppose, for instance, we wish to convert `208` inches into yards, feet, and inches.  One can of course say trivially that

`\qquad\qquad\qquad 208  =  0_{3}0_{12}208,`

i.e. 0 yard, 0 feet, 208 inches.  That probably isn't what we wanted, so we need to be more specific---we want to convert into yards, feet, and inches in standard form.

The way to to this is by converting smaller units into complete larger units, i.e. by carrying; the way to do that is by successive division.  How many whole feet, i.e. how many complete lots of `12` inches, go into `208` inches?  Dividing `12` into `208`, i.e. `12 \\ 208` or `208 -: 12`, we find that `12` goes `17` times, with a remainder of `4`, often written `17  "r"  4`.  In  `17  "r"  4`, "r" stands for "remainder".  Instead of this, we shall write `17_{12}4`, because if we did the division correctly, then `17_{12]4` has to be a wiggle expression equivalent to `208`.

In any case, `208` inches is equivalent to `17` feet and `4` inches, and this would be our final answer if we were using only feet an inches as units.  But since we are also using yards, we divide `17` by `3`, whence `17  = 5_{3}2`, i.e. `17` feet is `5` yards and `2` feet.

So in the end, `208` inches is `5` yards, `2` feet, `4` inches.  In wiggle without units,

`\qquad\qquad\qquad 208  =  5_{3}2_{12}4.`

The calculation proceeds from right to left, dividing by successive interbases, writing only the remainder, and passing the quotient to the next interbase for division.  The final quotient is then written before the leftmost interbase.

The work of successive division can be set forth as follows :

`\qquad\qquad\qquad{:"       "\ul{"      5"}_{"   3 "}2`
`\qquad\qquad\qquad{:"   3 "\ul{")   17"}_{" 12 "}4`
`\qquad\qquad\qquad{:" 12 )  208."`

Brave souls may even elect to drop the divisors on the left, and write them just on the right, at levels between the lines, from the beginning.


`\qquad\qquad\qquad{:"       "\ul{"      5"}_{"   3 "}2`
`\qquad\qquad\qquad{:"      "\ul{"    17"}_{" 12 "}4`
`\qquad\qquad\qquad{:"         208."`

Place value, superposition, and all that

Consider the number `535.49`.  It can be written as a series of multiples of powers of ten, e.g.

`\qquad 535.49 = 5 (10 xx 10)  +  3 (10)  +  5 (1)  +  4 (1/10)  +  9 (1/10 xx 1/10),`
`\qquad\qquad = 5 (100)  +  3 (10)  +  5 (1)  +  4 (0.1)  +  9 (0.01),`

We have already seen a some correspondences between how decimals work and how wiggle works.  Consider then

`\qquad\qquad\qquad 5_{7}2_{24}10;_{60}45_{10}7  =  898\frac{457}{600}`

We can write

`5_{7}2_{24}10;_{60}45_{10}7 `
`=  5  (7 xx 24) +  2 (24)  +  10 (1)  +   45 (1/60)  +  7 (1/60 xx 1/10)`
`=  5  (1_{7}0_{24}0) + 2 (1_{24}0) + 10 (1) +  45 (0;_{60}1) + 7 (0;_{60}0_{10}1).`

This decomposition tells what each superdigit contributes to the total.  The contribution is the product of the size of the superdigit itself (e.g. `5`) and the place value associated with where the superdigit is placed (e.g. `7 xx 24`).  The correspondence with decimals should be obvious.

Another thing to notice is that superposition holds just as well for wiggle expressions as it does for mixed units and for decimal notation.  Superposition is the idea that each superdigit contributes a known amount to the sum, in fixed proportion to its size, and independent of what the other superdigits are contributing.

Compound addition, carrying, and standard form

We have looked at converting mixed unit expressions into single-unit expressions, e.g.

`\qquad\qquad\qquad 5 "yd.", 2 "ft.", 4 "in."  =  17\frac{1}{3} "ft."`

It can be useful, and also instructive, to perform arithmetic directly with mixed expressions.  This is called compound arithmetic, and was once a substantial part of elementary arithmetic.

Addition is the most elementary of these arithmetical operations.  Suppose, then, that we wish to add 2 yards, 2 feet, 9 inches to 5 yards, 2 feet, 4 inches.

The simplest way to approach this is to add like terms, so that

`\qquad\qquad\qquad (2 "yd." + 2 "ft." + 9 "in.")  +  (5 "yd." + 2 "ft." + 4 "in.")`
`\qquad\qquad\qquad\qquad  =  (2 + 5) "yd."  +  (2 + 2) "ft."  +  (9 + 4) "in."`
`\qquad\qquad\qquad\qquad  =  7 "yd." + 4 "ft." + 13 "in."`

This result, while true, is unfinished.  It is customary to combine smaller units into whole bigger unit equivalents wherever possible, in a process equivalent to carrying in elementary arithmetic :

`\qquad\qquad\qquad 7 "yd." + 4 "ft." + 13 "in."  =  7 "yd." + 4 "ft." + 1"ft." + 1 "in." `
`\qquad\qquad\qquad\qquad =  7 "yd." + 5 "ft." + 1" in."`
`\qquad\qquad\qquad\qquad =  7 "yd." + 1 "yd." + 2 "ft." + 1 "in."`
`\qquad\qquad\qquad\qquad =  8 "yd." + 2 "ft." + 1 "in."`

After carrying has been completed, the result is in standard form 

Carrying and standard form also apply to wiggle notation in an obvious way, at least when the interbases are all whole numbers greater than one and the total quantity is not negative.  Then, wiggle notation is in standard form when each superdigit is non-negative, each superdigit except (perhaps) the last is a whole number, and each interbase is greater than the superdigit to it's immediate right.

There are at least two reasons to prefer standard form.  The first is that making full use of larger units keeps the corresponding numbers of units smaller.

The second, more important, reason is that it makes for ease of comparison---when quantities are in standard form, we can tell when one quantity is larger than another, or if they are equal.  One compares the amounts of the largest unit, and if those are equal, one compares the amounts of the next largest unit, and so forth, until we knows.  The process is similar to determining the order of words in a dictionary---lexical ordering.

It can reasonably be argued that both an ordered alphabet (or ordered syllabary) and either a place value number system or (more likely) the use of mixed units in standard form are probable antecedents to the invention of lexically ordered dictionaries.

New bases for free, by hundreds and by thousands

Consider the number `535.49165552`.  This is a number written in base ten.  This fact can be used immediately to write an equivalent wiggle expression : `5_{10}3_{10}5;_{10}4_{10}9_{10}1_{10}6_{10}5_{10}5_{10}5_{10}2`.  It turns out, however, that there are other equivalent wiggle expressions that can be written at sight.  There is of course the trivial possibility---simply consider `535.49165552` to be a single superdigit.

Be we can also write `535.49165552` immediately in base a hundred, `5_{100}35;_{100}49_{100}16_{100}55_{100}52,` or in base a thousand, `535;_{1000}491_{1000}655_{1000}520,` or in base a million `535;_{1000000}491655_{1000000}520000.`  Clearly, other positive whole powers of ten will work easily too.

Nor is it necessary to have a constant base.  Yet another equivalent of `535.49165552` is `5_{100}35;_{10}4_{100}91_{10}6_{1000}555_{10}2.`

So far we have clumped together digits of `535.49165552` into superdigits (making sure that there is clump boundary immediately after the unit digit), changed the decimal point to a semicolon, and then in the spaces between superdigits, written for an interbase a `1` with as many `0`s after it as there are digits in the superdigit to its immediate right.

Clumping is not the only possibility.  With a little more effort, we may also dissect.  We could, for instance, first rewrite each decimal digit as a number in base 5, `(1_{5}0)_{10}(0_{5}3)_{10}(1_{5}0);_{10}(0_{5}4)_{10}(1_{5}4)_{10}(0_{5}1)_{10}(1_{5}1)_{10}(1_{5}0)_{10}(1_{5}0)_{10}(1_{5}0)_{10}(0_{5}2),` and then remove brackets, compensating for the newly exposed `5`s by removing a factor of 5 from each 10 interbase, `1_{5}0_{2}0_{5}3_{2}1_{5}0;_{2}0_{5}4_{2}1_{5}4_{2}0_{5}1_{2}1_{5}1_{2}1_{5}0_{2}1_{5}0_{2}1_{5}0_{2}0_{5}2,`

This is a composite base, which can be called `2 xx 5`. The arithmetic of base `2 xx 5` is exactly the arithmetic of the Japanese abacus, or soroban.  The order here is important.  It is given by the order of the interbases in the repeating group, where the semicolon marks a break between one repeating group and the next.  On the soroban, the lone heaven bead on a rod is worth `5`, and each of the four earth beads is worth one `1`.

An alternative ten-friendly composite base is `5 xx 2`.  An abacus built according to that scheme would have four heaven beads, each worth `2`, and one earth bead worth `1`.  A regular soroban turned upside down could be used in that way.

BTW, Happy Australia Day.

Telescoping from the right, telescoping on the right, and full telescoping

Let's evaluate five weeks, two days, ten and three-quarter hours, in weeks and fractions of a week.

`\qquad\qquad\qquad 5;_{7}2_{24}10_{4}3.`

So far, we have followed used telescoping from the right, whereby the leftmost nonzero superdigit is divided by the interbase to its left, and then added to the superdigit to the left, this process being repeated until we are adding to the face value column.  Then


`\qquad\qquad\qquad 5;_{7}2_{24}10_{4}3  =  5;_{7}2_{24}(10\frac{3}{4}),`
`\qquad\qquad\qquad\qquad  =  5;_{7}2_{24}(\frac{43}{4}),`
`\qquad\qquad\qquad\qquad  =  5;_{7}(2\frac{43}{96}),`
`\qquad\qquad\qquad\qquad  =  5;_{7}(\frac{235}{96}),`
`\qquad\qquad\qquad\qquad  =  5\frac{235}{672}.`

Many of the practical uses for wiggle notation employ only integer or natural number interbases.  In these cases, the whole number part of the answer consists of the face value superdigit and the value of the expression to its left, while everything to the right produces the fractional part.  In such cases, instead of telescoping the fractional part from the left term by term as above, we can first telescope right...

`\qquad\qquad\qquad 5;_{7}2_{24}10_{4}3  =  5;_{7}0_{24}(2 xx 24  +  10)_{4}3,`
`\qquad\qquad\qquad\qquad  =  5;_{7}0_{24}58_{4}3,`
`\qquad\qquad\qquad\qquad  =  5;_{7}0_{24}0_{4}(58 xx 4  +  3),`
`\qquad\qquad\qquad\qquad  =  5;_{7}0_{24}0_{4}235,`

...and then compact left...

`\qquad\qquad\qquad\qquad  =  5\frac{235}{7 xx 24 xx 4}  =  5\frac{235}{672}.`

It can be written and remembered more succinctly :

`\qquad\qquad\qquad 5;_{7}2_{24}10_{4}3  =  5\frac{2_{24}10_{4}3}{7 xx 24 xx 4}  =  5\frac{235}{672}.`

It can be made more or less self-evident by the following argument :


`\qquad\qquad\qquad 5;_{7}2_{24}10_{4}3  =  5 + 0;_{7}2_{24}10_{4}3,`
`\qquad\qquad\qquad\qquad =  5 + 0;_{7}2_{24}10_{4}3,`
`\qquad\qquad\qquad\qquad=  5 + \frac{0;_{7}2_{24}10_{4}3}{1;_{7}0_{24}0_{4}0},` 
`\qquad\qquad\qquad\qquad =  5 + \frac{0_{7}2_{24}10_{4}3;}{1_{7}0_{24}0_{4}0;},`

`\qquad\qquad\qquad\qquad =  5 + \frac{2_{24}10_{4}3}{7 xx 24 xx 4},`
`\qquad\qquad\qquad\qquad =  5\frac{235}{672}.`

The combined process of telescoping the right part rightwards and then compacting it leftwards can be called telescoping on the right.  The arithmetic is perhaps a little simpler.

A slight variant of the process can be used for converting a wiggle expression to a pure rational form. In that case, one telescopes right not just the fractional part, but the whole wiggle expression, from its beginning (i.e. telescopes right, ignoring the semicolon), and then compacts left by dividing by the product of all the interbases to the right of the face value superdigit.  This can be called full telescoping.  The simplest case, and the most useful, is for converting a mixed fraction into a pure fraction :

`\qquad\qquad\qquad 3\frac{1}{7}  =  3;_{7}1  =  \frac{3_{7}1}{7}  =  \frac{22}{7}.

But the process also works for longer expressions.  e.g. to find the number of days, say, in five weeks, two days, ten and three-quarter hours, writing the result as a pure fraction,

`\qquad\qquad\qquad 5_{7}2;_{24}10_{4}3  =  \frac{5_{7}2_{24}10_{4}3}{24 xx 4},`
`\qquad\qquad\qquad  =  \frac{3559}{96}.`