Continued Fraction Expansion Calculator

What Is a Continued Fraction? A continued fraction represents a number as an integer plus a fraction whose denominator is itself an integer plus a fraction, and so on: x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + …))) Written compactly as [a₀; a₁, a₂, a₃, …] where the aᵢ are called partial quotients. The aᵢ are always positive integers (except a₀, which can be any integer).

Computing the Expansion The algorithm is identical to the Euclidean algorithm for GCD: Step 1: a₀ = floor(x). Set x₁ = 1/(x − a₀). Step 2: a₁ = floor(x₁). Set x₂ = 1/(x₁ − a₁). Repeat until aᵢ = 0 (rational number terminates) or desired precision is reached.

Rational Numbers Terminate Every rational number has a finite continued fraction expansion. Example: 355/113 = [3; 7, 16] — just three terms! Irrational numbers have infinite continued fraction expansions.

Famous Continued Fractions Golden ratio φ = (1+√5)/2 = [1; 1, 1, 1, 1, …] — all 1s. This makes it the “hardest” number to approximate rationally. √2 = [1; 2, 2, 2, 2, …] — all 2s after the first. e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …] — regular pattern with 2n appearing. π = [3; 7, 15, 1, 292, 1, 1, 1, 2, …] — seemingly irregular (no known pattern). The large partial quotient 292 in π explains why 355/113 is such an excellent approximation (error < 3×10⁻⁷).

Convergents: Best Rational Approximations Convergents are the fractions obtained by truncating the continued fraction: p₀/q₀ = a₀/1, p₁/q₁, p₂/q₂, … Each convergent is the best rational approximation with that denominator size. Recurrence: pₙ = aₙ × pₙ₋₁ + pₙ₋₂, qₙ = aₙ × qₙ₋₁ + qₙ₋₂. The convergents alternate above and below the true value.

Connection to the Euclidean Algorithm Computing the continued fraction expansion of p/q is equivalent to running the Euclidean algorithm on p and q. The number of steps = the number of partial quotients. The GCD appears as the last nonzero remainder. Lamé’s theorem (1844): Fibonacci numbers give the worst case — maximum steps for a given size.

Applications Gear ratios: engineers use convergents to find simple gear trains that approximate irrational speed ratios. Calendar design: the Julian calendar approximation 365.25 comes from [365; 4]. Planetary motion: Kepler’s laws involve near-resonances described by continued fractions. Cryptography: continued fractions appear in Wiener’s attack on RSA with small private keys.