[Gmp-commit] /var/hg/gmp-5.0: Describe cofactor canonicalization.

[mercurial at gmplib.org]

details:   /var/hg/gmp-5.0/rev/ad7988649bd9
changeset: 13553:ad7988649bd9
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Wed Feb 08 09:43:10 2012 +0100
description:
Describe cofactor canonicalization.

diffstat:

 ChangeLog    |   4 ++++
 doc/gmp.texi |  19 ++++++++++++++++---
 2 files changed, 20 insertions(+), 3 deletions(-)

diffs (40 lines):

diff -r d3dd234d4b43 -r ad7988649bd9 ChangeLog
--- a/ChangeLog	Wed Feb 08 00:04:07 2012 +0100
+++ b/ChangeLog	Wed Feb 08 09:43:10 2012 +0100
@@ -1,3 +1,7 @@
+2012-02-08  Niels Möller  <nisse at lysator.liu.se>
+
+	* doc/gmp.texi (mpz_gcdext): Describe cofactor canonicalization.
+
 2012-02-07  Niels Möller  <nisse at lysator.liu.se>
 
 	* mpn/generic/gcdext.c (mpn_gcdext): Fixed assert, related to the
diff -r d3dd234d4b43 -r ad7988649bd9 doc/gmp.texi
--- a/doc/gmp.texi	Wed Feb 08 00:04:07 2012 +0100
+++ b/doc/gmp.texi	Wed Feb 08 09:43:10 2012 +0100
@@ -3576,9 +3576,22 @@
 addition set @var{s} and @var{t} to coefficients satisfying
 @math{@var{a}@GMPmultiply{}@var{s} + @var{b}@GMPmultiply{}@var{t} = @var{g}}.
 The value in @var{g} is always positive, even if one or both of @var{a} and
- at var{b} are negative.  The values in @var{s} and @var{t} are chosen such that
- at math{@GMPabs{@var{s}} @le{} @GMPabs{@var{b}}} and @math{@GMPabs{@var{t}}
- at le{} @GMPabs{@var{a}}}.
+ at var{b} are negative (or zero if both inputs are zero).  The values in @var{s}
+and @var{t} are chosen such that normally, @math{@GMPabs{@var{s}} <
+ at GMPabs{@var{b}} / (2 @var{g})} and @math{@GMPabs{@var{t}} < @GMPabs{@var{a}}
+/ (2 @var{g})}, and these relations define @var{s} and @var{t} uniquely. There
+are a few exceptional cases:
+
+If @math{@GMPabs{@var{a}} = @GMPabs{@var{b}}}, then @math{@var{s} = 0},
+ at math{@var{t} = sgn(@var{b})}.
+
+Otherwise, @math{@var{s} = sgn(@var{a})} if @math{@var{b} = 0} or
+ at math{@GMPabs{@var{b}} = 2 @var{g}}, and @math{@var{t} = sgn(@var{b})} if
+ at math{@var{a} = 0} or @math{@GMPabs{@var{a}} = 2 @var{g}}.
+
+In all cases, @math{@var{s} = 0} if and only if @math{@var{g} =
+ at GMPabs{@var{b}}}, i.e., if @var{b} divides @var{a} or @math{@var{a} = @var{b}
+= 0}.
 
 If @var{t} is @code{NULL} then that value is not computed.
 @end deftypefun