Algorithm #3: Greatest Common Divisor

I am going to cover a very simple algorithm this time. It is the GCD(Greatest Common Divisor) algorithm. The GCD of two numbers a and b is the greatest number c such that a%c==0 and b%c==0.

The naive algorithm to find the GCD of two numbers is something like this:

int GCD(int a, int b)
{
   int i=MIN(a,b);
   while(i>=1)
   {
      if(a%i==0 && b%i==0)
         break;
      i--;
   }
   return i;
}

Here we start from MIN(a,b) and find the highest number that is a factor of both a and b; and return it. Simple algorithm but not too efficient.

A better algorithm for finding the GCD of two numbers is the Euclidean algorithm. The implementation is as follows:

int GCD(int a,int b)
 {
    if(a%b==0)
       return b;
    return GCD(b,a%b);
 }

This is a recursive algorithm. The function takes two numbers a and b. If b is a factor of a, then obviously the GCD of a and b is b. But if it is not, then the GCD of a and b is the GCD of b and a%b.

In other words, we take two numbers a and b and divide them. At each step, the remainder of the previous division becomes the divisor and the divisor of the previous division becomes the divident. We repeat this until the remainder becomes zero. The divisor when the remainder becomes zero is the GCD of a and b.

I’m sure most of you have done the Euclidean algorithm when you were in school. Maybe the image on this page will help refresh your memory:

http://f-of-x.blogspot.in/2010/04/euclids-algorithm-for-finding-gcf.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s