We don’t know for sure when the Euclidean Algorithm was created nor by whom, but it was made famous around 300 BC by the Elements – the magnum opus of Greek mathematician Euclid. Wikipedia describes it as “one of the oldest algorithms in common use” and Knuth affectionately calls it “the granddaddy of all algorithms”.
I’ll start with some background information that might help you to understand how the algorithm works and might amuse you if you like the history behind the things. But, in all honesty, all this preliminary stuff is mostly a pretext for me to learn how to create these “interactive diagrams”. Feel free to skip right to the algorithm itself.
Divisors and Measures
A number b is a divisor of a number a if the remainder of a / b is 0. These are the terms that I learned in school, but Euclid used a different term: measure. It is the same thing, but has a nice, very concrete geometrical connotation.
Suppose we have a long pole we want to measure. Unfortunately, we don’t have a ruler at hand, so we’ll have to measure it using a stick instead. We say that the stick measures the pole if the pole’s length is exactly a whole number of sticks. This is illustrated in the interactive diagram below.
Playing with the diagram above you can see things like:
- 1 can measure any number.
- Any number can measure itself.
- 21 is measured by 1, 3, 7 and 21.
- 29 is measured only by 29 itself and 1 (in other words, it is a prime number).
Common Divisors, Greatest or Otherwise
A GCD is no single divisor, though, it is a common divisor. Again, the concept is simple enough: we say that c is a common divisor of a and b if c is a divisor of both a and b. In Euclid’s terms: if c measures both a and b, than we can say that c is a common measure of them.
To visualize this, we can expand the previous diagram to two dimensions. Imagine we have a room measuring a×b and we want to fill it perfectly1 with square tiles of size c. This is only possible if the length of the side of the square tile is a common divisor of a and b. The interactive diagram below illustrates this:
And now that we described what a common divisor is, the term greatest common divisor describes itself: it is, well, the greatest common divisor. Put another way, the GCD of two numbers is the largest number that divides both of them without a remainder.
If you want, you can use the previous interactive diagram to easily find the GCD of the room width and room length. Start by setting the tile size to be equals to the smaller dimension of the room. Then decrement the tile size until it can perfectly fill the room. The resulting tile size is the GCD.
This works, but decrementing the tile size one by one is slow. Euclid (or whoever created the algorithm in the first place) was smarter than this.
The Algorithm
Perhaps not surprisingly, after 2300 years we don’t have just one single thing we call “Euclidean Algorithm”. Nowadays there are a few versions (or variations) of the algorithm, all based on the same principle but differing in a way or another.
“OK,” you might ask, “I understand that we have many variations today, but what would be the original Euclidean Algorithm?” As we’ll see, the answer to this question is not straightforward.
Subtractive version
If you open the Elements and look for what exactly Euclid said when describing the algorithm, you’ll find something along these lines: repeatedly subtract the smaller number from the larger one, until they become equal. The resulting value is the GCD of the numbers. In code, it looks like this:
⟨Subtractive Euclidean Algorithm⟩ =
function subtractiveEuclideanAlgorithm(a: number, b: number): number {
while (a != b) {
if (a > b) {
a -= b;
}
else {
b -= a;
}
}
return a;
}
You can see this algorithm in action in the interactive diagram below. It works by repeatedly chopping off parts of the rectangle in a way that guarantees that the GCD of the remaining rectangle’s length and width do not change.
Previously I said that we could find the GCD by decrementing the tile size one by one until we get a perfect fill. We can see this version of the Euclidean Algorithm as a more efficient way to shrink the tile.2
If I was required to chose one version of the Euclidean Algorithm to call the original one, I’d chose this one – after all, this is based on the exact words Euclid used. Some people, however, disagree with me – including a certain Donald Knuth.
Modern version
Did you try running the subtractive version of the Euclidean Algorithm using a very small value for one parameter and a very large value for the other one? This is a bad case for it, as the algorithm takes several steps slowly shrinking only one of the rectangle dimensions.
But if you think about it, this sequence of subtractions is really performing a division: we are dividing the larger side by the smaller one and taking only the remainder. We can therefore use the modulo operator instead of successive subtractions to reduce the number of steps it takes to get to the result. It’s essentially the same idea as before; we are just shrinking the rectangle even more rapidly.3
⟨Euclidean Algorithm⟩ =
function euclideanAlgorithm(a: number, b: number): number {
do {
let c = a;
a = b % a;
b = c;
} while (a > 0);
return b;
}
You might now be thinking that Euclid was not that smart. Someone touted as The Father of Geometry should have noticed that he could replace all those subtractions with the remainder of a division, right?
Well, he did notice. This is clear from the discussion that follows the algorithm description in the Elements. The problem is that it is really hard to express this modulo-based version of the algorithm with the mathematics of the third century BC.4 For this reason, Knuth argues that Euclid really meant to use modulo from the start, and what he (Knuth) presents as the original Euclidean algorithm is modulo-based.
Original or not, this is the version more commonly used these days, and therefore I call it the Euclidean Algorithm, without further qualifiers. Here’s a demo of it running step-by-step:
Recursive Version
Finally, for the sake of completeness, here’s a recursive implementation of the modern version – also said to be a common spot in the wild.
⟨Recursive Euclidean Algorithm⟩ =
function recursiveEuclideanAlgorithm(a: number, b: number): number {
if (b == 0)
return a;
else
return recursiveEuclideanAlgorithm(b, a % b);
}
Nutrition Facts
Summary: Given two positive natural numbers, find their greatest common divisor (GCD).
AKA: Euclid’s Algorithm.
Keywords: GCD, greatest common divisor, GCF, greatest common factor HCF, highest common factor, GCM, greatest common measure, HCD, highest common divisor.
Source code: euclidean_algorithm.ts (the code generated from the snippets on this page); dump_euclidean_algorithm.ts (the messy code for the interactive diagrams above); dump.ts (helper utilities).
References
- Euclid, Elements of Geometry. Translated and edited by Richard Fitzpatrick, 2007. (Book 7; Definitions, Propositions 1 and 2.)
- Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. (Section 4.5.2.)
- Robert Sedgewick, Algorithms in C++, Third Edition. Addison-Wesley, 1998. (Page 205.)
- Mladen Victor Wickerhauser, Mathematics for Multimedia. Birkhäuser, 2009. (Page 4.)
- Wikipedia, Euclidean Algorithm.
-
By “filling perfectly” I mean filling the whole room without having to cut any tile. ↩︎
-
Though, as it becomes evident when playing with the diagram, here we are not simply shrinking a square tile. In fact, the algorithm stops when the tile becomes a square. ↩︎
-
Saying that this version of the algorithm is “just shrinking the rectangle even more rapidly” may give a wrong idea of how it behaves while running. You can see this by yourself in the next interactive diagram. Anyway, I still argue that conceptually we are “just shrinking the rectangle even more rapidly”. ↩︎
-
How could he couldn’t say “repeat until the remainder is zero” if the very concept of zero wasn’t mainstream yet? Heck, even 1 was not considered a proper number, but something special called a “unity”. ↩︎