Python program to calculate the greatest common divisor using the Euclidean Algorithm

The Euclidean Algorithm to calculate the greatest common divisor (GCD) has many applications. We use it in programming class for two reasons: to practice loops and recursion, and to promote algorithmic thinking.

In this post, I’ll give you a description of the algorithm, as well as a few different implementations for you to practice loops and recursion.

Definitions

The greatest common divisor of a and b is the largest integer that divides both a and b. Also, gcd(0, 0) = 0.

Notice that the gcd(a,b) = gcd(|a|,|b|). So, we will assume that a and b are non-negative numbers.

Also notice that gcd(a,0) = a.

Euclidean Algorithm to calculate the greatest common divisor

The Euclidean algorithm is based on successive divisions as follows:

a = q1b + r1

b = q2r1 + r2

r1 = q3r2 + r3

…

r_n-1 = q_n+1r_n + 0

gcd(a,b) = r_n

So, the algorithm will find at each step, numbers q and r such that r_i-1 = q_i+1 r_n + r_n+1. When r_n+1=0, the algorithm will stop and the gcd is r_n.

How to find those numbers?

It happens, that we don’t need to know the numbers q_i, to calculate the numbers r_i. If you understand the division operation, you will notice that:

The first step, r₁ is the remainder of the division of a/b.
The second step, r₂ is the remainder of the division of b/r₁.
And so on.

So, translating the algorithm to pseudocode that we can later translate into a programming language, we get the following:

function gcd(a,b){
   if b==0 return a // see definitions section
else 
 return gcd(b, a % b) // remember the % operator in programming is the remainder of the division.

You can read more about the Euclidean algorithm here and here.

Python program to calculate the Greatest Common Divisor (GCD)

Let’s first examine the recursive implementation.

def gcd(a, b):
    if b == 0:
        return a
    else: 
        #a = q1b + r1
        #b = q1r1 + r2
        return gcd(b, a%b)

Notice from the algorithm that at each step, we will update the value of a with b, and the value of b with the remainder of the division a/b.

Even though recursive solutions to problems are elegant, we should avoid them as much as we can. The reason behind this is that recursion uses a lot of memory and we don’t want our program to crash because there is not enough memory to execute it.

In this case, the iterative solution is easy.

def iterative_gcd(a, b):
    while(b>0):
       a, b = b, a % b
    return a

In python, one can exchange the values of two variables in one line of code, as in the example above. This is not like that in some programming languages.

An earlier version of the Euclidean Algorithm was based on successive subtractions, instead of divisions.

I don’t recommend you use this version of the algorithm because it is inefficient. But I’m going to use it here as an example, so you understand the impact of using an inefficient algorithm to solve a problem.

def other_gcd(a, b):
    while(a!=b):
        if a>b:
            a = a - b
        else:
            b = b - a
    return a

In this case, I won’t even show you the recursive version because when you use numbers a and b where a – b is a big number, the program might crash.

As usual, I created a console program for you to test the functions implemented above.

if __name__=='__main__':
    a = 1160718174
    b = 316258250

    print (gcd(a,b))
    print (iterative_gcd(a,b))

    print (other_gcd(a,b))

The result for the example above is 1078. But feel free to modify the value of a and b.

For you to see the difference in the efficiency of each algorithm, let me show a way that you can print how long it takes, in seconds, to execute a function in python.

from time import time
if __name__=='__main__':
    a = 1160718174
    b = 11

    s1 = time()
    gcd(a,b)
    s2 = time()
    print (s2-s1)
    s1 = time()
    iterative_gcd(a,b)
    s2 = time()
    print (s2-s1)
    s1 = time()
    other_gcd(a,b)
    s2 = time()
    print (s2-s1)

The function time returns the current time. So, if we take the time before calling the function and the time after calling the function, we can know how long it took the execution.

If you execute the example above, you will get the following result.

Example of the execution time of three different algorithms

Look how different is the runtime of the first two versions (using divisions), compared to the last version using subtraction.

H@ppy coding!

Related posts: