Continued Fractions and Approximating Real Numbers

Continued fractions are a fascinating and efficient way to represent real numbers using rational approximations. They offer elegant expressions, allow precise control over approximation errors, and reveal remarkable patterns.

What is a Continued Fraction?

A simple continued fraction has the form:

\[x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots}}}}\]

Here, \(a_0\) is an integer and all subsequent \(a_i\) are positive integers. Every real number can be represented in this way:

• If the expansion ends, the number is rational.
• If it goes on forever, the number is irrational.

How to Compute the Continued Fraction of a Real Number

To convert a real number \(x\) into a continued fraction, follow this recursive process:

\[ \begin{aligned} a_0 &= \lfloor x \rfloor \\ x_1 &= \frac{1}{x - a_0} \\ a_1 &= \lfloor x_1 \rfloor \\ x_2 &= \frac{1}{x_1 - a_1} \\ &\ \vdots \end{aligned} \]

Repeat until the fractional part vanishes or until desired precision is reached. The resulting \([a_0; a_1, a_2, \ldots]\) is the continued fraction expansion.

The golden ratio \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\ldots\) has a remarkably simple continued fraction representation of all ones:

\[ \varphi = [1; 1, 1, 1, \ldots], \]

making it the “most irrational number” in the sense that it is the hardest to approximate by rational numbers. This is because its continued fraction convergents are the slowest to approach the actual value, meaning no other number has worse rational approximations.

\[\varphi = [1; 1, 1, 1, \ldots] = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}}\]

Generalized Continued Fractions

A generalized continued fraction allows numerators other than 1:

\[x = a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{a_3 + \cdots}}}\]

To evaluate this expression, define the sequences \(A_k\) and \(B_k\) as follows:

\[ \begin{aligned} A_{-1} &= 1, & B_{-1} &= 0 \\ A_0 &= a_0, & B_0 &= 1 \\ \text{For } k &\geq 1: \\ A_k &= a_k A_{k-1} + b_k A_{k-2} \\ B_k &= a_k B_{k-1} + b_k B_{k-2} \end{aligned} \]

Then the \(k\)-th approximation is \(C_k = \frac{A_k}{B_k}\).

JavaScript Implementation

function computeContinuedFraction(a, b) {
    const n = Math.min(a.length, b.length + 1);
    let A_km2 = 1, A_km1 = a[0];
    let B_km2 = 0, B_km1 = 1;
    const convergents = [[A_km1, B_km1, A_km1 / B_km1]];

    for (let k = 1; k < n; k++) {
        const A_k = a[k] * A_km1 + b[k - 1] * A_km2;
        const B_k = a[k] * B_km1 + b[k - 1] * B_km2;
        convergents.push([A_k, B_k, A_k / B_k]);
        [A_km2, A_km1] = [A_km1, A_k];
        [B_km2, B_km1] = [B_km1, B_k];
    }

    return convergents;
}

An elegant continued fraction for \(\pi\) is:

\[\pi = 3 + \cfrac{1^2}{6 + \cfrac{3^2}{6 + \cfrac{5^2}{6 + \cfrac{7^2}{6 + \ddots}}}}\]

Here:

• Numerators: \(b_k = (2k+1)^2\)
• Denominators: \(a_k = 6\)

This structure is pleasing, though the convergence is slow.

const N = 20;
const a = [3].concat(Array(N).fill(6));
const b = Array.from({ length: N }, (_, k) => (2 * k + 1) ** 2);
const result = computeContinuedFraction(a, b);
console.log(result.map(x => x[2]));

Converting Decimals to Fractions

We can use continued fractions to convert any real number \(x\) into a rational approximation \(\frac{p}{q}\) by stopping the expansion once the approximation is close enough.

Derivation

Apply the same process as above to get \(a_0, a_1, \ldots\) from \(x\). Then compute the convergents using:

\[ \begin{aligned} A_{-1} &= 1, & A_0 &= a_0 \\ B_{-1} &= 0, & B_0 &= 1 \\ A_k &= a_k A_{k-1} + A_{k-2} \\ B_k &= a_k B_{k-1} + B_{k-2} \end{aligned} \]

Stop when \(\left| \frac{A_k}{B_k} - x \right| < \text{tolerance}\).

JavaScript Code

function floatToFraction(x, tolerance = 1e-9) {

    let A_k = 1, A_km1 = 0;
    let B_k = 0, B_km1 = 1;
    let t = x;

    do {
        const a_k = Math.floor(t);
        [A_k, A_km1] = [a_k * A_k + A_km1, A_k];
        [B_k, B_km1] = [a_k * B_k + B_km1, B_k];
        t = 1 / (t - a_k);
    } while (Math.abs(x - A_k / B_k) > tolerance);

    return [A_k, B_k];
}

Try It Yourself

Convert decimals like 2.718, 1.75, or 0.142857 to fractions:

If you are a JavaScript developer, check out ContinuedFraction.js which helps you with the math of continued fractions: