The oldest algorithm, drawn as a tiling

Euclid’s algorithm is around 2,300 years old and is still the method every computer uses to reduce a fraction. In its modern form it is three lines:

while b ≠ 0:
    a, b = b, a mod b
return a

Correct, fast, and completely silent about why it works — the same complaint that can be made of the formula for a matrix inverse, and answered the same way. The geometric version says the same thing and explains itself as it goes.

Peeling squares #

Take a rectangle whose sides are whole numbers — 34 by 13, say. Cut off the largest square that fits. Then cut the largest square that fits in what remains. Repeat.

The final square has side 1, so $\gcd(34, 13) = 1$: the two numbers share no common measure larger than the unit.

Why does the last square give the greatest common divisor? Because of what a common divisor is, geometrically. A number $d$ divides both 34 and 13 exactly when a $d \times d$ tile can pave the whole rectangle edge to edge with none left over. And here is the thing worth noticing: if $d$ paves the original rectangle, it must also pave every square peeled off it, and therefore it must pave whatever remains after peeling. The leftover rectangle at each stage has exactly the same set of common measures as the one it came from.

So the process preserves the answer while making the rectangle smaller. When it finally terminates — with a rectangle that a single square fills perfectly — the side of that square is the largest tile that paves everything, all the way back up the chain.

Try one where the answer is not 1:

Why it always stops #

Each step strictly shrinks the shorter side of the rectangle, and the sides are whole numbers, so the sequence of shorter sides is a strictly decreasing sequence of positive integers. There are only finitely many of those below any starting value, so the process cannot run forever.

That is a genuine proof, and it is the same argument as the one hiding inside the three-line loop — a mod b is strictly less than b — but the geometry makes the shrinking visible rather than arithmetical.

A natural follow-up: what makes the algorithm slow? It is slowest when each step peels off exactly one square, because that is the least progress a step can make. Rectangles with that property have their sides in a very particular ratio:

This is Lamé’s theorem, proved in 1844 and generally credited as the first analysis of an algorithm’s running time in the modern sense: the number of steps Euclid’s algorithm takes on inputs below $N$ is at most about $\log_\varphi N$, where $\varphi$ is the golden ratio, and consecutive Fibonacci numbers achieve the bound.

The golden ratio’s appearance here is not decoration, any more than pi’s appearance in a needle-dropping experiment is. A rectangle whose sides are in the ratio $\varphi : 1$ has the property that peeling off one square leaves a rectangle of the same shape. Fibonacci ratios are the whole-number approximations to that, so they are precisely the inputs on which the algorithm makes the least progress per step.

The worst case is not the typical case, and the distance between them is worth measuring rather than assuming. Run the algorithm on four hundred thousand random pairs below a million. The slowest pair available is $1{,}346{,}269$ and $832{,}040$ — consecutive Fibonacci numbers, as Lamé requires — and it takes $29$ steps, against a bound of $\log_\varphi 10^6 = 28.7$, so the bound is tight. The average over the four hundred thousand random pairs is $11.2$, and the worst that turned up by chance was $23$.

How that average grows is the more interesting half. Repeating the experiment at a thousand, ten thousand, a hundred thousand and a million gives means of $5.39$, $7.33$, $9.27$ and $11.21$: a straight line in $\log N$, rising by $1.94$ steps for each factor of ten. That slope has a closed form, and it is not one anybody would guess from a picture of squares —

$$\frac{12\ln 2}{\pi^2} = 0.842766\ldots$$

steps per unit of $\ln N$, which is $1.9405$ per decade against the $1.940$ measured. The result is Heilbronn’s and Dixon’s, from the end of the 1960s, and the $\pi^2$ in it comes from the distribution of the continued-fraction terms — which is to say, from how often a run in the tiling happens to have length one, two, three. Nothing about rectangles put it there.

So the algorithm runs about two and a half times faster on a typical input than on its worst, both bounds are logarithmic, and that is why no better one has ever been needed. It is also one more case of $\pi$ turning up in a problem with no circle anywhere in it.

The sequence of counts is a continued fraction #

The tiling above produced squares in runs: two of size 13, then one of 8, one of 5, one of 3, one of 2, then two of 1. Those run-lengths — $2, 1, 1, 1, 1, 2$ — are not incidental. They are the continued fraction expansion of the ratio:

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

Every step of the tiling asks “how many copies of the current square fit before the shape changes?”, and the answers, in order, are the terms of the continued fraction. Two descriptions that look unrelated turn out to be one procedure watched from different angles — the same coincidence that makes four curves out of one cone. The algorithm for reducing fractions and the algorithm for expanding them into continued fractions are the same algorithm, watched from two angles.

Subtracting is not dividing #

There is a fork in the algorithm that the tiling makes unusually easy to see, and it is the difference between an algorithm that is fast and one that is famously not.

Euclid’s own procedure, as the Greeks ran it, was repeated subtraction: take the smaller length away from the larger, and keep going. In the picture that is peeling off one square at a time. The modern three-line version uses a mod b, which is repeated subtraction done all at once — peeling off an entire run of equal squares in a single step.

On most inputs the difference is unremarkable, because most runs are short. On the wrong input it is the difference between an instant and a lifetime. Take $\gcd(1,\, 1{,}000{,}000{,}000)$. The division version answers in one step: the remainder is zero immediately. The subtraction version peels a $1 \times 1$ square off a $1 \times 10^9$ rectangle, then another, then another, a billion times, all of them identical, arriving at the same answer having done a billion times the work.

The tiling shows exactly where the waste is. A run of identical squares carries no information beyond its length — the shape does not change until the run ends — so counting them one at a time is paying per square for a number that could have been obtained by one division. The continued fraction is precisely the list of run lengths, which is to say precisely the list of the moments where something actually happened.

