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
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);
long gcd (long a, long b);
gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1 does not
fit into a signed ‘long’.