From 9c10119cfaf80c032f27f3e1cfcf6c97ee79599d Mon Sep 17 00:00:00 2001
From: Bruno Haible <bruno@clisp.org>
Date: Sat, 29 Apr 2006 16:15:46 +0000
Subject: [PATCH] Document the gcd module.

---
 doc/ChangeLog   |  5 +++++
 doc/gcd.texi    | 45 +++++++++++++++++++++++++++++++++++++++++++++
 doc/gnulib.texi |  7 +++++--
 3 files changed, 55 insertions(+), 2 deletions(-)
 create mode 100644 doc/gcd.texi

diff --git a/doc/ChangeLog b/doc/ChangeLog
index 073ab2d79..33bd45a51 100644
--- a/doc/ChangeLog
+++ b/doc/ChangeLog
@@ -1,3 +1,8 @@
+2006-04-29  Bruno Haible  <bruno@clisp.org>
+
+	* gcd.texi: New file.
+	* gnulib.texi: Include it.
+
 2006-04-09  Paul Eggert  <eggert@cs.ucla.edu>
 
 	* gnulib-tool.texi (Modified imports): pathname -> file name.
diff --git a/doc/gcd.texi b/doc/gcd.texi
new file mode 100644
index 000000000..2834f4deb
--- /dev/null
+++ b/doc/gcd.texi
@@ -0,0 +1,45 @@
+@node gcd
+@section gcd
+@findex gcd
+
+The @code{gcd} function returns the greatest common divisor of two numbers
+@code{a > 0} and @code{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
+@samp{unsigned long}, you can include the @file{gcd.c} implementation file
+with parametrization.  The parameters are:
+
+@itemize @bullet
+@item WORD_T
+Define this to the unsigned integer type that you need this function for.
+
+@item GCD
+Define this to the name of the function to be created.
+@end itemize
+
+The created function has the prototype
+@smallexample
+WORD_T GCD (WORD_T a, WORD_T b);
+@end smallexample
+
+If you need the least common multiple of two numbers, it can be computed
+like this: @code{lcm(a,b) = (a / gcd(a,b)) * b} or
+@code{lcm(a,b) = a * (b / gcd(a,b))}.
+Avoid the formula @code{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
+@smallexample
+unsigned long gcd (long a, long b);
+@end smallexample
+and not
+@smallexample
+long gcd (long a, long b);
+@end smallexample
+because @code{gcd(LONG_MIN,LONG_MIN) = -LONG_MIN = LONG_MAX + 1} does not
+fit into a signed @samp{long}.
diff --git a/doc/gnulib.texi b/doc/gnulib.texi
index a3343c28b..775502d6a 100644
--- a/doc/gnulib.texi
+++ b/doc/gnulib.texi
@@ -1,5 +1,5 @@
 \input texinfo   @c -*-texinfo-*-
-@comment $Id: gnulib.texi,v 1.19 2005-09-19 15:48:03 haible Exp $
+@comment $Id: gnulib.texi,v 1.20 2006-04-29 16:15:46 haible Exp $
 @comment %**start of header
 @setfilename gnulib.info
 @settitle GNU Gnulib
@@ -7,7 +7,7 @@
 @syncodeindex pg cp
 @comment %**end of header
 
-@set UPDATED $Date: 2005-09-19 15:48:03 $
+@set UPDATED $Date: 2006-04-29 16:15:46 $
 
 @copying
 This manual is for GNU Gnulib (updated @value{UPDATED}),
@@ -177,6 +177,9 @@ arbitrary order.
 @end itemize
 
 
+@include gcd.texi
+
+
 @include quote.texi
 
 
-- 
2.11.0