Experiment № 093 · The story
Square What's Left
Why I picked it
Ninety-two experiments in, I realised I had skipped the oldest one in the book. Euclid's procedure for the greatest common divisor sits in Book VII of the Elements, around 300 BC, and it is still running today inside every fraction simplifier, every music-notation program working out a tuplet, and every RSA key ever generated. Knuth calls it the granddaddy of algorithms because it is the oldest non-trivial one still in daily use. I'd always known it as a two-line loop with a mod in it. I had never actually seen it, and it turns out it has a picture.
What I enjoy about it
The picture is a rectangle. Cut off the biggest square that fits, as many times as it fits, and you're left with a thinner rectangle sideways. Do the same to that. The squares keep shrinking until one finally fits exactly, and its side is the answer: the largest tile that could have covered the original rectangle with nothing left over. When the animation finishes, the pink grid shows exactly that. I also love that the two counters disagree so wildly. Try "Lopsided": the picture is a row of 499 squares and then two tiny ones, which is 501 subtractions but only two divisions. That difference between subtracting and dividing is the whole reason the algorithm is fast. Then switch to "Every pair" and run it on 160,000 pairs at once. Lines of every slope light up wherever the numbers share a factor, and the slowest pairs crowd along two lines at the golden ratio.
Something you might take away
The worst case is the Fibonacci numbers, and that's a lovely fact: the slowest pair is the one whose quotient is 1 at every step, a rectangle that cuts off a single square each time and stays as close to golden as it can. Gabriel Lamé proved in 1844 that this is the worst it ever gets, so the number of steps grows only with the number of digits, never with the size of the numbers. That's why it's worth knowing. A computer can find the gcd of two 600-digit numbers in a few thousand steps, and the extended version, the one that also gives you the s and t in the readout, is how RSA finds its private key. Running it backwards is also how you reduce a fraction, find the gears that best approximate a ratio, or see why a calendar needs leap years. A 2,300-year-old trick about rectangles is still holding up a lot of the modern world.