[Gmpcommit] /home/hgfiles/gmp4.3: Update mpn_gcd, mpn_gcd_1, mpn_gcdext doc...
mercurial at gmplib.org
mercurial at gmplib.org
Thu Jan 7 14:11:59 CET 2010
details: /home/hgfiles/gmp4.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
nonzero 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 nonzero.
 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 nonzero. 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
+nonzero 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 nonzero.
+ 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})
More information about the gmpcommit
mailing list