Gregory Friedman The Greg Wide Web on the name →

Case Study · Math · Number Theory

The Best Rational Approximations

2026

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,

x=a0+1a1+1a2+1a3+⋯,x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}},

which is compact enough to write as the list of its integer terms, [a0;a1,a2,a3,… ][a_0; a_1, a_2, a_3, \dots]. 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.

ak=⌊xk⌋,xk+1=1xk−ak.a_k = \lfloor x_k \rfloor, \qquad x_{k+1} = \frac{1}{x_k - a_k}.

What makes this more than a notation is the convergents: truncate the tower at term kk and you get a fraction pk/qkp_k / q_k, and those fractions are the best rational approximations of xx in the strongest available sense. No fraction with a denominator up to qkq_k comes closer than pk/qkp_k/q_k 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.

Terms k
9

φ = [1; 1, 1, 1, 1, 1, 1, 1, 1, …]

Nested form
1 + 11 + 11 + 11 + 11 + 11 + …
Convergent values
2.081.791.51.210.92012345678target 1.618term kconvergent value
Convergent error
1e01e-21e-4012345678term k|error| (log scale)
Continued-fraction convergents. Each row gives the term, the convergent as a fraction, its decimal value, and the absolute error against the target number.
kterm aₖconvergentvalueerror
011/11.000000006.2e-1
112/12.000000003.8e-1
213/21.500000001.2e-1
315/31.666666674.9e-2
418/51.600000001.8e-2
5113/81.625000007.0e-3
6121/131.615384622.6e-3
7134/211.619047621.0e-3
8155/341.617647063.9e-4
Heuristic read

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) → φ.

Plate I Any positive number, expanded. Pick a constant or type an expression of your own (sqrt(2), 1/sqrt(2), 355/113); set how many terms k to compute, then read off the nested-fraction tower, the convergents as fractions, and a log-scale plot of how fast the error falls. A heuristic read of the terms sorts the number by kind (rational, quadratic, or transcendental-looking). Watch φ crawl (all ones, the slowest possible) against π, whose term 292 makes 355/113 leap to six-decimal accuracy in a single step.

The approach

The engine is a five-line recurrence. Alongside the term loop, the convergents build up from two seed columns by

pk=ak pk−1+pk−2,qk=ak qk−1+qk−2,p_k = a_k\,p_{k-1} + p_{k-2}, \qquad q_k = a_k\,q_{k-1} + q_{k-2},

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: 2=[1;2,2,2,… ]\sqrt 2 = [1; 2, 2, 2, \dots], 3=[1;1,2,1,2,… ]\sqrt 3 = [1; 1, 2, 1, 2, \dots]. Lagrange proved the equivalence, so a repeating continued fraction is the signature of “root of a quadratic.”
  • e is patterned but not periodic: [2;1,2,1,1,4,1,1,6,… ][2; 1, 2, 1, 1, 4, 1, 1, 6, \dots], the even numbers marching up the middle. Euler found this, and the non-repeating pattern is a proof that ee is irrational.
  • The golden ratio is all ones, φ=[1;1,1,1,… ]\varphi = [1; 1, 1, 1, \dots], 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 φ\varphi 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 φ\varphi 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 FnF_n: every fraction in [0,1][0, 1] in lowest terms whose denominator is at most nn, in ascending order, so that F5=01,15,14,13,25,12,35,23,34,45,11F_5 = \tfrac{0}{1}, \tfrac{1}{5}, \tfrac{1}{4}, \tfrac{1}{3}, \tfrac{2}{5}, \tfrac{1}{2}, \tfrac{3}{5}, \tfrac{2}{3}, \tfrac{3}{4}, \tfrac{4}{5}, \tfrac{1}{1}. What is worth staring at is what happens between adjacent terms. If p/qp/q and r/sr/s are next to each other in some FnF_n, then

∣ps−qr∣=1,|ps - qr| = 1,

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 (p+r)/(q+s)(p+r)/(q+s) 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 q+sq+s, at which point the mediant arrives and splits it in two.

Now the picture. Sit a circle on top of each fraction p/qp/q, tangent to the number line at p/qp/q, with centre (p/q, 1/(2q2))(p/q,\ 1/(2q^2)) and radius 1/(2q2)1/(2q^2). These are Ford circles, and the squared denominator is not decoration. Write dd for the distance between the centres of the circles at p/qp/q and r/sr/s; every term involving the heights cancels, and what is left is

d2−(r1+r2)2=(ps−qr)2−1(qs)2.d^{2} - (r_1 + r_2)^{2} = \frac{(ps - qr)^{2} - 1}{(qs)^{2}}.

