The idea: peel off the integer part, flip the rest
Take a number x. Write down its integer part a₀ = ⌊x⌋. The rest,
x − a₀, is between 0 and 1, so its reciprocal x₁ = 1/(x − a₀)
is bigger than 1. Do the same to x₁, then to x₂, and so on. The integer parts
a₀, a₁, a₂, … are the terms, and putting them back gives the
continued fraction
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + …))) = [a₀; a₁, a₂, a₃, …]![Peeling π: 3.14159 has integer part 3 and rest 0.14159; 1/0.14159 = 7.06251 gives 7; then 15.99659 gives 15, 1.00342 gives 1 and 292.63 gives 292. On the right the terms form the staircase 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + …)))), so π = [3; 7, 15, 1, 292, …]](Images/continued-fractions/peel.svg)
The page draws three panels: PEEL (one row per term, the flipped rest flies to the next row), NESTED FRACTION (the terms as a staircase) and CONVERGENTS (the fractions you get by cutting the staircase off). Demo: π gives 22/7 and 355/113 runs all three for π.
For a fraction it is Euclid's algorithm
If x = p/q, the integer part is the quotient and the rest is the remainder:
p = a·q + r, so x = a + r/q, and flipping the rest gives q/r. The next
row works on the pair (q, r): that is exactly the
Euclidean algorithm. The terms are Euclid's quotients,
and the expansion ends when the remainder is 0. So every fraction has a
finite continued fraction, and every finite one is a fraction.
| Euclid row | term | flip |
|---|---|---|
| 415 = 4·93 + 43 | a₀ = 4 | 93/43 |
| 93 = 2·43 + 7 | a₁ = 2 | 43/7 |
| 43 = 6·7 + 1 | a₂ = 6 | 7/1 |
| 7 = 7·1 + 0 | a₃ = 7 | stop |
So 415/93 = [4; 2, 6, 7] (Demo: 415/93 is Euclid's algorithm). For 1071/462 the last divisor is the gcd 21, and the last convergent is the fraction in lowest terms, 51/22 (Demo: 1071/462 reduces to 51/22).
Convergents: cut the fraction off
Stopping after aₖ gives a fraction hₖ/kₖ, the k-th convergent. You do not have to simplify the nested fraction each time. Two seeds and one rule do it:
h₋₂ = 0, h₋₁ = 1 hₖ = aₖ·hₖ₋₁ + hₖ₋₂
k₋₂ = 1, k₋₁ = 0 kₖ = aₖ·kₖ₋₁ + kₖ₋₂For π: h₁ = 7·3 + 1 = 22 and k₁ = 7·1 + 0 = 7, so the second convergent is 22/7. The convergents land on alternate sides of x, each one closer than the last.
| number | continued fraction | convergents |
|---|---|---|
| π | [3; 7, 15, 1, 292, …] | 3, 22/7, 333/106, 355/113, 103993/33102 |
| √2 | [1; 2, 2, 2, …] | 1, 3/2, 7/5, 17/12, 41/29, 99/70 |
| e | [2; 1, 2, 1, 1, 4, 1, 1, 6, …] | 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71 |
| φ | [1; 1, 1, 1, …] | 1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21 |
Best rational approximations: 22/7 and 355/113
A fraction h/k is a best approximation of x if no fraction with a denominator up to k is closer. Every convergent from k = 1 on is one. The page checks it by brute force: for every denominator d up to kₖ it takes the nearest p/d and marks the row ✓ if none beats the convergent. Only a₀/1 can fail, because ⌊x⌋ rounds down: for e, 3/1 is closer than 2/1 (Demo: e).
The error is less than 1/kₖ², and more exactly about
1/(kₖ·kₖ₊₁). So a big next term makes a convergent
unusually good. 355/113 is followed by 292: it is correct to 6 decimals
(3.1415929 against 3.1415927), far better than its denominator promises. The Chinese
astronomer Zu Chongzhi found it around 480 AD.
Patterns: square roots repeat, φ is all ones
A fraction ends; π shows no pattern at all. But square roots of whole numbers repeat: √2 = [1; 2, 2, 2, …] (Demo: √2), because √2 − 1 = 1/(√2 + 1) and √2 + 1 = 2 + (√2 − 1). Lagrange proved that the repeating ones are exactly the roots of quadratic equations. The number e has the pattern 1, 2k, 1.
The golden ratio φ = (1 + √5)/2 solves φ = 1 + 1/φ, so every term is 1 (Demo: golden ratio φ, all ones). Its convergents are ratios of Fibonacci numbers (see Fibonacci numbers), and with the smallest possible terms they close in as slowly as possible: φ is the irrational number that is hardest to approximate by fractions. That is also why consecutive Fibonacci numbers are Euclid's worst case, and why sunflowers use the golden angle: see The Sunflower Spiral.
| number | continued fraction |
|---|---|
| fraction p/q | finite (Euclid's quotients) |
| √n, roots of quadratics | infinite, repeating |
| e | infinite, pattern 1, 2k, 1 |
| π | infinite, no known pattern |
See also Prime Factorization for another way to reduce a fraction, and Monte Carlo π for a much slower way to estimate π.
What the page leaves out
Reals are peeled with ordinary floating-point numbers, so only the first few terms are shown (doubles lose about two digits per large term). Real code expands √n with exact integer arithmetic, and uses convergents to solve Pell's equation x² − n·y² = 1. Semiconvergents (intermediate fractions between two convergents), the Stern–Brocot tree, negative numbers and generalized continued fractions with numerators other than 1 are not shown.