A fraction that never closes

Euclid’s algorithm takes a rectangle and peels the largest square off it, over and over, until nothing is left. Drawn as a tiling it computes a greatest common divisor. What this essay is about is the part of that process the greatest common divisor throws away: how many squares came off at each step.

The counts are $2, 1, 1, 1, 1, 2$. Everything else about the picture — the sizes, the positions, the colours — can be reconstructed from those six numbers and the starting rectangle’s shape, because each count says how many times the current short side goes into the current long one, and that is the only decision the algorithm ever makes.

Read as a sequence, the counts are a second name for the ratio $34/13$. Written out, that name looks like this:

$$\frac{34}{13} = 2 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{2}}}}}$$

The tower #

The nesting is the whole notation, and it is easier to look at than to typeset.

The reason the tower is the natural way to write the algorithm’s output is that each step of Euclid’s algorithm is a step of the tower. Peeling $q$ squares off an $a$ by $b$ rectangle leaves a $b$ by $r$ rectangle with $a = qb + r$; dividing through by $b$ gives

$$\frac{a}{b} = q + \frac{r}{b} = q + \cfrac{1}{\,b/r\,},$$

and $b/r$ is the next rectangle’s ratio. The recursion is the algorithm and the algorithm is the recursion. Nothing has been added; the fraction is the peeling, transcribed.

Written in a line the expansion is $[2; 1, 1, 1, 1, 2]$, with a semicolon after the whole-number part because that one is not like the others — it can be zero or negative, and the rest cannot.

One wrinkle is worth disposing of at once, because it is the only ambiguity in the notation. The last quotient can always be split: $[2; 1, 1, 1, 1, 2]$ and $[2; 1, 1, 1, 1, 1, 1]$ are the same number, since a final $2$ is $1 + 1/1$. Every rational therefore has exactly two expansions, one ending in a quotient above one and one ending in a quotient of one, and picking either convention makes the representation unique. This is the continued-fraction version of $0.999\ldots = 1$, and it has the same cause: a positional system with a degenerate case at the end.

Apart from that, the representation is completely rigid. Decimal expansions are not — they depend on a choice of base, and a number that looks tidy in base ten can look arbitrary in base seven. A continued fraction is built from the number’s own arithmetic and uses no base at all, which is why it can detect properties, like being the root of a quadratic, that no decimal expansion can see.

Terminating is the same as being a ratio #

Euclid’s algorithm on whole numbers always stops. Each remainder is strictly smaller than the last and they are all non-negative, so the sequence of remainders is a strictly decreasing sequence of whole numbers, which cannot go on forever. That is the standard termination argument and it is the reason a rational number has a finite continued fraction.

Turn it around and the statement becomes interesting. If the peeling never stops, the sides had no common measure at all — because a common measure would have to divide every remainder, and the remainders are getting smaller than any fixed length.

$\sqrt{2}$ has expansion $[1; 2, 2, 2, \ldots]$, repeating forever. The proof that it repeats is a single observation: after the first square is removed, the leftover strip has the same proportions as a strip that appeared earlier, so the algorithm is in a state it has been in before and must do the same thing again.

That self-similarity is the whole of it. The peeling never terminates, so $\sqrt{2}$ is not a ratio of whole numbers — which is the irrationality proof in a form Euclid’s contemporaries would have recognised, since to them incommensurability was exactly this: two lengths with no common unit.

The one that repeats fastest #

Every quotient in an expansion measures how much of the current rectangle the current square accounts for. A large quotient means the square nearly fills the rectangle and very little is left over; a quotient of one means the square barely gets started and almost everything is left.

The golden ratio’s expansion is $[1; 1, 1, 1, \ldots]$, all ones, which is the extreme case in a precise sense: no expansion can have smaller quotients, because a quotient of zero would mean the short side is longer than the long one.

That self-reference is the same fact as the self-similarity of the rectangle, and it is why the golden ratio keeps appearing in places that have nothing to do with each other. A shape that reproduces itself after one operation and a number that reproduces itself after one operation are the same object described in two languages, which is the connection this collection has already met from the geometric side.

The convergents #

Stopping the tower early gives a fraction. Stopping at each level in turn gives a sequence of them, and the sequence is the reason continued fractions are worth having.

For $\varphi$ the convergents are $1/1$, $2/1$, $3/2$, $5/3$, $8/5$, $13/8$: consecutive Fibonacci numbers, which is the second place that sequence turns up in this picture and the first place it is inevitable. The recurrence that builds convergents from quotients is

$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$

and when every $a_k$ is one, that is the Fibonacci recurrence with no room for anything else to happen.

Two properties make the convergents useful rather than merely available. They alternate around the value, so any two consecutive ones bracket it. And neighbouring convergents satisfy

$$p_k q_{k-1} - p_{k-1} q_k = \pm 1,$$

a determinant of one, which says the two fractions are as close together as two fractions with those denominators can possibly be. Everything about how well continued fractions approximate follows from that single identity, and it is checked in every figure on this page that draws a convergent.

How good the approximations are #

The determinant identity gives a bound immediately: $|x - p_k/q_k| < 1/(q_k q_{k+1})$, and since $q_{k+1} > q_k$ that is better than $1/q_k^2$. A fraction that accurate is not something a search would find; the denominators that work are rare.

$\pi$’s spike is $355/113$, accurate to seven decimal places with a three-digit denominator, and it is a direct consequence of the quotient $292$ appearing early in $\pi$’s expansion $[3; 7, 15, 1, 292, \ldots]$. A large quotient means the previous convergent was already very good — the square nearly filled the rectangle — so a big number in the expansion is a announcement that an unusually accurate fraction has just gone past.

