doc/gcd.texi

   1 @node gcd
   2 @section gcd
   3 @findex gcd
   4
   5 The @code{gcd} function returns the greatest common divisor of two numbers
   6 @code{a > 0} and @code{b > 0}.  It is the caller's responsibility to ensure
   7 that the arguments are non-zero.
   8
   9 If you need a gcd function for an integer type larger than
  10 @samp{unsigned long}, you can include the @file{gcd.c} implementation file
  11 with parametrization.  The parameters are:
  12
  13 @itemize @bullet
  14 @item WORD_T
  15 Define this to the unsigned integer type that you need this function for.
  16
  17 @item GCD
  18 Define this to the name of the function to be created.
  19 @end itemize
  20
  21 The created function has the prototype
  22 @smallexample
  23 WORD_T GCD (WORD_T a, WORD_T b);
  24 @end smallexample
  25
  26 If you need the least common multiple of two numbers, it can be computed
  27 like this: @code{lcm(a,b) = (a / gcd(a,b)) * b} or
  28 @code{lcm(a,b) = a * (b / gcd(a,b))}.
  29 Avoid the formula @code{lcm(a,b) = (a * b) / gcd(a,b)} because - although
  30 mathematically correct - it can yield a wrong result, due to integer overflow.
  31
  32 In some applications it is useful to have a function taking the gcd of two
  33 signed numbers. In this case, the gcd function result is usually normalized
  34 to be non-negative (so that two gcd results can be compared in magnitude
  35 or compared against 1, etc.). Note that in this case the prototype of the
  36 function has to be
  37 @smallexample
  38 unsigned long gcd (long a, long b);
  39 @end smallexample
  40 and not
  41 @smallexample
  42 long gcd (long a, long b);
  43 @end smallexample
  44 because @code{gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1} does not
  45 fit into a signed @samp{long}.