Most recent change of ContinuedFraction

Edit made on October 25, 2008 by ColinWright at 21:49:56

Deleted text in red / Inserted text in green

WW
HEADERS_END
Take any number. It consists of a whole number, plus
a bit left over. That extra bit might be zero, in which
case we're done, but it might not be. If you subtract
off the whole number, the bit left over is between 0 and 1.
It might be 0, but it can't be 1.

Call the extra /x./

Now we can take EQN:\frac{1}{x}. That too is a whole number, plus
a bit left over. Again, that extra bit might be zero, in
which case we're done, but it might not be. Subtract off
the whole number, and repeat.
* Note: This will terminate if and only if the starting number is rational.
** Not hard to prove, and an interesting exercise.

Let's do this with EQN:\pi.

| EQN:\pi | = | 3 | + | 0.1415926... |
| 1/0.1415926... | = | 7 | + | 0.0625133... |
| 1/0.0625133... | = | 15 | + | 0.9965944... |
| 1/0.9965944... | = | 1 | + | 0.0034172... |
| 1/0.0034172... | = | 292 | + | 0.6345908... |
_ _
EQN:\Large{\pi=3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+...}}}}}

We can write this as EQN:\pi=[3;7,15,1,292,...]

Cutting this off at different stages gives us rational approximations.
* EQN:[3]=3=3.0000...
* EQN:[3;7]=22/7\approx3.142857
* EQN:[3;7,15]=333/106\approx3.14151
* EQN:[3;7,15,1]=355/113\approx3.141593
* EQN:[3;7,15,1,292]=103993/33102\approx3.1415926530
Compare these with the "correct" value of 3.1415926535897931...

As you can see, the large number in the expansion causes a
sudden jump in the terms used in the rational approximation.

However, a large number in the continued fraction implies a
small error in the previous step. That means that cutting
off the continued fraction just before a large number will
give an unreasonably good approximation.

Hence EQN:\pi\approx\frac{355}{113}

Using this technique gives an approximation with an error
that is "best" given a limit on the size of the denominator.
----
We can also use continued fractions to give another proof that
root two is irrational.
----
Given a continued fraction, we can compute the successive truncations as follows.
Taking EQN:\sqrt{2}=[1;2,2,2,2,2,...] as an example, write a table with
three rows. Put the CF terms across the top, and start with a sort of
"identity matrix", but the wrong way around. Here:

COLUMN_START
| | | 1 | 2 | 2 | 2 | 2 | 2 | ... |
| 0 | 1 | 1 | 3 | 7 | 17 | 41 | 99 | ... |
| 1 | 0 | 1 | 2 | 5 | 12 | 29 | 70 | ... |
COLUMN_SPLIT
So we have EQN:{41}{29} EQN:\frac{41}{29} and EQN:{99}{70} EQN:\frac{99}{70} as approximations to EQN:\sqrt{2}.
COLUMN_END

_ Each term is the product of the quotient above it and the term on its left,
plus the term two to the left. Here it is for EQN:\pi

COLUMN_START
| | | 3 | 7 | 15 | 1 | 292 | ... |
| 0 | 1 | 3 | 22 | 333 | 355 | 103933 | ... |
| 1 | 0 | 1 | 7 | 106 | 113 | 33102 | ... |
COLUMN_SPLIT
So /333=15*22+3/ and /113=1*106+7,/ and we get EQN:\frac{355}{113} as an approximation of EQN:\pi.
COLUMN_END