Euclid’s Algorithm

Coding challenges are much fun. Here’s an example of a relatively easy one: find the greatest common divisor of two numbers.

What’s the best way to go about doing this?

It depends, of course, on your metric. If you’re looking for elegance over speed, than Euclid’s Algorithm is an excellent way to solve the problem. This algorithm will be familiar to anyone who has taken a computer science course on algorithms (the algorithm demonstrates recursion very clearly). However, I have discovered that my ability to describe the algorithm in words is Not Great. So, I’ve made some visual aid happen! But first, a gist of the algorithm.

Basically, Euclid’s algorithm follows this pattern:

1) Find the remainder of two numbers. Let R be this value. If R is zero, you’re done, and the GCD is the smaller number. Otherwise, go on.

2) Return to step 1 with the smaller of the two numbers and R.

If this makes good sense based purely on the above description, well done/come-replace-me. Otherwise, here is a link to my graphic.

Once you input numbers, you should see many boxes appear. Each box is a unit, and each row is a number (if your screen is big enough. I recommend keeping the numbers you throw in under 75). Once the remainder is found, it will divide the smaller number. Note that as a Mathematician of the Highest Caliber, I have chosen to use rainbow colors.

Let me know if you have any questions!

For other resources:

Donald Knuth’s The Art of Programming Vol I kicks off with a discussion of Euclid’s Algorithm in the context of defining algorithms.

Abstract Algebra textbooks will cover this algorithm too, but I’m somewhat unsure of their accessibility.