Monday, January 25, 2010

Using wiggle to calculate values of a polynomial

Today's calculator-ridden generation, given

`\qquad\qquad\qquad p(x)  =  3 x^3  +  4 x^2  +  2 x  +  5`

and asked to calculate `p(2)`, run off and calculate

`\qquad\qquad\qquad p(2)  =  3 (2)^3  +  4 (2)^2  +  2 (2)  +  5.`

The calculation in that form requires two powers, three multiplications, and three additions.  It is usually more efficient to calculate the equivalent wiggle expression

`\qquad\qquad\qquad p(2)  =  3_{2}4_{2}2_{2}5,`

which requires only three multiplications and three additions.  Although succinctly written in wiggle notation, this is actually an old trick known as nested multiplication.  One of the vagaries of the usual curriculum is that this trick is rarely taught to newbies; even many oldbies are unfamiliar with it, and they will have met it under the name synthetic division, where it is used only for the much less common purpose of evaluating the remainder when dividing a polynomial by a monomial.

The convenience is not limited to calculations with positive whole numbers.  We need to be careful to represent missing powers by zeroes in the wiggle expression.

It is also time to introduce a more surgical way to negate :  let an overbar negate whatever is under it.

For example, let's find `q(-1.5)`, where

`\qquad\qquad\qquad q(x)  =  3.1  x^3  -  2.2  x  +  5.7,`
`\qquad\qquad\qquad\qquad =  3.1_{x}0_{x}\bar{2.2}_{x}5.7.`

Then

`\qquad\qquad\qquad  q(-1.5)  =  3.1_{\bar{1.5}}0_{\bar{1.5}}\bar{2.2}_{\bar{1.5}}5.7,`
`\qquad\qquad\qquad\qquad  = (\bar{4.65} + 0)_{\bar{1.5}}\bar{2.2}_{\bar{1.5}}5.7,`
`\qquad\qquad\qquad\qquad  = (6.975 - 2.2)_{\bar{1.5}}5.7,`
`\qquad\qquad\qquad\qquad  = (\bar{7.1625} + 5.7),`
`\qquad\qquad\qquad\qquad  = -1.4625`

With a little practice, one can get to the point when one can stare at an expression like


`\qquad\qquad\qquad q(x)  =  3.1  x^3  -  2.2  x  +  5.7,`

think 

`\qquad\qquad\qquad\qquad q(x) =  3.1_{x}0_{x}\bar{2.2}_{x}5.7.`

and calculate `q(x)` for a succession of values of `x`, and so prepare a table of values for making a plot.

To the unknown base

Let's evaluate the following wigglish expression :

`\qquad\qquad\qquad 3_{x}4_{x}2_{x}5.`

Telescoping from the left, we get

`\qquad\qquad\qquad 3_{x}4_{x}2_{x}5  =  (3 x  +  4)_{x}2_{x}5,`
`\qquad\qquad\qquad\qquad  =  (3 x^2  +  4 x  +  2)_{x}5,`
`\qquad\qquad\qquad\qquad  =  3 x^3  +  4 x^2  +  2 x  +  5.`

So in brief, we get

`\qquad\qquad\qquad 3_{x}4_{x}2_{x}5  =  3 x^3  +  4 x^2  +  2 x  +  5.`

The pattern that suggests itself here is true in general---a polynomial in the variable `x` can be thought of as a number in base `x`.

Polynomials can be added, subtracted, and multiplied as if they were numbers in base `x`.  For instance

`\qquad\qquad\qquad (3 x^3  +  4 x^2  +  x  +  5)  +  (x^3  +  2 x^2  +  7 x  + 2)`
`\qquad\qquad\qquad\qquad =  4 x^3  +  6 x^2  +  8 x  +  7`

becomes

`\qquad\qquad\qquad 3_{x}4_{x}1_{x}5  +  1_{x}2_{x}7_{x}2`
`\qquad\qquad\qquad\qquad =  4_{x}6_{x}8_{x}7.`

The last calculation resembles the ordinary addition `3415 + 1272  =  4687.`

The product

`\qquad\qquad\qquad (x + 2) (x + 3)  =  x^2 + 5 x + 6`

can be rendered

