Tag Archives: computer science

The Euclidean Algorithm

I remember being in school and learning about fractions. In particular, I remember the problems we had when trying to add and subtract fractions. This problem also presented itself when we tried to multiply fractions, although we still received partial credit if we couldn’t reduce fractions to their lowest terms.

What I’m referring to is the problem of finding the Greatest Common Divisor (GCD) of two numbers. The GCD of two numbers is the largest number that divides into both numbers with a remainder of zero each time. This problem has many applications, but for most of us we can relate to it because of our frustrations with fractions.

The algorithm that I’m writing about and have written a script for is called the Euclidean Algorithm, which solves precisely this problem. To be more precise, the Euclidean Algorithm finds the greatest common divisor between two integer numbers.

There are different versions of the algorithm, but the one I have implemented finds the GCD by subtracting the smaller number from the larger number, and if the result is greater than 0, the procedure repeats itself with the two lower numbers. Otherwise, the result (the GCD) is the final number that was greater than 0.

Lets see an example:
Consider the number 9 and 21.
21 – 9 = 12. 12 is greater than 0, so we repeat the procedure with 9 and 12.
12 – 9 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 9.
9 – 3 = 6. 6 is greater than 0, so we repeat the procedure with 3 and 6.
6 – 3 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 3.
3 – 3 = 0. 0 is not greater than 0, so can exit the loop portion of the algorithm.
Since 3 was the last positive number that we arrived at in this procedure, we see that the GCD of 9 and 12 is 3.

To learn more and see more examples, check out My Script on The Euclidean Algorithm.

Examples Page

Sometimes, the most effective way to understand a new concept is to actually see it in action. On My Examples Page, I have implemented a variety of scripts to help teach many different concepts.This is the page that is the easiest for me to update, so you will regularly see changes to this page along with an accompanying blog entry at My Blog Page.

This page is focused on teaching individual concepts and/or algorithms. In particular, with the HTML5 Canvas element, I’ve been able to visualize many of these concepts. Generally I try to provide a script that executes the given algorithm (or concept) and allows for users to view these concepts on random instances. When possible, I provide a button labeled “New Problem” (or something similar) which will allow the user to view a different instance of the algorithm.