The Euclidean Algorithm, Drawn as a Single Straight Line

There’s a classical way to see Euclid’s algorithm as geometry. Here’s a different one — and a rule about when to trust the computer running it.

Most people who have met the geometric version of Euclid’s algorithm have met it in one form. Take a rectangle. Cut out the biggest square that fits. Look at what’s left, and repeat. The number of squares removed at each stage gives the partial quotients of a continued fraction, and the last square you cut is the greatest common divisor.

It’s a lovely picture and it’s very old. The Greeks called the underlying operation anthyphairesis — mutual subtraction — and it’s how Euclid handles ratio in the Elements. Book VII does it for whole numbers. Book X does it for lengths, and its second and third propositions between them contain the idea that still startles: two magnitudes are incommensurable exactly when the subtraction never stops.

I want to show you a different picture of the same thing. Nothing gets subdivided. Nothing gets removed. One straight line just keeps going.

The setup

Start with a rectangle — length L₁, breadth B₁ — and draw its diagonal. That diagonal has a slope, m = B₁/L₁. Hold onto it, because it never changes again. A straight line has exactly one slope, however far you extend it. That single fact does all the work below.

Now attach a second rectangle at the far end of the diagonal. Its dimensions are entirely up to you. Extend the same line into it.

The line has to leave that rectangle somewhere, and there are only three exits. It runs out of height before it runs out of length, and leaves through the top. It runs out of length first, and leaves through the side. Or it hits a corner exactly.

Here’s the construction. Wherever the line exits, put a corner of the next rectangle at that point, and give the new rectangle whatever was left over — the part of the side the line didn’t consume. Writing (lₙ, bₙ) for the n-th rectangle:

Condition     Line exits through     Next rectangle
lₙ·m < bₙ     the side               (lₙ, bₙ − lₙ·m)
lₙ·m > bₙ     the top                (lₙ − bₙ/m, bₙ)
lₙ·m = bₙ     a corner, exactly      stop

Keep going. The rectangles get smaller, they tile along the line without overlapping, and every one of their entry corners sits on that same original line. Eventually — usually — the line strikes a corner dead-on and the chain stops.

The first surprise

When the chain stops, the last rectangle has exactly the aspect ratio of the one you started with.

That isn’t something I built in. Substitute m = B₁/L₁ into the stopping condition lₙ·m = bₙ and you get lₙ/bₙ = L₁/B₁ in one line. The line hits a corner precisely when the rectangle it’s crossing is similar to the one that set the slope.

This is the part I find most satisfying. Similarity isn’t a bonus feature of the construction. It is the terminating condition, wearing a different hat.

Counting the steps

Rescale to strip the slope out — set P = l and Q = b/m — and the comparison “l·m vs b” becomes just “P vs Q”. Every step then replaces the larger of the two by their difference.

That’s the subtractive Euclidean algorithm. Not something like it. It is it, halted one step early: it stops when the two quantities become equal rather than when one hits zero.

So the count is classical. Form X = L₂·B₁ and Y = B₂·L₁, expand X/Y as a continued fraction [a₀; a₁, …, aₖ], and the number of rectangles after the second is

N = (a₀ + a₁ + ⋯ + aₖ) − 1

That the subtractive algorithm takes the sum of the partial quotients is an elementary observation. The definitive treatment is Yao and Knuth’s 1975 paper, which also proves the much harder average-case result: averaged over all fractions with denominator n, the sum grows like (6/π²)(ln n)². What the geometry adds is a way of seeing it — not as a bookkeeping count, but as the length of one unbroken path.

Try it. L₁ = 80, B₁ = 30, L₂ = 50, B₂ = 70. Then X = 1500, Y = 5600, and 15/56 = [0; 3, 1, 2, 1, 3]. Those sum to 10, so the prediction is nine transitions. Drawing it out gives

(50, 70) → (50, 205/4) → (50, 65/2) → (50, 55/4) → (40/3, 55/4)
         → (40/3, 35/4) → (40/3, 15/4) → (10/3, 15/4) → (10/3, 5/2)
         → (10/3, 5/4)

Nine transitions, ending on a rectangle of ratio 8:3 — which is 80:30, as promised.

There’s a third way to read the same count. Write down which way the line leaves each rectangle: S for the side, T for the top. For the example that’s SSS T SS T SS. Now find 15/56 in the Stern–Brocot tree — the binary tree that contains every positive fraction exactly once — and write down the route from the root: LLL R LL R LL. Same word, letters renamed. The runs are the partial quotients (the last one shortened by one), and the length of the route is always the sum of the partial quotients minus one. So N has a one-line description: it is the depth of X/Y in the Stern–Brocot tree.

Two more things worth noticing. First, only the combination X/Y matters: two setups with completely different slopes but the same X/Y produce chains of identical length. The slope draws the picture; the ratio does the arithmetic. Second, swapping length and breadth in both rectangles leaves N unchanged, since it sends X/Y to Y/X and the digit sum survives — geometrically, just reflecting the whole figure in the line y = x.

