Euclid’s Algorithm – Implementation in Python

The Euclid Algorithm is an algorithm that is used to find the greatest divisor of two integers. It is often used for teaching purposes as well as in applied problems. There are several kinds of the algorithm: regular, extended, and binary. All types of Euclid’s algorithm can be easily implemented in the Python programming language.

Classic Euclid’s Algorithm

This type of Euclid’s algorithm is the simplest, it was invented over 1300 years ago. With the advent of electronic computers, opportunities for the use of the Euclidian algorithm have expanded, and new, more efficient implementations of it have emerged. The algorithm consists of a certain number of steps, the number of which depends on the size of the input data.

Python implementation

There are several implementations of the classical Euclid algorithm, based on the use of various operators and features of Python (remainder of division, subtraction, recursion). These implementations differ slightly, with strong differences in performance observed only for specific input data.

Implementation with remainder of division

The idea is simple; the algorithm reduces numbers until one equals zero and the other equals the sought divisor. To do this, the while loop is used, in which the greater number is divided by the lesser number and becomes equal to the remainder of the division. Thus, the function will return the greatest common divisor (NOD) of its two arguments. The code of the Euclidean algorithm in Python:

def gcd_rem_division(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 %= num2
        else:
            num2 %= num1
    return num1 or num2

Since one of the numbers always becomes zero, the function will always return the divisor, thanks to the logical operator or, which is used with return. In each new iteration, a larger number becomes a smaller number and vice versa. Let’s take the numbers 168 and 105 and describe the program manually:

• 1 iteration: 168 % 105 = 63 105
• 2 iteration: 63 105 % 63 = 42
• 3 iteration: 63 % 42 = 21 42
• 4 iteration: 42 % 21 = 0 21

After 4 iterations, the algorithm completes its work, because one of the numbers is zero, and the second number is equal to the greatest common divisor, in our case it is 21. Let’s check how the program works:

a = gcd_rem_division(168, 105)
print(a) # Prints 21

Implementation with subtraction

This implementation has the same idea as the previous one, but here we use subtraction to reduce the numbers to zero and the divisor to zero. The code for calculating NOD in Python:

def gcd_subtraction(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
    return num1 or num2

Let’s also describe how the program works with the numbers 168 and 105:

• 1 iteration: 168 – 105 = 63 105
• 2 iteration: 63 105 – 63 = 42
• 3 iteration: 63 – 42 = 21 42
• 4 iteration: 21 42 – 21 = 21
• 5 iteration: 21 – 21 = 0 21

We can see that up to iteration 4, the results of both versions of the algorithm are exactly the same. The differences begin when the 4th iteration results in numbers 21 and 21 instead of 0 and 21, which adds an extra iteration to the algorithm with subtraction, but this does not mean that it works less efficiently. Tocheck how the program works:

a = gcd_subtraction(168, 105)
print(a) # Prints out 21

Implementation with recursion

The idea of the algorithm is similar to the implementation through the remainder of division, but instead of the while loop, recursion is used. This is the code for a Python program that uses recursion to find the NOD:

def gcd_recursion(num1, num2):
    if num1 == 0:
        return num2
    return gcd_recursion(num2 % num1, num1)

The first thing worth noting is that only num1 is checked for zero. It is important to understand that the numbers are constantly swapping places. As the first number in the recursive function call, num2 % num1 is passed in, recall the 4th iteration in the algorithm via the remainder of division:

• 4 iteration: 42 % 21 = 0 – num1 21 – num2

That is, the recursive algorithm will check the number num1 for zero, get True, and return the value of num2, which is the largest common divisor.

Algorithm features: prime numbers

If the two numbers passed in have no common divisors, the algorithm will return 1. Indeed, because every number is divisible by one. For example, the numbers 35 and 18 have no common divisors:

• 35 = 5 * 7 * 1
• 18 = 2 * 9 * 1 = 3 * 6 * 1

The algorithm will return one if both numbers passed in are prime and not equal to each other. Prime numbers are only divisible by themselves and by one. If the algorithm receives one prime number as input, that does not mean that it will necessarily return one:

• 5 and 15: number 5 is prime and 15 is not, the algorithm will return the greatest common divisor of 5.
• 5 and 21: number 5 is prime and 21 is not, the algorithm will return one because 21 is not divisible by 5.
• 3 and 21: number 3 is prime, 21 is not, a 3 will be returned because 21 is divisible by 3.

Extended Euclid’s algorithm

The extended algorithm is called not because it is faster or more complex implementation, but because it allows you to extract additional information from the input data. The extended algorithm also finds the greatest common divisor, and it also determines two coefficients of x and y, such that: ax + by = gcd(a,b), where gcd is a function on finding the NOD. In other words, the algorithm finds the greatest divisor and its linear representation. gcd is an acronym that is often used to refer to a function for finding the NOD:

• g – Greatest;
• c – Common;
• d – Divisor.

Implementation in Python

The program code looks like this:

def gcd_extended(num1, num2):
    if num1 == 0:
        return (num2, 0, 1)
    else:
        div, x, y = gcd_extended(num2 % num1, num1)
    return (div, y - (num2 // num1) * x, x)

Let’s check if the code works:

a = gcd_extended(426, 334)
print(f'The divisor is {a[0]}, x = {a[1]}, y = {a[2]}')

The divisor is 2, x = 69, y = -88

Let’s substitute the obtained coefficients into the formula, then: 69*426-334*88 = 2 Indeed, the coefficients and the divisor are found correctly. But how does the algorithm work? First it checks if the first number is equal to zero, if it is, then the second number is the divisor, and the coefficients are equal to 0 and 1, because “num1 * x + num2 * y = y” in the case where y = 1, and the left product is zero. The function returns three numbers: the divisor, the coefficient of x, and the coefficient of y. Recursion is used for its implementation, the divisor is obtained in the same way as in the classical recursive algorithm, and the coefficients are recursively calculated using the formulas:

• x = y – (num2 // num1) * x
• y = x

Binary Euclid Algorithm

The essence of the binary algorithm is exactly the same – to find the greatest divisor. It differs from the classical algorithm only in the way of implementation.

The complexity of the algorithm is still determined by O(h2) functions, but real-world tests show that the binary algorithm is 60% more efficient than the classical algorithm, this is due to differences in the implementation of conventional arithmetic operations and shifts.

Python implementation

The binary algorithm has a rather complex implementation compared to all the previous ones, but it pays off in terms of efficiency. Python code:

def binary_gcd(num1, num2):
    shift = 0
    # If one of the numbers is zero, the divisor is another number
    if num1 == 0:
        return num2
    if num2 == 0:
        return num1
    # If num1 = 1010 and num2 = 0100, then num1 | num2 = 1110
    # 1110 & 0001 == 0, then there is a shift, which is fixed in shift
    while (num1 | num2) & 1 == 0:
        shift += 1
        num1 >>= 1
        num2 >>= 1
    #If True, then num1 is even, otherwise it is odd
    while num1 & 1 == 0:
        # if it is odd, then shift one bit
        num1 >>= 1
    while num2 != 0:
        # if the number is odd, then shift one bit
        while num2 & 1 == 0:
            num2 >>= 1
        # if the first number is greater than the second
        if num1 > num2:
            # swap them around
            num1, num2 = num2, num1
        #now the first number is less than the second, subtract
        num2 -= num1
    # return the number after shifting the bits
    return num1 << shift

The result of the execution will not differ from the results obtained by other implementations.

Runtime test

We will use the monotonic function in the time module to run the test. Read more about it and how to time the program’s execution here. We will do the test using the Euclidean binary algorithm function described above and the classical algorithm function described in the beginning. The check code is as follows:

start = time.monotonic()
for i in range(10000):
    binary_gcd(168024, 105023)
result = time.monotonic() - start
print("binary time : {:>.3f}".format(result) + " seconds")
start = time.monotonic()
for i in range(10000):
    gcd_rem_division(168024, 105023)
result = time.monotonic() - start
print("standard time: {:>.3f}".format(result) + " seconds")

The result of the test is as follows:

binary time : 0.219 seconds
standard time: 0.094 seconds

From the results, you can see that the implementation of the classical algorithm in Python is faster than the binary one. So, it is better to use the classical Euclidian algorithm in Python, but if you program in C++ and speed of execution is important, then use the binary algorithm.

Conclusion

Euclid’s algorithm allows you to effectively find common divisors of numbers. Over the many years of its existence, several different kinds have been invented, which may differ in the way they are implemented and their effectiveness. Any kind of Euclid’s algorithm can be implemented in Python without the use of third-party libraries.