Greatest Common Divisor

Let a and b be integers, not both zero. The largest integer d such that d exactly divides both a and b is called the greatest common divisor of a and b . The GCD of the two integers a and b is denoted as gcd(a, b)

The Process

This implementation would follow the Euclid’s Algorithm. The gcd function for two integers is as shown below:

gcd (a, 0) = a
gcd (a, b) = gcd (b, a\mbox{ mod }b)

First we divide a with b and get the remainder r . If r is 0 then b is the GCD as it exactly divides a and obviously itself, else r might be the GCD in which case r should divide b exactly. To test for this in the next iteration the new value of a is the old value of b from the old iteration, and the new value of b is the value of r from the previous iteration. Thus the process continues while r is not 0. When r is zero that is b exactly divides a and thus b has the GCD of the initial two integers. The process to find the GCD of two integers is as below:

INTEGER a, b, r;
WHILE TRUE , run loop forever
   r = a%b
   IF 'r' = '0'
     THEN
       BREAK from loop
   ENDIF
   a = b
   b = r
ENDWHILE
Now b is the GCD of the two initial integers.

This process is used to determine the GCD of n integers. Let there be n integers  a_0, a_1, a_2, a_3, a_4, \ldots , a_n . Taking g_0 = 0 , if the GCD g_1 = gcd (g_0, a_0) , then the GCD of a_0, a_1 will be g_2 = gcd (g_1, a_1) , and the GCD of a_0, a_1, a_2 is g_3 = gcd (g_2, a_2) , thus for n integers the GCD would be g_n = gcd ( \ldots gcd(gcd(gcd(gcd(g_0, a_0), a_1), a_2), a_3), \ldots , a_{n-1})) .
This is implemented by taking one variable used to hold the intermediate GCD values and another the input numbers. The intermediate GCD value is set to 0, and the next input number and the current intermediate GCD result is processed and the next GCD is found. This is performed iteratively and at ith iteration.
We find the GCD of the first i integers by g_i = gcd (g_{i-1}, a_{i-1}) and initially g_0 = 0 .

Sourcecode

#include <stdio.h>

#define TRUE 1

int gcd (int a, int b);

int
main (void)
{
 int g = 0, a, i = 0;
 printf ("\nFinding GCD of n integers");
 printf ("\nEnter numbers serially (\"0\" to end)\n");

 while (TRUE)
 {
   printf ("Enter Number [%d] :", i++);
   scanf ("%d", &a);
   /* 0 to end */
   if (a == 0)
     break;
   /* a is used to hold the temporary value of
 *     * gcd at ith iteration
 *         */
   g = gcd (g, a);
 }
 printf ("\nGCD is %d\n", g);

 return 0;
}

int
gcd (int a, int b)
{
 int rem;

 if (b == 0)
  return a;

 while (TRUE)
 {
   rem = a % b;
   if (rem == 0)
     break;
   a = b;
   b = rem;
 }
 return b;
}

g is initialized to 0 which would be used to hold intermediate GCD results. The integers are input inside the loop and the GCD of the currently input integer a with the old value of g is found and the value of g is updated with this result which reflects the GCD of the all input integers till now. When 0 is input the loop is terminated. The function GCD is coded following the exact structure of the algorithm.

Output

Run 1:       input = 35, 95, 215, 65

Finding GCD of n integers
 Enter       numbers      serially    ("0"  to  end )
 Enter       Number     [1]   :35
 Enter       Number     [2]   :95
 Enter       Number     [3]   :215
 Enter       Number     [4]   :65
 Enter       Number     [5]   :0
 GCD is       5

Run 2:       input = 221, 39, 4199, 247, 91

Finding GCD of n integers
 Enter numbers serially ("0"  to  end )
 Enter       Number     [1]   :221
 Enter       Number     [2]   :39
 Enter       Number     [3]   :4199
 Enter       Number     [4]   :247
 Enter       Number     [5]   :91
 Enter       Number     [6]   :0
 GCD is       13

Resources

Check more about GCD/HCF/GCF in wikipedia: http://en.wikipedia.org/wiki/Greatest_common_divisor

Update

27.03.2011 : Code slightly changed. gcd () function now safe from division by 0
07.05.2011 : Code updated, slight modification in iterative function.

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