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

### 12.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:

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