$\varphi$, with all quotients equal to one, never announces anything. Its convergents are as bad as convergents are allowed to be, and this is the precise sense in which the golden ratio is the hardest number to approximate by fractions. The pigeonhole argument gives a floor that every irrational must beat infinitely often; $\varphi$ beats it and does no better, forever.

What the picture cannot show #

The peeling figures stop at nine steps because a drawing has to stop somewhere, and where they stop is where the interesting behaviour of most numbers begins.

For $\sqrt{2}$ and $\varphi$ the picture is honest, because the expansions repeat and nine steps show the whole pattern. Lagrange proved in 1770 that this happens exactly for the quadratic irrationals — the roots of quadratics with whole-number coefficients — so a repeating expansion is a complete characterisation of one kind of number, which is a rare thing to have.

For everything else the drawing shows a beginning and nothing more. $e$ has expansion $[2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$, a pattern that continues but is not periodic. $\pi$ has no known pattern at all, and whether its quotients are bounded is an open question: nobody can rule out a quotient of a billion appearing somewhere, which would mean an astonishingly good rational approximation to $\pi$ that no one has found.

So the figures show a mechanism working and cannot show what it produces in the long run. That is the standing limitation of everything in this field, and it is sharper here than elsewhere: the algorithm is completely deterministic, entirely elementary, and its output for the most famous constant in mathematics is not understood.

What is known is statistical, and it has a strange shape. Gauss observed, and Kuzmin proved in 1928, that for almost every real number the quotients follow a fixed distribution: a quotient equals $k$ with probability $\log_2(1 + 1/k(k+2))$, so about $41\%$ of quotients are $1$, about $17\%$ are $2$, and large quotients are rare but not rare enough for their average to exist. The geometric mean of the quotients converges to Khinchin’s constant, $2.685\ldots$, for almost every number — and it is not known whether $\pi$, $e$ or $\sqrt2$ is one of them. The theorem covers everything except every number anybody can name, which is a pattern that also afflicts random walks and normal numbers: the typical case is completely understood and no specific case is.

The calendar, and a gear train #

The reason continued fractions were developed is not the reason they are taught. They were developed because somebody needed to approximate an awkward ratio with a fraction whose denominator was small enough to build.

The year is about $365.2422$ days long. The fractional part, expanded, is $[0; 4, 7, 1, 3, 5, \ldots]$, and its convergents are $\tfrac14$, $\tfrac{7}{29}$, $\tfrac{8}{33}$, $\tfrac{31}{128}$.

The Julian calendar takes the first convergent, $\tfrac14$: one leap year in four. That overshoots by about eleven minutes a year, which is three days in four centuries, and by 1582 the accumulated error had moved the equinox by ten days. The Gregorian reform uses $\tfrac{97}{400}$ — leap years except centuries, except centuries divisible by four hundred — which is not a convergent but is very close to $\tfrac{31}{128}$, and is accurate to about one day in three thousand years.

The interesting question is why the reform chose four hundred rather than the better and simpler $128$. The answer is that a rule has to be usable by people who are not doing arithmetic, and dividing by four hundred is easy in a decimal-and-century calendar while dividing by $128$ is not. The mathematics offers the optimal denominators; the choice among them is made on other grounds entirely.

Huygens faced the same problem with no such escape. Building a mechanical planetarium in 1680, he needed gears whose tooth counts were in the ratio of Saturn’s period to the Earth’s — $77{,}708{,}431$ to $2{,}640{,}858$ — and no workshop cuts a gear with seventy-seven million teeth. He expanded the ratio as a continued fraction and took a convergent: $206/7$. The error is under a thousandth of a percent, and the gears are small enough to make. This is the earliest clear use of the convergents as the answer to “what is the best small approximation”, and it comes from a workshop rather than from a proof.

What the algorithm costs #

Every quotient equal to one is also the worst case for the algorithm’s running time, and the two facts are the same fact.

Peeling one square per step removes as little as possible, so the number of steps is as large as it can be for the size of the numbers involved. The rectangles where this happens are the ones with consecutive Fibonacci numbers as sides — $34$ and $21$, then $21$ and $13$, and so on down. That is Lamé’s theorem, from 1844: the number of steps Euclid’s algorithm takes is at most about $\log_\varphi$ of the smaller number, with equality exactly for Fibonacci pairs.

Lamé’s result is often described as the first analysis of an algorithm’s worst case, some hundred and thirty years before that became a subject. What makes it work is that the worst case is not found by searching — it is read off the observation that small quotients mean slow progress, and the sequence with the smallest possible quotients is forced.

The practical consequence is a good one. Even the worst case is logarithmic, so Euclid’s algorithm on two numbers of a thousand digits takes a few thousand steps rather than anything alarming, and it remains the method actually used.

It also explains a piece of engineering folklore. A hash table whose stride is chosen as a fraction of its size performs best when that fraction is hard to approximate — because a stride close to a simple ratio revisits a few residues quickly, and a stride close to $\varphi$ spreads out for as long as possible before repeating. The property that makes the golden ratio the slowest case for Euclid’s algorithm makes it the best case for anything wanting to avoid a pattern, and the two statements are the same statement with the sign flipped.

Where the ladder goes next #

The convergents raise a question this essay has only gestured at: they are the best approximations, and “best” needs a definition and a proof. That is how close a fraction can get, which reaches the same fractions from a completely different direction — a pigeonhole argument with no algorithm in it anywhere.

The determinant of one that makes the convergents work is also the rule that generates every fraction exactly once, in a tree whose left-and-right paths turn out to be continued fraction expansions in disguise. And the non-terminating peel, taken as an argument rather than an illustration, is the classical proof that $\sqrt{2}$ is irrational — with the arithmetic that this essay left implicit made exact and drawn as a shrinking square.