Euclidean GCD Spiral Screensaver
The Euclidean GCD Spiral screensaver draws the real, 2,300-year-old Euclidean algorithm as nested shrinking squares, finding the greatest common divisor of two random numbers. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Euclidean GCD Spiral screensaver works
The saver picks two real random numbers and draws them as a rectangle, then runs the true Euclidean algorithm on them.
Each step tiles the real larger side with as many copies of the smaller side as fit, exactly the geometric picture behind the algorithm's repeated division.
The leftover remainder becomes the next real side length, and the process repeats, spiraling the nested squares inward.
Once the remainder reaches zero, the last nonzero square is the real greatest common divisor; it holds briefly, then a fresh pair of numbers begins.
Euclid's algorithm, drawn as squares
Euclid described the algorithm for the greatest common divisor in Book VII of the Elements, dated to about 300 BC, and it is often called one of the oldest algorithms in common use. The idea is that the greatest common divisor of two numbers does not change when the larger is replaced by its remainder after division by the smaller. Repeating this shrinks the numbers until the remainder is zero, and the last non-zero value is the answer.
The geometric reading is natural. Take a rectangle with sides a and b. Cut off as many squares of the shorter side as will fit, leaving a smaller rectangle, and repeat. When the leftover is exactly a square, its side is the greatest common divisor, and the rectangle can be tiled by squares of that size. If the numbers share no factor, the division ends at one. The same sequence of quotients forms the continued fraction of the ratio a over b.
The algorithm is also fast: Gabriel Lamé showed in 1844 that the number of division steps never exceeds five times the number of decimal digits of the smaller number, with the worst case produced by consecutive Fibonacci numbers. An extended version also finds integers s and t with sa plus tb equal to the greatest common divisor, which is how modular inverses are computed in cryptography.
A worked example
Two numbers that share a large common factor collapse to their real GCD in just a couple of steps, while a pair of coprime numbers spiral through many more shrinking squares before reaching one.
Settings & tips
- Accent recolours the current nested square.
- This is the real, unmodified ancient Euclidean algorithm.
- A fresh pair of random numbers begins automatically once the GCD is found.
Frequently asked questions
- Is this a real algorithm?
- Yes — the real Euclidean algorithm, one of the oldest algorithms still in common use today.
- What do the nested squares mean?
- Each square is a real, literal geometric picture of one step of repeated division in the algorithm.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Why are Fibonacci numbers the worst case?
- Each step of Euclid's algorithm then removes the smallest possible amount, because every quotient is one. Gabriel Lamé used this in 1844 to bound the number of steps.
- What is the extended Euclidean algorithm?
- It also finds integers x and y such that ax plus by equals the greatest common divisor (Bézout's identity). Cryptography uses it to compute modular inverses.
- How is this related to continued fractions?
- The quotients produced at each division step are the terms of the continued fraction expansion of a divided by b.