# Euclidean algorithm (C)

### From LiteratePrograms

**Other implementations**:**C**| Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

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){intm = a % b; a = b; b = m;}returna;

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

<<Euclidean algorithm simple>>=inteuclidean_gcd(inta,intb){if(b > a){intt = 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>>=inteuclidean_gcd(inta,intb){if(b > a)gotob_larger;while(1){a = a % b;if(a == 0)returnb; b_larger: b = b % a;if(b == 0)returna;}}

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 unrolledintmain(intargc,char* argv[]){printf("%d\n", euclidean_gcd(atoi(argv[1]), atoi(argv[2])));return0;}

## See also

Download code |