Euclidean algorithm (C)

From LiteratePrograms

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two natural numbers (or polynomials, or any other object with the necessary structure), and was one of the first known algorithms to be described formally. It is based on the two identities:

a > b implies: gcd(a, b) = gcd(b, a mod b)

gcd(a, 0) = a

The Euclidean algorithm is straightforward to describe in C using a loop that repeatedly replaces a by b and b by a mod b simultaneously until b becomes zero. This requires a temporary variable:

<<Euclidean algorithm main loop simple>>=
while (b != 0) {
    int m = a % b;
    a = b;
    b = m;
}
return a;

We need only ensure that at the start a > b by swapping the inputs if necessary:

<<Euclidean algorithm simple>>=
int euclidean_gcd(int a, int b) {
    if (b > a) { int t = a; a = b; b = t; }
    Euclidean algorithm main loop simple
}

Another strategy that involves less copy operations is to unroll the loop to two iterations and alternate the roles of a and b each iteration:

<<Euclidean algorithm unrolled>>=
int euclidean_gcd(int a, int b) {
    if (b > a) goto b_larger;
    while (1) {
        a = a % b;
        if (a == 0) return b;
b_larger:
        b = b % a;
        if (b == 0) return a;
    }
}

In the first part, a is always larger, while in the second part b is always larger. The label in the middle allows us to jump into the middle of the loop in the case where b is initially larger. We can try out our implementation with this simple test driver:

<<euclidean_gcd.c>>=
#include <stdio.h>  /* printf */
#include <stdlib.h> /* atoi */
Euclidean algorithm unrolled
int main(int argc, char* argv[]) {
    printf("%d\n", euclidean_gcd(atoi(argv[1]), atoi(argv[2])));
    return 0;
}

Euclidean algorithm (C)

From LiteratePrograms

See also

Views

Navigation