The square-removal picture shows you the quotients as counts of tiles. This one shows you the whole step count as a single path length, and termination as a line striking a corner. Two pictures of the same object, each showing something the other hides.

When it never stops

If X/Y is irrational, the continued fraction never terminates and neither does the chain. The rectangles shrink forever and the line never finds a corner. This is the golden rectangle’s endless self-similar subdivision in a different costume, and it’s Euclid Book X in modern dress.

I wanted to watch it happen, so I ran it with X/Y = √2. And the computer disagreed with Euclid.

First, what the computer actually checks. In the rescaled coordinates the line hits a corner exactly when P = Q, so the natural test is: stop as soon as |P − Q| < ε, for some small tolerance ε. Every run below uses that test, starting from P = √2 and Q = 1. (A relative test, or the same test written in the original rectangle coordinates, gives different numbers — so it’s worth saying which one you mean.)

In ordinary double-precision floating point, with ε = 10⁻¹², the chain stopped after 90 steps. That’s impossible. So I raised the precision to two hundred digits and dropped the tolerance altogether, asking only whether P and Q were exactly equal. It “terminated” again, after about two thousand steps. Only by doing the whole thing symbolically in the field ℚ(√2), with no rounding anywhere, did it behave.

And the symbolic run says something sharper than “it doesn’t terminate.” Over twenty thousand steps the line never once hits a corner — but |P − Q| gets down to 10⁻³⁸²⁸. It gets absurdly, unimaginably close. It just never arrives. That gap between arbitrarily close and exactly there is the entire content of incommensurability, and it is precisely the gap a computer cannot see.

The tolerance is a real object

A computer never tests whether the line hits the corner. It can’t. What it tests is whether the line comes within ε.

So the thing the machine computes isn’t the chain at all. It’s a different, perfectly well-defined object: the chain that stops at the first step where |P − Q| < ε. Call its length N(ε), and ask an honest question — how does N(ε) grow as ε shrinks?

When X/Y is badly approximable — when its continued fraction has bounded terms, the golden ratio being the extreme case — the answer is clean. N(ε) grows like log(1/ε): never faster, never slower than a constant multiple of it. When the expansion is periodic you can go further and compute the constant exactly. It’s the average term divided by the logarithmic growth rate of the convergent denominators. For the golden ratio that gives 1/log φ = 2.0781; for √2, 2/log(1+√2) = 2.2692; for √3, 2.2780. In my runs the counts matched these to within a few percent, and usually much closer.

Here is √2 at high precision, keeping the tolerance well inside the working precision:

digits   ε          steps   predicted   ratio
60       10⁻²⁰      104     104.5       0.995
120      10⁻⁴⁰      208     209.0       0.995
240      10⁻⁸⁰      416     418.0       0.995
600      10⁻²⁰⁰     1044    1045.0      0.999
900      10⁻³⁰⁰     1566    1567.5      0.999

Half a percent, as the tolerance shrinks across 280 orders of magnitude.

Get Arsh Jad’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

For a typical ratio the classical theory predicts an extra factor of log log(1/ε) — and “typical” is doing real work there. The statement holds with probability close to one, not for every single number, and the reason it can’t be made sharper is the same reason the extra factor appears at all. It’s the Gauss–Kuzmin distribution, under which the chance of a partial quotient equalling k falls off like 1/k². That tail is heavy enough that the average term is infinite. Every so often a typical number throws up an enormous quotient, and the subtractive process has to grind through every unit of it. My own numerics are consistent with this and nowhere near strong enough to confirm it; the range you’d need is far wider than I could compute.

Two kinds of wrong

Here’s the part I’d actually want someone to take away.

Go back to double precision and vary the tolerance:

ε          steps   predicted   ratio
10⁻⁴       20      20.9        0.96
10⁻⁶       30      31.3        0.96
10⁻⁸       41      41.8        0.98
10⁻¹²      90      62.7        1.44
10⁻¹⁶      124     83.6        1.48

The theory nails it, nails it, nails it — and then falls apart. So there are two different things that can stop the chain early, and from the outside they look identical:

1. Tolerance-limited stopping. A clean mathematical object, predictable to half a percent. This “bug” has a formula.
2. Roundoff-limited stopping. Accumulated error has perturbed the trajectory itself, so you’re no longer computing the chain you think you are. No formula. Just wrong.

My original 90 was the second kind. For a while I had a tidy story about how my floating-point bug was secretly a theorem. It wasn’t. It was a bug sitting just past the edge of where the theorem applies.

One honest caveat about the last two rows: they don’t mean much on their own. Write the same chain slightly differently — in the original rectangle coordinates instead of P and Q, say — and you get 81 and 116 instead of 90 and 124. That isn’t a flaw in the table. It’s what “no formula” means.

