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:

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    IF num1 < num2
      SWAP (num1, num2)
    num1 := num1 - num2
  RETURN num2

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):

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    tmp  := num1
    num1 := num2 MOD num1
    num2 := tmp
  RETURN num2

There is also a recursive version of the algorithm:

FUNCTION GCD(num1, num2)
  IF num1 <> 0 THEN
    RETURN GCD(num2 MOD num1, num1)
  RETURN num2

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 .
#include <stdio.h>
#include <stdlib.h>

/**
* @author Andrei Ciobanu
* @date DEC 11, 2010
*/

int gcd1(int num1, int num2);
int gcd2(int num1, int num2);
int gcd3(int num1, int num2);
int gcd4(int num1, int num2);

/**
* Calculates the greatest common divisor .
* @param num1
* @param num2
* @return The greatest common divisor of num1 and num2
*/
int gcd1(int num1,int num2)
{
  int tmp;
  while(num1 > 0) {
    if (num1 < num2) {
      /* Swap */
      tmp = num1;
      num1 = num2;
      num2 = tmp;
    }
    num1 -= num2;
  }
  return num2;
}

/**
* Calculates the greatest common divisor . (Instead of using multiple
* substractions we use division)
* @param num1
* @param num2
* @return The greatest common divisor of num1 and num2
*/
int gcd2(int num1, int num2)
{
  int tmp;
  while (num1 > 0) {
    tmp = num1;
    num1 = num2 % num1;
    num2 = tmp;
  }
  return num2;
}

/**
* Calculates the greatest common divisor . (The same as gcd2 but instead
* using a FOR loop)
* @param num1
* @param num2
* @return The greatest common divisor of num1 and num2
*/
int gcd3(int num1, int num2)
{
  int tmp;
  for(num1 = abs(num1), num2 = abs(num2); num1 > 0; tmp = num1,
    num1 = num2 % num1, num2 = tmp);
  return num2;
}

/**
* Calculates the greatest common divisor . (Recursive way)
* @param num1
* @param num2
* @return The greatest common divisor of num1 and num2
*/
int gcd4(int num1, int num2)
{
  if (num1) {
    return gcd4(num2 % num1, num1);
  }
  return num2;
}

int main(int argc, char *argv[])
{
  printf("gcd1(%u, %u) = %un", 10, 25, gcd1(10, 25));
  printf("gcd1(%u, %u) = %un", 100, 24, gcd1(100, 24));

  printf("gcd2(%u, %u) = %un", 10, 25, gcd2(10, 25));
  printf("gcd2(%u, %u) = %un", 100, 24, gcd2(100, 24));

  printf("gcd3(%u, %u) = %un", 10, 25, gcd3(10, 25));
  printf("gcd3(%u, %u) = %un", 100, 24, gcd3(100, 24));

  printf("gcd4(%u, %u) = %un", 10, 25, gcd4(10, 25));
  printf("gcd4(%u, %u) = %un", 100, 24, gcd4(100, 24));
  return (0);
}

And the output when running the whole program is:

gcd(10, 25) = 5
gcd(100, 24) = 4
gcd2(10, 25) = 5
gcd2(100, 24) = 4
gcd3(10, 25) = 5
gcd3(100, 24) = 4
gcd4(10, 25) = 5
gcd4(100, 24) = 4

Note:

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 Comments

Leave a Reply

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

Are we human, or are we dancer *