Lesson goal: A better Greatest Common Divisor (GCD)

Previous: Reducing fractions with the GCD | Home | Next: Least common multiple (LCM)

The past lesson on GCDs was able to produce GCDs using a very inefficient algorithm. Looping through all possible numbers simply cannot be the best way to proceed. It worked, but is not the best way to compute a GCD. This often comes up in computer programming: you find an algorithm that works, but it is slow or long (in lines of code). How do you make it better?

So enter the idea of "properly" implementing computer algorithms. If you go to the GCD page on Wikipedia, you'll find the algorithm outlined by the gcd(a,b) function shown below. Look how short it is! No loops at all!

Interestingly, the function itself is recursive. Can you see why? It's because the gcd(a,b) function is called within the gcd(a,b) function. That is, this version of gcd(a,b) calls itself. Is this legal? Yes, it is, and often recursion is a very elegant way of solving problems. But you have to always be extra sure that you have some "terminal condition," or some condition that will always eventually be true, that will end the process of the function eternally calling itself. Here it's the if b==0 then condition.

Now you try. Try running this GCD function for a few values.

Type your code here:

See your results here:

The GCD has some interesting properties. Can you verify these using the GCD algorithm here? The print statement verifies the first one in the list below.
  • Is $m\cdot gcd(a,b)=gcd(m\cdot a,m\cdot b)$?

  • Is $gcd(a + m\cdot b, b) = gcd(a, b)$?

  • Is $gcd(a,b)=gcd(b,a)?$

  • If you want the GCD of more than two numbers you can use $gcd(a, b, c) = gcd(gcd(a, b), c)$. Define a function called gcd3(a,b,c) that uses this fact to compute the GCD of 3 numbers.
Show a friend, family member, or teacher what you've done!

Here is a share link to your code:

Does your code work? Want to run it on your iPhone?

Here's your code:

  1. Use [Control]-[C] (Windows) or [⌘]-[C] (MacOS) to copy your code.

  2. Paste it using [Control]-[V] (Windows) or [⌘]-[V] (MacOS) into this page

  3. Then click the "Use on iPhone" button that you'll see.