doc/gcd.texi

   1 @node gcd
   2 @section gcd: greatest common divisor
   3 @findex gcd
   4
   5 @c Copyright (C) 2006, 2009-2013 Free Software Foundation, Inc.
   6
   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.
  13
  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.
  17
  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:
  21
  22 @itemize @bullet
  23 @item WORD_T
  24 Define this to the unsigned integer type that you need this function for.
  25
  26 @item GCD
  27 Define this to the name of the function to be created.
  28 @end itemize
  29
  30 The created function has the prototype
  31 @smallexample
  32 WORD_T GCD (WORD_T a, WORD_T b);
  33 @end smallexample
  34
  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.
  40
  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
  45 function has to be
  46 @smallexample
  47 unsigned long gcd (long a, long b);
  48 @end smallexample
  49 and not
  50 @smallexample
  51 long gcd (long a, long b);
  52 @end smallexample
  53 because @code{gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1} does not
  54 fit into a signed @samp{long}.