2 @section gcd: greatest common divisor
5 @c Copyright (C) 2006, 2009-2015 Free Software Foundation, Inc.
7 @c Permission is granted to copy, distribute and/or modify this document
8 @c under the terms of the GNU Free Documentation License, Version 1.3 or
9 @c any later version published by the Free Software Foundation; with no
10 @c Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
11 @c Texts. A copy of the license is included in the ``GNU Free
12 @c Documentation License'' file as part of this distribution.
14 The @code{gcd} function returns the greatest common divisor of two numbers
15 @code{a > 0} and @code{b > 0}. It is the caller's responsibility to ensure
16 that the arguments are non-zero.
18 If you need a gcd function for an integer type larger than
19 @samp{unsigned long}, you can include the @file{gcd.c} implementation file
20 with parametrization. The parameters are:
24 Define this to the unsigned integer type that you need this function for.
27 Define this to the name of the function to be created.
30 The created function has the prototype
32 WORD_T GCD (WORD_T a, WORD_T b);
35 If you need the least common multiple of two numbers, it can be computed
36 like this: @code{lcm(a,b) = (a / gcd(a,b)) * b} or
37 @code{lcm(a,b) = a * (b / gcd(a,b))}.
38 Avoid the formula @code{lcm(a,b) = (a * b) / gcd(a,b)} because---although
39 mathematically correct---it can yield a wrong result, due to integer overflow.
41 In some applications it is useful to have a function taking the gcd of two
42 signed numbers. In this case, the gcd function result is usually normalized
43 to be non-negative (so that two gcd results can be compared in magnitude
44 or compared against 1, etc.). Note that in this case the prototype of the
47 unsigned long gcd (long a, long b);
51 long gcd (long a, long b);
53 because @code{gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1} does not
54 fit into a signed @samp{long}.