JavaScript – Euclidean Algorithm

One of the things that you often have to learn early on in school after multiplication and division is how to find the GCD (Greatest Common Divisor) of two numbers. It is possible that you know the GCD as the GCF (Greatest Common Factor) or the HCF (Higest Common Factor). Do you know how to calculate this for any two positive integers? Many may simply list all of the positive divisors of both numbers and take the largest shared between the two numbers. On the other hand, at times it isn’t easy to list all of these positive divisors. Therefore you could use Euclid’s Algorithm to find the GCD of two numbers.

What is Euclid’s Algorithm

To use this algorithm, you should do the following:

  1. Find the remainder of dividing the larger number by the smaller one:
    remainder = max % min
  2. If the remainder is equal to 0, you can stop because you have identified the GCD which is the smaller number from the previous step.
  3. Start back at step one, using the smaller number as the larger number and the remainder as the smaller number:
    max = min
    min = remainder

Now let’s try to find the GCD of 462 and 910 using the algorithm outlined above:

  1. Find the remainder of dividing 910 (the larger number) by 462 (the smaller number):
    remainder = 910 % 462 =  448
  2. Since the remainder is not 0, we must now find the remainder of dividing 462 (the new larger number) by 448 (the new smaller number):
    remainder = 462 % 448 = 14
  3. Since the remainder is not 0 we must now find the remainder of dividing 448 (the new larger number) by 14 (the new smaller number):
    remainder = 448 % 14 = 0
  4. We know that 14 is the GCD because that was the last smaller number used that gave a remainder of 0.
Now that we can see how easy that is and how efficient it is, it is now time to implement it as a function on a computer.  Since JavaScript is my favorite language and it is the most widely available action language, I decided to define it in JavaScript:
function gcd(a, b) {
  return b ? gcd(b, a % b) : a;
}

The cool thing about this function definition is the fact that it is actually defined recursively. Although I didn’t have to define it that way, I felt it was the perfect opportunity to show how to think recursively. The following live example proves that this works for all integers:
GCD Implemenetation

That example shows the power of recursion, JavaScript, and old school mathematics! 8)

Leave a Reply

Your email address will not be published. Required fields are marked *