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

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