Continued Fraction Algorithm

Algorithm

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

Let $x_0$ be the irrational number in question.

The steps are:

\(\text {(1)}: \quad\)

\(\ds k\)

\(=\)

\(\ds 0\)

initialise

\(\text {(2)}: \quad\)

\(\ds a_k\)

\(=\)

\(\ds \floor {x_k}\)

the $k$th partial quotient (that is, $a_k$) is the integer part of $x_k$

\(\text {(3)}: \quad\)

\(\ds x_{k + 1}\)

\(=\)

\(\ds \frac 1 {x_k - a_k}\)

the subsequent term is the reciprocal of the fractional part of $x_k$

\(\text {(4)}: \quad\)

\(\ds k\)

\(=\)

\(\ds k + 1\)

increase $k$ by $1$ then go to step $(2)$

Then $x_0 = \sqbrk {a_0, a_1, a_2, \ldots}$ is the required continued fraction expansion.

Examples

Example: $\sqrt 2$

Applying the Continued Fraction Algorithm to $\sqrt 2$:

\(\text {(1)}: \quad\)

\(\ds x_0\)

\(=\)

\(\ds \sqrt 2\)

\(\text {(2)}: \quad\)

\(\ds a_0\)

\(=\)

\(\ds \floor {x_0}\)

\(\ds = \floor {\sqrt 2}\)

step $(2)$

\(\text {(3)}: \quad\)

\(\ds \)

\(=\)

\(\ds 1\)

integer part of $\sqrt 2$ is $1$

\(\text {(4)}: \quad\)

\(\ds x_{0 + 1}\)

\(=\)

\(\ds \frac 1 {x_0 - a_0}\)

\(\ds = \frac 1 {\sqrt 2 - 1}\)

step $(3)$

\(\text {(5)}: \quad\)

\(\ds x_1\)

\(=\)

\(\ds \frac 1 {\sqrt 2 - 1} \times \paren {\frac {\sqrt 2 + 1} {\sqrt 2 + 1} }\)

multiply by $1$

\(\text {(6)}: \quad\)

\(\ds \)

\(=\)

\(\ds \sqrt 2 + 1\)

\(\text {(7)}: \quad\)

\(\ds a_1\)

\(=\)

\(\ds \floor {x_1}\)

\(\ds = \floor {\sqrt 2 + 1}\)

step $(2)$

\(\text {(8)}: \quad\)

\(\ds \)

\(=\)

\(\ds 2\)

integer part of $\paren {\sqrt 2 + 1 }$ is $2$

\(\text {(9)}: \quad\)

\(\ds x_{1 + 1}\)

\(=\)

\(\ds \frac 1 {x_1 - a_1}\)

\(\ds = \frac 1 {\paren {\sqrt 2 + 1 } - 2}\)

step $(3)$

\(\text {(10)}: \quad\)

\(\ds x_2\)

\(=\)

\(\ds \frac 1 {\sqrt 2 - 1} \times \paren {\frac {\sqrt 2 + 1} {\sqrt 2 + 1} }\)

multiply by $1$

\(\text {(11)}: \quad\)

\(\ds \)

\(=\)

\(\ds \sqrt 2 + 1\)

lines $7$ through $11$ repeat ad infinitum: $\sqrt 2 = \sqbrk {1, \sequence 2}$

$\blacksquare$

Proof 1

The validity of the material on this page is questionable. In particular: circular reasoning You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

This article, or a section of it, needs explaining. In particular: Why is this a circular reasoning? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Let $x_0$ be an irrational number.

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

From Bound for Difference of Limit of Simple Infinite Continued Fraction with Convergent:

$x_1$ lies strictly between any successive pair of its convergents.

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

In particular, as $a_1 \ge 1$, we know that $a_0 < x_0 < a_0 + 1$.

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

We note, in particular, that $a_0$ is therefore determined by $x_0$ alone.

Now we write:

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

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

Then:

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

From Real Number minus Floor:

$0 \le \left\{{x_0}\right\} < 1$

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

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

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

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

Then $x_1 = \left[{a_1, a_2, a_3, \ldots}\right]$.

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

So $x_1$ is an irrational number greater than $a_1$ which is positive.

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

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

And so on.

$\blacksquare$