Continued Fraction Algorithm

Algorithm

The Continued Fraction Algorithm is a method for finding the a continued fraction expansion for any irrational number to as many partial quotients as desired.

Let $x_1$ be the irrational number in question.

The steps are:

1. Set $k := 1$.
2. Set $a_k := \left \lfloor {x_k} \right \rfloor$.
3. Set $x_{k+1} := \dfrac {1} {x_k - a_k}$.
4. Set $k := k + 1$.
5. Go to step 2.

Then $x_1 = \left[{a_1, a_2, a_3, \ldots}\right]$ is the required continued fraction expansion.

Proof

Let $x_1$ be an irrational number.

We seek $a_1, a_2, \ldots \in \Z$ such that $x_1 = \left[{a_1, a_2, \ldots}\right]$.

We know from Value of Simple Continued Fraction that $x_1$ lies strictly between any successive pair of its convergents.

So, for a start, it has to lie between $C_1 = a_1$ and $C_2 = a_1 + \dfrac 1 {a_2}$.

In particular, as $a_2 \ge 1$, we know that $a_1 < x_1 < a_1 + 1$.

So $a_1 = \left \lfloor {x_1} \right \rfloor$ where $\left \lfloor {x_1} \right \rfloor$ is the floor function of $x_1$.

We note, in particular, that $a_1$ is therefore determined by $x_1$ alone.

Now we write:

$x_1 = \left \lfloor {x_1} \right \rfloor + \left\{{x_1}\right\}$

where $\left\{{x_1}\right\}$ is the fractional part of $x_1$.

Then:

$x_1 = a_1 + \cfrac 1 {a_2 + \cfrac 1 {a_3 + \cfrac 1 {\ddots}}} = \left \lfloor {x_1} \right \rfloor + \cfrac 1 {a_2 + \cfrac 1 {a_3 + \cfrac 1 {\ddots}}} = \left \lfloor {x_1} \right \rfloor + \dfrac 1 {\left[{a_2, a_3, a_4, \ldots}\right]}$.

Note that from Real Number Minus Floor, $0 \le \left\{{x_1}\right\} < 1$.

But because $x_1$ is irrational, $\left\{{x_1}\right\} \ne 0$.

So $0 < \left\{{x_1}\right\} < 1$.

So: $\left[{a_2, a_3, a_4, \ldots}\right] = \dfrac 1 {x_1 - \left \lfloor {x_1} \right \rfloor} = \dfrac 1 {\left\{{x_1}\right\}}$.

Now we write $x_2 = \dfrac 1 {\left\{{x_1}\right\}}$.

Then $x_2 = \left[{a_2, a_3, a_4, \ldots}\right]$.

As $\left\{{x_1}\right\} < 1$ we have that $x_2 = \dfrac 1 {\left\{{x_1}\right\}} > 1$.

So $x_2$ is an irrational number greater than $a_2$ which is positive.

Repeating the argument leads to $a_2 = \left \lfloor {x_2}\right \rfloor$ and so $a_2$ is determined uniquely from $x_2$ and hence from $x_1$.

In the same way, $x_3 = \dfrac 1 {\left\{{x_2}\right\}}$ and so $x_3 = \left[{a_3, a_4, a_5, \ldots}\right]$.

And so on.

$\blacksquare$