And the edge is sharp enough to state as a rule. To get within ε of a corner, the chain has to work through the continued fraction until the convergent denominators reach about 1/ε. But the first few partial quotients of a number are only pinned down by an interval of width about 1/q², where q is the denominator you’ve reached. So to follow the chain that far, you need the starting ratio — and everything computed from it — to about ε². That’s twice as many digits as the tolerance itself. Which gives:

You need working precision at least twice the number of digits of tolerance you’re testing.

It’s a heuristic, not a theorem, but it’s one you can check. Ask for 10⁻¹² in double precision and you’re demanding 24 digits out of 16. I tested it on 22 runs, from double precision up to 400 digits, comparing each against the same chain computed at much higher precision. The rule called the regime correctly on 21 of them. The single miss sits exactly on the boundary: double precision at 10⁻⁸, which the rule allows, comes out one step off (41 instead of 40). Even the “nails it” row in the table above was already starting to wobble.

That’s the useful thing. Not “your numerical failure is secretly mathematics” — sometimes it is and sometimes it’s just failure. The useful thing is a criterion telling you which, and here it’s concrete enough to check before you run anything.

What this is, and isn’t

A way of seeing something, not a new result. Everything above is classical, and the picture has close relatives I didn’t know about when I started drawing it.

The closest is the Stern–Brocot tree, as above: the record of which way the line exits is literally its path. That same path is what Caroline Series used to tie continued fractions to geometry. She read it as the cutting sequence of a geodesic crossing the Farey tessellation of the hyperbolic plane, so the counting result is an instance of her correspondence — though her line lives in hyperbolic space, not on a flat page. Straightening a billiard trajectory by reflecting the table gives a single straight line crossing a chain of attached rectangles, which is mechanically very close to this; there, though, the tiles are congruent copies rather than shrinking remainders. Klein’s picture of the convergents as vertices of a lattice hull is the standard geometric-number-theory version.

I also tried and failed to prove a general formula for N(ε) covering all irrational ratios. It broke: runs of 1s in the continued fraction let the chain satisfy the tolerance test far earlier than my bookkeeping allowed, and the error is unbounded rather than constant. What survives is the order-of-growth statement for badly approximable ratios, with an exact constant for the periodic ones. A neat-looking claim I had about Liouville numbers turned out to be flatly false. Both went in the bin, and the post is better for it.

One loose end for another day. The construction works just as well with boxes in three dimensions, but there it turns into a multidimensional subtractive algorithm, and that family is notorious for failing to converge. The natural generalisation exists, and it may well be broken. That’s a story of its own.

Further reading

The classical picture and its history

• Euclid, Elements, Book VII Props 1–2 (numbers); Book X Props 2–3, which together give the incommensurability criterion.
• D. H. Fowler, The Mathematics of Plato’s Academy: A New Reconstruction, 2nd ed., Oxford, 1999 — the standard account of anthyphairesis.
• J. Shallit, “Origins of the analysis of the Euclidean algorithm,” Historia Mathematica 21 (1994), 401–419 — who really got there first: Reynaud’s 1811 bound, Finck’s 1841 analysis, then Lamé.

Counting the steps

• A. C. Yao and D. E. Knuth, “Analysis of the subtractive algorithm for greatest common divisors,” PNAS 72 (1975), 4720–4722.
• D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., §4.5.3.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, §4.5 — the Stern–Brocot tree.
• G. Lamé, Comptes Rendus 19 (1844), 867–870 — the sharp worst-case bound via Fibonacci numbers, traditionally (if not quite accurately) seen as the start of complexity analysis.
• V. Baladi and B. Vallée, “Euclidean algorithms are Gaussian,” Journal of Number Theory 110 (2005), 331–386 — the modern distributional theory.

Continued fraction statistics

• A. Ya. Khinchin, Continued Fractions — Gauss–Kuzmin, and the sum of partial quotients.
• P. Lévy, Bulletin de la Société Mathématique de France 57 (1929), 178–194 — growth of the convergent denominators.

The geometric relatives

• C. Series, “The modular surface and continued fractions,” J. London Math. Soc. (2) 31 (1985), 69–80. Her “The geometry of Markoff numbers,” Mathematical Intelligencer 7 (1985), is the readable companion.
• O. Karpenkov, Geometry of Continued Fractions, Springer, 2013 — Klein polygons and sails.

Approximate gcd, for the tolerance question

• A. Schönhage, “Quasi-gcd computations,” Journal of Complexity 1 (1985), 118–137.

If you want to vary something

• H. Nakada, Tokyo Journal of Mathematics 4 (1981), 399–426 — the α-continued fraction family, in which a genuine tunable parameter interpolates between algorithm variants. See Nakada–Natsui (2008) and Carminati–Tiozzo (2012) for how the entropy depends on α.

Released under CC BY 4.0.