Euclid's Algorithm for Calculating the GCD
Why I'm Interested
It's sometimes tempting to dismiss such simple problems as calculating the greatest common divisor of two positive integers. But I think it can be interesting to consider just how these sorts of things can be done.
If you put me on the spot not too long ago, and asked me to divise a way to calculate the gcd of two positive integers, I'd have perhaps first considered brute forcing it, checking every value in the range 1 through the smaller of the two:
/**
* Calculates the greatest common divisor of arguments
* Returns: the gcd of n and m
* Preconditions: n and m are positive
**/
int gcd(int n, int m ) {
int divisor = n < m ? n : m;
while (0 != n % divisor || 0 != m % divisor) {
divisor--;
}
return divisor;
}
Now, while as unseemly as this was feels, computers are fast enough to make this work for most applications and it was so easy to write up that one might feel you should have a good reason to put more effort into it (such as needing the gcd of many large values).
In fact, you can try it here. Don't be afraid to use large inputs, as you're computer's in all likelyhood fast enough to handle it.
To see the algorithm at work, enter two positive integers you want to test
A Better Way
At this point, I would try to justify putting more effort with this by saying how it's all for fun and I don't need to be efficient with my time, but smart people have already looked at this problem before and we can just see how they've done it.
In fact, none other than Euclid of Alexandria (an ancient Greek mathematician who lived around 300 BC) wrote down a solution. Specifically, his solution is described in proposition 1 and proposition 2 of Book VII of Euclid's Elements.
The basic idea is that if q is how many times n goes into m and r is the remainder (so that m = qn + r), then (assuming r $\neq$ 0) gcd(m,n) = gcd(n,r).
This is simple to see. First denote d=gcd(m,n) and $\delta=gcd(n,r)$. Then, since d is the gcd of m and n, d|m and d|qn, and so d|(m - qn), but m - qn = r, so d|r, hence d is a common divisor of both n and r, and so is less than or equal the greatest common divisor $\delta$ (d $\leq$ $\delta$).
Conversely, $\delta$|n, so $\delta$|nq, and $\delta$|r, so $\delta$|(qn + r), i.e., $\delta|m$. Since d is the greatest common divisor of m and q, $\delta$ $\leq$ d.
But combined, these results imply d = $\delta$, as claimed.
The reason this helps us devise an algorithm is because the remainder is always less than n. So, if after replacing gcd(m,n) with gcd(n,r), we were to treat n as the new m and r as the new n, we'd be able to repeat the process over and over, with n decreasing by at least 1 every step.
It would only break down if the new r value were to ever equal 0, but if r = 0, then m = qn, and hence n is a common divisor of m and n. Moreover, since no divisor of n can be greater than n, it must be that $n$ is the greatest common divisor, and so we've found our gcd.
Now, not only have smart people come up with the idea before, smart people have written it up as a simple algorithm. Here's Donald Knuth's description in the first section of The Art of Computer Programming:
Euclid's algorithm: Given two positive integers m and n, find their greatest common divisor, that is, the largest positive integer that evenly divides both m and n.
E1: [Find Remainder] Divide m by n and let r be the remainder.
E2: [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
E2: [Reduce] Set m $\leftarrow$ n, n $\leftarrow$ r, and go back to step E1.
Written up, this algorithm becomes
/**
* Calculates the greatest common divisor of arguments
* Returns: the gcd of n and m
* Preconditions: n and m are positive
**/
int euclid(m, n) {
int r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
return n;
}
To hopefully aid in understanding the algorithm, enter any two positive integers (there are no artificially imposed size contraints here) and hit calculate. A table will be printed containing the values of n, m, and r after each r assignment. The initial values occupy the first rows, and the final values occupy the last rows.
Knuth points out that this code can actually be improved. First by using multiple return points, needless moves can be avoided. Specifically, once we obtain r by dividing m, m is no longer need, so we can instead place the value of r in m. Since the r value needs to become the new n value, we alternate the rolls of m and n.
Second, if n > m, r will equal m, and the first cycle of the loop will only do the job of swapping n and m. This is a needless division, and instead we can save time by explicity checking for it, treating n as m if it is in fact larger. With these adjustments implemented, we get:
/**
* Calculates the greatest common divisor of arguments
* Returns: the gcd of n and m
* Preconditions: n and m are positive
**/
int improvedEuclid(m, n) {
// The algorithm will still work even if this if statement is removed
if (n > m) {
n = n % m;
if (n == 0) {return m;}
}
while (1) {
m = m % n;
if (m == 0) {return n;}
n = n % m;
if (n == 0) {return m;}
}
}
To see the algorithm at work, enter two positive integers you want to test
Mark checkbox to print steps (print occurs after every assignment)