Next: Searching for Libraries, Previous: error and progname, Up: Particular Modules [Contents][Index]

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