`\qquad\qquad\qquad (1_{x}2) (1_{x}3)  =  1_{x}5_{x}6

and this resembles the ordinary numerical product `12 xx 13  =  156.`

Base `x` calculations do not always agree with corresponding decimal calculations.  The base `x` calculation is most often actually simpler, because there is no carrying, as there with ordinary numbers, e.g. :

`\qquad\qquad\qquad (15) (15)  =  1 ^{1}0^{2}5  =  225, `

but, (no carrying steps this time),

`\qquad\qquad\qquad (1_{x}5) (1_{x}5)  =  1_{x}10_{x}25.`

Wigglish sums, products, and quotients

To make a sum using wiggle, write the addends as a string of superdigits, and interpose `1`s as interbases, e.g.

`\qquad\qquad\qquad a + b + c + d  =  a_{1)b_{1}c_{1}d.`

Summation is essentially wiggle in base one.

To make a product using wiggle, write the factors as a string of interbases.  Then write `1` as the first superdigit and `0`s for all remaining superdigits, e.g.

`\qquad\qquad\qquad a  b  c  d  =  1_{a)0_{b}0_{c}0_{d}0.`

To make a quotient using wiggle, treat the numerator and denominator as you would for a fraction, e.g.

`\qquad\qquad\qquad p -: q  =  p // q  =  p/q  =  q  \\  p  =  0;_{q}p.`

There is no particularly easy way to represent negation or subtraction in wiggle.

Weirder bases, and what should you call the decimal point in other bases?

Now let's look at a fractional base.  Let's try base one-tenth.  What is

`\qquad\qquad\qquad 12.345_{\frac{1}{10}}`?

The wiggle equivalent is

 `\qquad\qquad\qquad 12.345_{\frac{1}{10}}  =  1_{\frac{1}{10}}2;_{\frac{1}{10}}3_{\frac{1}{10}}4_{\frac{1}{10}}5.`

Telescoping from the left, we have

`\qquad\qquad\qquad 1_{\frac{1}{10}}2;_{\frac{1}{10}}3_{\frac{1}{10}}4_{\frac{1}{10}}5,`
`\qquad\qquad\qquad\qquad  =  ((1 xx \frac{1}{10}) + 2);_{\frac{1}{10}}3_{\frac{1}{10}}4_{\frac{1}{10}}5,`
`\qquad\qquad\qquad\qquad  =  (2.1);_{\frac{1}{10}}3_{\frac{1}{10}}4_{\frac{1}{10}}5.`

Telescoping now from the right, we have