This also sharpens what Lamé’s theorem is about. The Fibonacci worst case is slow for the division version because every run has length one, so no division ever gets to skip anything: the two algorithms coincide exactly on the inputs where there is nothing to skip. That is the honest statement of the bound. Division is not faster than subtraction in general — it is faster by however much the runs are longer than one, and on the golden-ratio rectangle they never are.

There is a footnote for anyone implementing it. On a machine, division is the expensive instruction and subtraction the cheap one, which reopens the question. The binary GCD algorithm exploits this: it removes factors of two by shifting, subtracts, and never divides at all, and on hardware where division costs a great deal more than shifting it wins despite taking more steps. Which is the reliable shape of these things — the step count and the cost are two different quantities, and the picture only draws the first. The same gap appears wherever a drawing is used to reason about work: rectangles under a curve get more accurate as they get narrower, and the drawing says nothing at all about what each additional rectangle costs to evaluate.

What happens when it never stops #

Now the interesting part. Nothing in the square-peeling construction requires the sides to be whole numbers. It can be run on any rectangle at all. So run it on a rectangle whose sides are 1 and $\sqrt{2}$.

It never terminates.

The peeling goes on producing squares forever, each smaller than the last, and no stage ever comes out exact. The Greeks had a word for the procedure — anthyphairesis, roughly “reciprocal subtraction” — and its failure to terminate on certain rectangles was, for them, the discovery that some pairs of lengths have no common measure at all. There is no tile, however small, that paves both a unit square’s side and its diagonal — and it is the Pythagorean theorem that puts $\sqrt2$ there in the first place.

This is the incommensurability of $\sqrt{2}$, and it arrives here as a statement about a process rather than about a number. There is no need to say “irrational”, or even to have the concept: the claim is simply that a certain construction does not stop. The connection to the Pythagorean theorem is direct, since the diagonal of the unit square is where $\sqrt{2}$ comes from in the first place. The theorem that made Greek geometry powerful also produced the object that broke its arithmetic.

The usual proof of irrationality — assume $\sqrt2 = p/q$ in lowest terms, derive that $p$ and $q$ are both even, contradiction — is shorter. But it is a proof by contradiction, and it leaves behind no picture of what irrationality is. The tiling leaves a very clear one: an infinite regress of squares, never quite closing.

Continued fractions inherit this cleanly. A rational number has a finite continued fraction; an irrational one has an infinite fraction that never repeats a terminating pattern. And $\sqrt{2}$, run through the peeling process, gives the run-lengths $1, 2, 2, 2, 2, \ldots$ — one square, then two forever. The regress is not chaotic. It is perfectly regular, and perfectly endless, which is a considerably stranger thing to be.

What the picture cannot show #

The tiling shows termination beautifully and non-termination only by implication. Nine squares are drawn for $1 : \sqrt{2}$, the tenth would be a few pixels across, and after that there is nothing to look at — so the picture demonstrates that the process has not yet stopped, which is not the same as demonstrating that it never will.

The gap is closed by an argument rather than by the drawing: at each stage the leftover rectangle for $1 : \sqrt{2}$ is similar to the one before, scaled down by a fixed factor. A shape similar to its own descendant can never reach zero, because reaching zero would make it similar to nothing. That self-similarity is the real content, and the picture can only gesture at it.

It is worth noticing how different this is from the integer case, where termination is guaranteed by a counting argument — a decreasing sequence of positive integers must stop — that needs no picture at all.

There is a sharper version of this limitation, and it applies to the world rather than to the drawing. Run the peeling on two physical lengths — a real rod and a real diagonal, measured with a real instrument. No finite number of steps can ever establish that the process will not terminate. Every measurement carries a tolerance, and any two lengths known to within a tolerance are consistent with some pair of whole numbers in that ratio. Incommensurability is not an observable property.

This is not a quibble about precision. It is a statement about what kind of fact irrationality is. The Greeks did not discover that the diagonal of a square is incommensurable with its side by measuring anything; the measurement would have been consistent with $99/70$, which is right to four decimal places and was in fact used as the value. They discovered it by proving that a construction cannot close, which is a claim no experiment reaches. A picture drawn from measurements can only ever say not yet.

That distinction — between properties an instrument can settle and properties only an argument can settle — is one of the more durable divisions in the subject, and this is the oldest place it shows up. It is the same wall that dropping needles on a floor runs into from the other side: an experiment can produce a number resembling $\pi$ to two places and can never produce the fact that $\pi$ is what it is.

The habit #

What the tiling does is turn a question about numbers into a question about whether a physical process halts. That translation is worth having on hand. It converts “do these two lengths have a common measure?” into “does this cutting procedure terminate?”, and the second question has a visible answer.

The same instinct — replace a property with a process, then watch the process — shows up again in the sphere with one point removed, where an infinite plane is matched with a finite surface by asking where a moving line lands. Different subject, same move. It is also what makes the integral definable: “what is the area?” becomes “does this sequence of approximations converge?”, and the second question has a checkable answer.

The ladder from here #

The rungs above this one: the algorithm’s extended form, which produces not just the gcd but the coefficients that express it as a combination of the inputs — the fact that makes modular inverses and public-key cryptography possible. Continued fractions in their own right, and the sense in which the truncations are the best possible rational approximations. Ford circles and the Stern–Brocot tree, which lay every rational out in a structure the algorithm walks. The same peeling in the Gaussian integers, where “largest square that fits” still makes sense and the gcd is complex. Lamé’s bound in full, as the first analysis of an algorithm’s running time. And the continued fraction of $\varphi$, all ones forever, which makes the golden ratio the hardest number of all to approximate by fractions — the reason it governs phyllotaxis and packing, and a claim that deserves its own essay and its own picture rather than a sentence here.