17.16 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:

• WORD_T Define this to the unsigned integer type that you need this function for.
• GCD Define this to the name of the function to be created.

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’.