doc/gcd.texi

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