Next: , Previous: error and progname, Up: Particular Modules


13.9 gcd: greatest common divisor

The gcd function returns the greatest common divisor of two numbers a > 0 and b > 0. It is the caller's responsibility to ensure that the arguments are non-zero.

If you need a gcd function for an integer type larger than ‘unsigned long’, you can include the gcd.c implementation file with parametrization. The parameters are:

The created function has the prototype

     WORD_T GCD (WORD_T a, WORD_T b);

If you need the least common multiple of two numbers, it can be computed like this: lcm(a,b) = (a / gcd(a,b)) * b or lcm(a,b) = a * (b / gcd(a,b)). Avoid the formula lcm(a,b) = (a * b) / gcd(a,b) because—although mathematically correct—it can yield a wrong result, due to integer overflow.

In some applications it is useful to have a function taking the gcd of two signed numbers. In this case, the gcd function result is usually normalized to be non-negative (so that two gcd results can be compared in magnitude or compared against 1, etc.). Note that in this case the prototype of the function has to be

     unsigned long gcd (long a, long b);

and not

     long gcd (long a, long b);

because gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1 does not fit into a signed ‘long’.