`\qquad\qquad\qquad  =  (2.1);_{\frac{1}{10}}3_{\frac{1}{10}}(4 + \frac{5}{\frac{1}{10}}),`
`\qquad\qquad\qquad  =  (2.1);_{\frac{1}{10}}3_{\frac{1}{10}}(4 + 50),`
`\qquad\qquad\qquad\qquad =  (2.1);_{\frac{1}{10}}3_{\frac{1}{10}}54,`
`\qquad\qquad\qquad  =  (2.1);_{\frac{1}{10}}(3 + \frac{54}{\frac{1}{10}}),`
`\qquad\qquad\qquad\qquad   =  (2.1);_{\frac{1}{10}}(3 + 540),`
`\qquad\qquad\qquad\qquad   =  (2.1);_{\frac{1}{10}}(543),
`\qquad\qquad\qquad\qquad   =  (2.1); + (5430),`
`\qquad\qquad\qquad\qquad   =  5432.1.`

So

`\qquad\qquad\qquad 12.345_{\frac{1}{10}}  =  5432.1,`

and numbers in base one-tenth are just the reverse of numbers in base ten, with the same digit (here a two) marked by the point.  If it doesn't look to be exactly the reverse (check!), that is because you are thinking of the point as positioned between `2` and `3` or `1` and `2`, rather than written just to the right of the `2`.

This suggests an answer to the vexed question of what to call the decimal point when the base is not ten.  Some people call it the binary point in binary, the ternary point in base three, as so forth.  A few have tried for a more generic solution by calling it the basal point.  Still others call it the fraction marker, because, for whole number bases greater than one, the part before the point represents a whole number, but the part afterthe point represents a fraction less than one.

But what it really does is tells us which digit appears at face value.  It should probably be called the 'face value point' or 'unit point'.  Because what it does is mark which digit appears at face value.  In some respects, it would be better if it were a mark under the face value digit, rather than just to the right.  If, for instance, we used an underbar to mark the face value digit, than we would have


`\qquad\qquad\qquad 1\ul{2}345_{\frac{1}{10}}  =  543\ul{2}1_{10},`

and we would see even more clearly the relation between base ten and base a tenth.

The common usage of the decimal point is, nevertheless, here to stay.  For that reason, it is probably best to learn to use it, and just think of it as marking the digit to it's left as appearing at face value.  The use of the semicolon to mark the face value superdigit can be justified similarly.

Base-n arithmetic and wiggle

We saw above that

`\qquad\qquad\qquad 5_{10}3_{10}5;_{10}4_{10}9  =  535.49.`

Being explicit about the base, we can write

`\qquad\qquad\qquad 5_{10}3_{10}5;_{10}4_{10}9  =  535.49_{10}.`

Translating numbers in other bases into wiggle is an immediate generalization.  As a first example, suppose we are trying to evaluate

`\qquad\qquad\qquad 10110111_{2}.`

We rewrite this, with the same digits---or bits---in the same order as the superdigits, and making each interbase be 2, so that



`\qquad\qquad\qquad 10110111_{2}  =  1_{2}0_{2}1_{2}1_{2}0_{2}1_{2}1_{2}1.`

Telescoping from left, we get

`\qquad\qquad\qquad 1 xx 2  =  2,`
`\qquad\qquad\qquad 2 + 0  =  2,`
`\qquad\qquad\qquad 2 xx 2  =  4,`
`\qquad\qquad\qquad 4 + 1  =  5,`
`\qquad\qquad\qquad 5 xx 2  =  10,`
`\qquad\qquad\qquad 10 + 1  =  11,`
`\qquad\qquad\qquad 11 xx 2  =  22,`
`\qquad\qquad\qquad 22 + 0  =  22,`
`\qquad\qquad\qquad 22 xx 2  =  44,`
`\qquad\qquad\qquad 44 + 1  =  45,`
`\qquad\qquad\qquad 45 xx 2  =  90,`
`\qquad\qquad\qquad 90 + 1  =  91,`
`\qquad\qquad\qquad 91 xx 2  =  182,`
`\qquad\qquad\qquad 182 + 1;  =  183;`

so that in the end

`\qquad\qquad\qquad 10110111_{2}  =  183.`

Let's try one with a fractional part.  What is

`\qquad\qquad\qquad 102.21_{3}?`


Rewriting in wiggle, we have

`\qquad\qquad\qquad 102.21_{3}  =  1_{3}0_{3}2;_{3}2_{3}1.`

Telescoping from the left and the right, we get

`\qquad\qquad\qquad 1_{3}0_{3}2;_{3}2_{3}1  =  (3 + 0)_{3}2;_{3}2_{3}1,` `\qquad\qquad\qquad\qquad  =  3_{3}2;_{3}2_{3}1,`
`\qquad\qquad\qquad\qquad  =  (9 + 2);_{3}2_{3}1,`
`\qquad\qquad\qquad\qquad  =  11;_{3}2_{3}1,`
`\qquad\qquad\qquad\qquad  =  11;_{3}(2 + \frac{1}{3}),`
`\qquad\qquad\qquad\qquad  =  11;_{3}\frac{7}{3},`
`\qquad\qquad\qquad\qquad  =  11\frac{7}{9}.`

Odder bases are also easy to calculate with.

Fractions and decimals---why two notations?

Although form represents the same kind of number, rational form ("fractions") and decimal form ("decimals") are used rather diferrently.

Fractions are used mostly in theoretical work including pure mathematics, and also by users of mixed units.

Decimals, on the other hand, are de rigeur in technical work, including engineering, experimental physics, and applied mathematics.

So, oddly enough, users of number convention largely work with fractions, while users of the quantities convention largely work with decimals.

The reason for the difference in use is not simply an accident of history.  In technical work, one is usually working with measured values, and these are usually approximate; in theoretical work (except for computational experiments) one's numbers are usually exact.

The arithmetic of decimals is somewhat simpler than the arithmetic of fractions, and the decimals are much more readily compared for size than are fractions.  These are huge advantages when working with approximate numbers.

The arithmetic of rational fractions, on the other hand, can be exact with nonterminating expressions.  To say `\frac{1}{3}` in  decimal is to say `0.3333...`  In theoretical work, we usually prefer exactness.  The inexactness of finitely terminated decimal values (e.g.  `0.333`) becomes a problem.

In technical calculations, on the other hand, exactness is rare, and we manage inaccuracy with limits.   We stop writing more digits when we reach the limit of accuracy of the value itself if it is measured, or the limit of accuracy of some other values in a calculation, or the limit of accuracy needed for the purpose of the calculation.

Fractions rational and decimal, and wiggle

Consider the number two and three-quarters.  We can write it in mixed rational form, `2\frac{3}{4},`  or in pure rational form, `\frac{11}{4},` or in decimal form, `2.75`.  Each of these forms can be modelled in wiggle notation :

`\qquad\qquad\qquad 2\frac{3}{4}  =  2;_{4}3,`

`\qquad\qquad\qquad \frac{11}{4}  =  0;_{4}11,`

`\qquad\qquad\qquad 2.75  =  2;_{10}7_{10}5`.

Rational forms ("fractions") and decimal forms ("decimals") are two alternative ways of representing the numbers that live between the whole numbers.

Fractions and decimals are alternative notations for rational numbers.  Although they are used to represent the same things, the notations themselves are usually taught as unrelated.  Wiggle notation serves as a kind of bridge.  As we shall eventually see, wiggle glues a lot of things together.