Euclid’s Algorithm

Recently I’ve started to implement (or reimplement) the most common algorithms a software developer should know . One of the nicest books I found on this topic is Algorithms in C (Robert Sedgewick) . Of course, there is this and this, but lately I am more interested on the “implementation” side of things than on maths and theory .

1. Algorithm Description

Euclid’s Algorithm is an efficient method for calculating the greatest common divisor of two numbers (aka GCD) . The  GCD of two numbers is considered the largest number that divides both of them (without leaving a reminder) .

Euclid’s algorithm is based on the principle that given two numbers a and b, if a is greater than b than the greatest common divisor of a and b is the same with the common divisor of b and (b – a) . If we transform the above property into “code” (actually pseudo-code) the algorithm looks like this:

The above pseudo-code is called the subtraction-variant . We can of course replace the repetitive subtractions with one division . The division-based version looks like this (in pseudo-code):

There is also a recursive version of the algorithm:

2. Algorithm Implementation

2.1 C Language

For this implementation I’ve written 4 functions that do the same thing (calculate the greatest common divisor) but in a slightly different manner:

int gcd1(int num1, int num2); The most naive implementation, using repeated subtractions .
int gcd2(int num1, int num2); A more performance-wise implementation, that instead of using repeated subtractions is using divisions .
int gcd3(int num1, int num2); Using a FOR loop instead of the classical WHILE loop .
int gcd4(int num1, int num2); The recursive version of the algorithm .

And the output when running the whole program is:


If you are interested to read about a more performance-wise way to find the greatest common divisor of two numbers you can read this article on Stein’s Algorithm .

3 thoughts to “Euclid’s Algorithm”

Leave a Reply

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

Are we human, or are we dancer *