Tuesday, January 5, 2010

Euclid's Algorithm : GCD of 2 integers

The following example solves a classic elementary problem: "Reduce a given fraction to its lowest terms", e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid's algorithm.

C Code
Iterative solution
// Iterative algorithm
int gcd(int a, int b)
{
   int temp;

   while(b)
   {
      temp = a % b;
      a = b;
      b = temp;
   }

   return(a);
}

Recursive solution
// Recursive algorithm
int gcd_recurse(int a, int b)
{
   int temp;
   temp = a % b;

   if (temp == 0)
   {
      return(b);
   }
   else
   {
      return(gcd_recurse(b, temp));
   }
}

Driver program
#include <studio.h>

int gcd(int a, int b);
int gcd_recurse(int a, int b);

int main()
{
  printf("\nGCD(%2d,%2d) = [%d]", 6,4,  gcd(6,4));

 printf("\nGCD(%2d,%2d) = [%d]", 6,4,  gcd_recurse(6,4));

  return(0);
}

Thanks.

0 comments:

Post a Comment