Euclid's GCD Algorithm in ANSI C

In mathematics, Euclid's algorithm is a simple yet efficient method for computing the greatest common divisor of two positive integers.

There are 3 possible implementation for Euclid's algorithm:

1. Division-Based Euclid

/*
 * Description:
 *  Returns the greatest common denominator of a and b using the
 *  Euclid's algorithm division-based.
 * Parameters:
 *  a,b - two positive integers
 * Returns:
 *  the greatest common denominator
 */
int Euclid_Gcd_Division(int a, int b)
{
    int temp;
    while(b!=0)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return abs(a);
}

Here's numeric example on how the algorithm works:

Phase	a	b	temp
Initialization	32	15	Undefined
Step 1	15	2	15
Step 2	2	1	2
Step 3	1	0	1

In Step 3, b becomes equal to 0 and the while loop is exited. The result will be the content of a.

2.Subtraction-based Euclid

/*
 * Description:
 *  Returns the greatest common denominator of a and b using the
 *  Euclid's algorithm subtraction-based.
 * Parameters:
 *  a,b - two positive integers
 * Returns:
 *  the greatest common denominator
 */
int Euclid_Gcd_Subtraction(int a, int b)
{
    a = abs(a);
    b = abs(b);
    if (a != 0)
    {
        while (b != 0)
        {
            if (a > b)
            {
                a = a - b;
            }
            else
            {
                b = b - a;
            }
        }
    }
    return a;
}

Here's a numeric example on how the algorithm works:

Phase	a	b	Observation
Input	-32	15
Initialization	32	15	a>b
Step 1	17	15	a>b
Step 2	2	15	a<b
Step 3	2	13	a<b
Step 4	2	11	a<b
Step 5	2	9	a<b
Step 6	2	7	a<b
Step 7	2	5	a<b
Step 8	2	3	a<b
Step 9	2	1	a>b
Step 10	1	1	a>b
Step 11	1	0	b>=a (else branch)

In Step 11, b becomes equal to 0 and the while loop is exited. The result will be the content of a.

3.Recursion-based Euclid

/*
 * Description:
 *  Returns the greatest common denominator of a and b using the
 *  Euclid's algorithm recursion-based.
 * Parameters:
 *  a,b - two positive integers
 * Returns:
 *  the greatest common denominator
 */
int Euclid_Gcd_Recursion(int a, int b)
{
    int result;
    if (b == 0)
    {
        result = a;
    }
    else
    {
        result = Euclid_Gcd_Recursion(b, a % b);
    }
    return abs(result);
}

The algorithm is the same as the division-based Euclid algorithm. The difference is that this is algorithm is recursive, while the division-based Euclid is iterative.

4.Example

#include<stdio.h>
#include<stdlib.h>

int Euclid_Gcd_Division(int a, int b);
int Euclid_Gcd_Subtraction(int a, int b);
int Euclid_Gcd_Recursion(int a, int b);

int main(void)
{
    int a = 580;
    int b = -320;
    printf("Euclid division based   : %d\n"
           "Euclid subtraction based: %d\n"
           "Euclid recursion based  : %d\n",
            Euclid_Gcd_Division(a,b),
            Euclid_Gcd_Subtraction(a,b),
            Euclid_Gcd_Recursion(a,b));
    return 0;
}