So two Ford circles are tangent exactly when ∣ps−qr∣=1|ps - qr| = 1, 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.

Denominator cap n
n = 6
Target x in (0, 1)

F₆ holds 13 fractions. |Fn| = 1 + Σ φ(k) for k ≤ n = 1 + 1 + 1 + 2 + 2 + 4 + 2 = 13.

0/11/41/32/51/22/33/41/12/5x = 0.61803
In F6 already New at this n (denominator exactly n) Selected Both axes use the same scale, so the tangencies are real. The two circles of radius 1/2, at 0/1 and 1/1, run off the top of the frame.

Pick a fraction. Arrow keys move along the sequence.

Magnified, around the selection

3/8 · F₈3/7 · F₇2/5window width 1.2e-1 · same scale on both axes

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.

The Stern-Brocot walk toward the target. Each row gives the step number, the turn taken, the bracketing Farey pair, the mediant reached, its value, and, where the two roads meet, which continued-fraction convergent it is.
stepturnbracketmediantvalueconvergent
0root0/1 · 1/01/11p1/q1
1L0/1 · 1/11/20.5p2/q2
2R1/2 · 1/12/30.666666667p3/q3
3L1/2 · 2/33/50.6p4/q4
4R3/5 · 2/35/80.625p5/q5
5L3/5 · 5/88/130.615384615p6/q6
6R8/13 · 5/813/210.619047619p7/q7
7L8/13 · 13/2121/340.617647059p8/q8
8R21/34 · 13/2134/550.618181818p9/q9
9L21/34 · 34/5555/890.617977528p10/q10
10R55/89 · 34/5589/1440.618055556p11/q11
11L55/89 · 89/144144/2330.618025751
12R144/233 · 89/144233/3770.618037135
13L144/233 · 233/377377/6100.618032787
14R377/610 · 233/377610/9870.618034448
15L377/610 · 610/987987/15970.618033813
16R987/1597 · 610/9871597/25840.618034056
17L987/1597 · 1597/25842584/41810.618033963
18R2584/4181 · 1597/25844181/67650.618033999
19L2584/4181 · 4181/67656765/109460.618033985
20R6765/10946 · 4181/676510946/177110.61803399
21L6765/10946 · 10946/1771117711/286570.618033988
22R17711/28657 · 10946/1771128657/463680.618033989
23L17711/28657 · 28657/4636846368/750250.618033989
24R46368/75025 · 28657/4636875025/1213930.618033989
25L46368/75025 · 75025/121393121393/1964180.618033989
26R121393/196418 · 75025/121393196418/3178110.618033989
27L121393/196418 · 196418/317811317811/5142290.618033989
28R317811/514229 · 196418/317811514229/8320400.618033989
29L317811/514229 · 514229/832040832040/13462690.618033989
30R832040/1346269 · 514229/8320401346269/21783090.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.

Plate II The Farey sequence of the unit interval, with a circle standing on each fraction: centre (p/q, 1/(2q²)), radius 1/(2q²), touching the number line at p/q and nowhere else. Step the denominator cap n and watch every new fraction arrive at exactly the level of its denominator, wedged into the cusp between the two circles that produced it. Adjacent circles touch and no others do, so the tangency you can see is the determinant condition |ps − qr| = 1 you can check in the panel beside it, worked out in integers on whichever pair you select. The inset is scaled to the selected circle rather than to the interval, because radii fall as one over two q squared and by n = 12 the small ones are a pixel across. The last panel runs a mediant search toward a target of your choosing and marks the nodes that turn out to be, exactly, the convergents Plate I computes by an entirely different algorithm.

That last panel is what ties the page together. Pick a target xx, bracket it between 0/10/1 and 1/11/1, take the mediant, see which side of it xx 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 1/2=[0;1,2,2,2,… ]1/\sqrt2 = [0; 1, 2, 2, 2, \dots] the walk turns L, R, R, L, L, R, R and passes through 1/1,1/2,2/3,3/4,5/7,7/10,12/171/1, 1/2, 2/3, 3/4, 5/7, 7/10, 12/17; the plate marks 1/1,2/3,5/7,12/171/1, 2/3, 5/7, 12/17, 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 1,2,2,21, 2, 2, 2: 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 qq buys a circle of radius 1/(2q2)1/(2q^2), 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 φ\varphi, 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 φ\varphi, and the difference surfaces within a dozen terms). Exact rational inputs sidestep this: a typed p/qp/q 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.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.