[Gmp-commit] /home/hgfiles/gmp-4.3: Update mpn_gcd, mpn_gcd_1, mpn_gcdext doc...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp-4.3/rev/de30972da69d
changeset: 12541:de30972da69d
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Thu Jan 07 14:11:11 2010 +0100
description:
Update mpn_gcd, mpn_gcd_1, mpn_gcdext documentation.

diffstat:

 doc/gmp.texi |  75 ++++++++++++++++++++++++++++++++---------------------------
 1 files changed, 41 insertions(+), 34 deletions(-)

diffs (85 lines):

diff -r 456550117e63 -r de30972da69d doc/gmp.texi
--- a/doc/gmp.texi	Mon Jan 04 01:31:44 2010 +0100
+++ b/doc/gmp.texi	Thu Jan 07 14:11:11 2010 +0100
@@ -5334,40 +5334,47 @@
 negative value if @math{@var{s1} < @var{s2}}.
 @end deftypefun
 
- at deftypefun mp_size_t mpn_gcd (mp_limb_t *@var{rp}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t *@var{s2p}, mp_size_t @var{s2n})
-Set @{@var{rp}, @var{retval}@} to the greatest common divisor of @{@var{s1p},
- at var{s1n}@} and @{@var{s2p}, @var{s2n}@}.  The result can be up to @var{s2n}
-limbs, the return value is the actual number produced.  Both source operands
-are destroyed.
-
-@{@var{s1p}, @var{s1n}@} must have at least as many bits as @{@var{s2p},
- at var{s2n}@}.  @{@var{s2p}, @var{s2n}@} must be odd.  Both operands must have
-non-zero most significant limbs.  No overlap is permitted between @{@var{s1p},
- at var{s1n}@} and @{@var{s2p}, @var{s2n}@}.
- at end deftypefun
-
- at deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t @var{s2limb})
-Return the greatest common divisor of @{@var{s1p}, @var{s1n}@} and
- at var{s2limb}.  Both operands must be non-zero.
- at end deftypefun
-
- at deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, mp_size_t *@var{r2n}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t *@var{s2p}, mp_size_t @var{s2n})
-Calculate the greatest common divisor of @{@var{s1p}, @var{s1n}@} and
-@{@var{s2p}, @var{s2n}@}.  Store the gcd at @{@var{r1p}, @var{retval}@} and
-the first cofactor at @{@var{r2p}, *@var{r2n}@}, with *@var{r2n} negative if
-the cofactor is negative.  @var{r1p} and @var{r2p} should each have room for
- at math{@var{s1n}+1} limbs, but the return value and value stored through
- at var{r2n} indicate the actual number produced.
-
- at math{@{@var{s1p}, @var{s1n}@} @ge{} @{@var{s2p}, @var{s2n}@}} is required,
-and both must be non-zero.  The regions @{@var{s1p}, @math{@var{s1n}+1}@} and
-@{@var{s2p}, @math{@var{s2n}+1}@} are destroyed (i.e.@: the operands plus an
-extra limb past the end of each).
-
-The cofactor @var{r2} will satisfy @m{r_2 s_1 + k s_2 = r_1, @var{r2}*@var{s1}
-+ @var{k}*@var{s2} = @var{r1}}.  The second cofactor @var{k} is not calculated
-but can easily be obtained from @m{(r_1 - r_2 s_1) / s_2, (@var{r1} -
- at var{r2}*@var{s1}) / @var{s2}} (this division will be exact).
+ at deftypefun mp_size_t mpn_gcd (mp_limb_t *@var{rp}, mp_limb_t *@var{xp}, mp_size_t @var{xn}, mp_limb_t *@var{yp}, mp_size_t @var{yn})
+Set @{@var{rp}, @var{retval}@} to the greatest common divisor of @{@var{xp},
+ at var{xn}@} and @{@var{yp}, @var{yn}@}.  The result can be up to @var{yn} limbs,
+the return value is the actual number produced.  Both source operands are
+destroyed.
+
+@{@var{xp}, @var{xn}@} must have at least as many bits as @{@var{yp},
+ at var{yn}@}.  @{@var{yp}, @var{yn}@} must be odd.  Both operands must have
+non-zero most significant limbs.  No overlap is permitted between @{@var{xp},
+ at var{xn}@} and @{@var{yp}, @var{yn}@}.
+ at end deftypefun
+
+ at deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t *@var{xp}, mp_size_t @var{xn}, mp_limb_t @var{ylimb})
+Return the greatest common divisor of @{@var{xp}, @var{xn}@} and @var{ylimb}.
+Both operands must be non-zero.
+ at end deftypefun
+
+ at deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{gp}, mp_limb_t *@var{sp}, mp_size_t *@var{sn}, mp_limb_t *@var{xp}, mp_size_t @var{xn}, mp_limb_t *@var{yp}, mp_size_t @var{yn})
+Let @m{U, at var{U}} be defined by @{@var{xp}, @var{xn}@} and let @m{V, at var{V}} be
+defined by @{@var{yp}, @var{yn}@}.
+
+Compute the greatest common divisor @math{G} of @math{U} and @math{V}.  Compute
+a cofactor @math{S} such that @math{G = US + VT}.  The second cofactor @var{T}
+is not computed but can easily be obtained from @m{(G - US) / V, (@var{G} -
+ at var{U}*@var{S}) / @var{V}} (the division will be exact).  It is required that
+ at math{U @ge V > 0}.
+
+ at math{S} satisfies @math{S = 1} or @math{@GMPabs{S} < V / (2 G)}. @math{S =
+0} if and only if @math{V} divides @math{U} (i.e., @math{G = V}).
+
+Store @math{G} at @var{gp} and let the return value define its limb count.
+Store @math{S} at @var{sp} and let |*@var{sn}| define its limb count.  @math{S}
+can be negative; when this happens *@var{sn} will be negative.  The areas at
+ at var{gp} and @var{sp} should each have room for @math{@var{xn}+1} limbs.
+
+The areas @{@var{xp}, @math{@var{xn}+1}@} and @{@var{yp}, @math{@var{yn}+1}@}
+are destroyed (i.e.@: the input operands plus an extra limb past the end of
+each).
+
+Compatibility note: GMP 4.3.0 and 4.3.1 defined @math{S} less strictly.
+Earlier as well as later GMP releases define @math{S} as described here.
 @end deftypefun
 
 @deftypefun mp_size_t mpn_sqrtrem (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, const mp_limb_t *@var{sp}, mp_size_t @var{n})