Case Study · Math · Number Theory
The Best Rational Approximations
The idea
There is a folder in my GitHub history called RepeatedFractions, a placeholder made when continued fractions first struck me as beautiful, and this page is what it was waiting for. A continued fraction rewrites a number as a tower of nested reciprocals,
which is compact enough to write as the list of its integer terms, . The terms come out of a loop that is Euclid’s algorithm wearing different clothes: take the integer part, subtract it, invert the remainder, repeat.
What makes this more than a notation is the convergents: truncate the tower at term and you get a fraction , and those fractions are the best rational approximations of in the strongest available sense. No fraction with a denominator up to comes closer than does. That is a remarkable guarantee, and it is why every good rational approximation you have ever met, 22/7 for pi, 355/113 for pi to six places, is a continued-fraction convergent whether its discoverer knew it or not.
The plate below is the algorithm made concrete: pick a famous constant or type an expression of your own and watch the terms, convergents, and error fall out. The rest of this page is what those terms are telling you.
φ = [1; 1, 1, 1, 1, 1, 1, 1, 1, …]
| k | term aₖ | convergent | value | error |
|---|---|---|---|---|
| 0 | 1 | 1/1 | 1.00000000 | 6.2e-1 |
| 1 | 1 | 2/1 | 2.00000000 | 3.8e-1 |
| 2 | 1 | 3/2 | 1.50000000 | 1.2e-1 |
| 3 | 1 | 5/3 | 1.66666667 | 4.9e-2 |
| 4 | 1 | 8/5 | 1.60000000 | 1.8e-2 |
| 5 | 1 | 13/8 | 1.62500000 | 7.0e-3 |
| 6 | 1 | 21/13 | 1.61538462 | 2.6e-3 |
| 7 | 1 | 34/21 | 1.61904762 | 1.0e-3 |
| 8 | 1 | 55/34 | 1.61764706 | 3.9e-4 |
Quadratic irrational (algebraic, degree 2)
The terms fall into a repeating block (period 1: 1). A continued fraction is eventually periodic exactly when the number is a root of a quadratic (Lagrange), so this reads as an algebraic irrational. Heuristic read of the partial quotients, not a proof.
Zoom on φ: every convergent is a ratio of consecutive Fibonacci numbers, 1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, … Because each term is 1, the recurrence p_k = p_{k-1} + p_{k-2} is the Fibonacci rule itself, so p_k = F(k+2) and q_k = F(k+1), and F(k+2)/F(k+1) → φ.
The approach
The engine is a five-line recurrence. Alongside the term loop, the convergents build up from two seed columns by
which is the whole algorithm; everything else in the plate is presentation. The interesting work is choosing the specimens, because the terms of a continued fraction are a fingerprint of what kind of number you are looking at:
- Rational numbers terminate. The loop is Euclid’s algorithm, so it halts exactly when the remainder hits zero, which is exactly when the number was a fraction to begin with.
- Quadratic irrationals are periodic. The square roots repeat forever in a cycle: , . Lagrange proved the equivalence, so a repeating continued fraction is the signature of “root of a quadratic.”
- e is patterned but not periodic: , the even numbers marching up the middle. Euler found this, and the non-repeating pattern is a proof that is irrational.
- The golden ratio is all ones, , and that is the punchline of the whole subject. A small term means a big jump in accuracy, so the number hardest to approximate by rationals is the one whose terms are all as small as they can be. That makes the “most irrational” number, and it is why so many growing things (sunflower florets, pinecone spirals, leaf arrangement) space themselves by the golden angle: it is the packing that never lines up, because no rational approximation of is ever good enough to make the spirals repeat.
Mediants, and the circles that kiss
Everything above comes out of the Euclidean algorithm: take a floor, subtract, invert, repeat. There is a second construction that produces the same fractions and never divides anything, and setting the two beside each other is the fastest way I know to see why the convergents are special rather than merely good.
Start with the Farey sequence : every fraction in in lowest terms whose denominator is at most , in ascending order, so that . What is worth staring at is what happens between adjacent terms. If and are next to each other in some , then
and conversely, any two fractions satisfying that determinant condition are neighbours at some level. That is an unreasonably strong statement about a sequence defined by nothing more than “sort the fractions with small denominators,” and the rest follows from it. The mediant of a neighbour pair is automatically already in lowest terms, it lies strictly between its parents, and it is the first fraction ever to appear between them: the gap stays empty until level , at which point the mediant arrives and splits it in two.
Now the picture. Sit a circle on top of each fraction , tangent to the number line at , with centre and radius . These are Ford circles, and the squared denominator is not decoration. Write for the distance between the centres of the circles at and ; every term involving the heights cancels, and what is left is
So two Ford circles are tangent exactly when , they are strictly separated whenever it is larger, and there is no third case: they never overlap, anywhere, at any denominator. The determinant condition and the tangency are one statement in two alphabets, which is why the plate lets you check either on any pair you point at. It checks with integers rather than with the geometry, and deliberately so: the floating-point distance between two kissing centres lands a few ulps to one side or the other of the sum of the radii, sometimes above and sometimes below, so a comparison of two doubles cannot be trusted to decide a question that four integers settle exactly. The readout prints both, and the disagreement between them is worth a look.
F₆ holds 13 fractions. |Fn| = 1 + Σ φ(k) for k ≤ n = 1 + 1 + 1 + 2 + 2 + 4 + 2 = 13.
Pick a fraction. Arrow keys move along the sequence.
Magnified, around the selection
Scaled to the selected circle, not to the interval. The two dots on the circle are where it touches its neighbours; the dot on the line is p/q itself. The dashed circles sitting in the cusps are the mediants, and each first appears at the level marked beneath it.
The neighbour test, on this pair
- Selected
- 2/5 = 0.4
- First appears in
- F₅, because a fraction in lowest terms arrives at level n = q
- Ford circle
- centre (0.4, 1/50) · radius 1/(2·5²) = 1/50
- Left neighbour
- 1/3
- Determinant q·r − p·s
- 3·2 − 1·5 = 1 · neighbours
- Circle gap, exactly
- d² − (r₁+r₂)² = (1² − 1)/(3²·5²) = 0 · tangent: the circles kiss, and the fractions are Farey neighbours
- Same gap in floating point
- d − (r₁+r₂) = 2.8e-17
- Right neighbour
- 1/2
- Determinant q·r − p·s
- 5·1 − 2·2 = 1 · neighbours
- Circle gap, exactly
- d² − (r₁+r₂)² = (1² − 1)/(5²·2²) = 0 · tangent: the circles kiss, and the fractions are Farey neighbours
- Same gap in floating point
- d − (r₁+r₂) = 0
- Mediant of the two neighbours
- (1+1)/(3+2) = 2/5 · the selection itself
- A non-neighbour, for contrast
- 3/5 · 5·3 − 2·5 = 5 · gap = (5² − 1)/625 = 0.0384 > 0, so these two circles do not touch
The mediant search: the same convergents, by the other road
Turn sequence LRLRLRLRLRLRLRLRLRLRLRLRLRLRLR
Its run lengths 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, … (the last run is cut short by the step cap)
Partial quotients of x [0; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …]
Convergents, by the Euclidean recurrence 0/1, 1/1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, …
The run lengths and the partial quotients are computed by separate routines that never consult each other, so the agreement between those two lines is a result rather than a construction. The marked rows below are the nodes this walk reached that are exactly the convergents 1/1, 1/2, 2/3, 3/5, 5/8, 8/13, …, arrived at by bisecting a bracket rather than by inverting a remainder. The unmarked rows between them are the semiconvergents: the best you can do while one partial quotient is still being spent.
| step | turn | bracket | mediant | value | convergent |
|---|---|---|---|---|---|
| 0 | root | 0/1 · 1/0 | 1/1 | 1 | p1/q1 |
| 1 | L | 0/1 · 1/1 | 1/2 | 0.5 | p2/q2 |
| 2 | R | 1/2 · 1/1 | 2/3 | 0.666666667 | p3/q3 |
| 3 | L | 1/2 · 2/3 | 3/5 | 0.6 | p4/q4 |
| 4 | R | 3/5 · 2/3 | 5/8 | 0.625 | p5/q5 |
| 5 | L | 3/5 · 5/8 | 8/13 | 0.615384615 | p6/q6 |
| 6 | R | 8/13 · 5/8 | 13/21 | 0.619047619 | p7/q7 |
| 7 | L | 8/13 · 13/21 | 21/34 | 0.617647059 | p8/q8 |
| 8 | R | 21/34 · 13/21 | 34/55 | 0.618181818 | p9/q9 |
| 9 | L | 21/34 · 34/55 | 55/89 | 0.617977528 | p10/q10 |
| 10 | R | 55/89 · 34/55 | 89/144 | 0.618055556 | p11/q11 |
| 11 | L | 55/89 · 89/144 | 144/233 | 0.618025751 | |
| 12 | R | 144/233 · 89/144 | 233/377 | 0.618037135 | |
| 13 | L | 144/233 · 233/377 | 377/610 | 0.618032787 | |
| 14 | R | 377/610 · 233/377 | 610/987 | 0.618034448 | |
| 15 | L | 377/610 · 610/987 | 987/1597 | 0.618033813 | |
| 16 | R | 987/1597 · 610/987 | 1597/2584 | 0.618034056 | |
| 17 | L | 987/1597 · 1597/2584 | 2584/4181 | 0.618033963 | |
| 18 | R | 2584/4181 · 1597/2584 | 4181/6765 | 0.618033999 | |
| 19 | L | 2584/4181 · 4181/6765 | 6765/10946 | 0.618033985 | |
| 20 | R | 6765/10946 · 4181/6765 | 10946/17711 | 0.61803399 | |
| 21 | L | 6765/10946 · 10946/17711 | 17711/28657 | 0.618033988 | |
| 22 | R | 17711/28657 · 10946/17711 | 28657/46368 | 0.618033989 | |
| 23 | L | 17711/28657 · 28657/46368 | 46368/75025 | 0.618033989 | |
| 24 | R | 46368/75025 · 28657/46368 | 75025/121393 | 0.618033989 | |
| 25 | L | 46368/75025 · 75025/121393 | 121393/196418 | 0.618033989 | |
| 26 | R | 121393/196418 · 75025/121393 | 196418/317811 | 0.618033989 | |
| 27 | L | 121393/196418 · 196418/317811 | 317811/514229 | 0.618033989 | |
| 28 | R | 317811/514229 · 196418/317811 | 514229/832040 | 0.618033989 | |
| 29 | L | 317811/514229 · 514229/832040 | 832040/1346269 | 0.618033989 | |
| 30 | R | 832040/1346269 · 514229/832040 | 1346269/2178309 | 0.618033989 |
The walk starts at the Stern-Brocot root 1/1, bracketed by 0/1 and 1/0. For a target in (0, 1) the first turn is always left, and the bracket never returns to 1/0. The bracket is a Farey neighbour pair at every step, which is why its mediant is always already in lowest terms. Partial quotients are computed in ordinary floating point and are capped at twelve terms, so the tail of an irrational target is not to be trusted past a dozen or so; that is the same ceiling Plate I carries, and for the same reason.
That last panel is what ties the page together. Pick a target , bracket it between and , take the mediant, see which side of it falls on, keep that half, and repeat. This is a walk down the Stern-Brocot tree, and it is a binary search that never leaves the rationals: no remainders, no reciprocals, nothing but addition. Among the fractions it produces are, exactly, the convergents from the top of this page. For the walk turns L, R, R, L, L, R, R and passes through ; the plate marks , which are the convergents, and the unmarked ones between them are the semiconvergents, the intermediate best-so-far fractions you pass while a single partial quotient is still being spent. Then run-length encode the turn sequence, L, RR, LL, RR, and you get : the partial quotients themselves. The plate computes the walk and the expansion by separate routines that never consult each other, so the agreement on screen is a result and not an assertion.
Why the second picture earns its space is that it turns best approximation from a fact about error into a fact about packing. A denominator of buys a circle of radius , so precision is paid for in area, and the room the circles leave unfilled is where the irrationals have to live. A number is hard to approximate precisely when it threads a corridor the circles never crowd, and , whose turn sequence alternates L, R, L, R forever and never spends two consecutive steps going the same way, threads the tightest corridor there is. Plate I argues that with an inequality about denominators. Plate II is the same claim with the algebra taken out and the geometry left in, and I find I believe it more having seen both.
Scope, and what next
The plate computes in ordinary floating point, which sets a deliberate ceiling: past ten or so terms the accumulated rounding can invent spurious large terms for irrational inputs, because the algorithm is exquisitely sensitive to the tail of the number it is handed (feeding it 1.6180339887 is not the same as feeding it , and the difference surfaces within a dozen terms). Exact rational inputs sidestep this: a typed is expanded by integer Euclid, so it terminates exactly, the way the theory promises. For the irrationals the scope is “enough terms to see the pattern, not enough to trust the twentieth digit”; an arbitrary-precision version would carry the numbers symbolically, and that is the natural next step. What stayed with me is how much number theory is packed into the recurrence: the same five lines touch Euclid, Fibonacci, Pell’s equation, and the reason a piano’s twelve-tone scale works (2^(7/12) is a convergent-quality approximation of a perfect fifth). A good small algorithm is a door into a large subject, and this one opens onto most of classical number theory.