[Gmp-commit] /home/hgfiles/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Jan 7 14:12:15 CET 2010
details: /home/hgfiles/gmp/rev/ea6dc9d5a562
changeset: 13347:ea6dc9d5a562
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Jan 07 13:41:43 2010 +0100
description:
Rewrite quotient round-up code.
details: /home/hgfiles/gmp/rev/9eb05ff71195
changeset: 13348:9eb05ff71195
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Jan 07 13:42:28 2010 +0100
description:
Trivial merge.
details: /home/hgfiles/gmp/rev/3a4217027601
changeset: 13349:3a4217027601
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Jan 07 13:43:29 2010 +0100
description:
Fix error message typo.
details: /home/hgfiles/gmp/rev/7475114f90f5
changeset: 13350:7475114f90f5
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Jan 07 14:10:50 2010 +0100
description:
Update mpn_gcd, mpn_gcd_1, mpn_gcdext documentation.
diffstat:
ChangeLog | 2 +
doc/gmp.texi | 59 ++++++++++++++++++++++++---------------------
mpn/generic/mu_divappr_q.c | 17 ++++++++++---
tests/mpn/t-div.c | 2 +-
4 files changed, 47 insertions(+), 33 deletions(-)
diffs (134 lines):
diff -r b9edb959b0b2 -r 7475114f90f5 ChangeLog
--- a/ChangeLog Thu Jan 07 05:16:36 2010 +0100
+++ b/ChangeLog Thu Jan 07 14:10:50 2010 +0100
@@ -2,6 +2,8 @@
* Version 5.0.0 released.
+ * mpn/generic/mu_divappr_q.c: Rewrite quotient round-up code.
+
* mpn/generic/mu_div_qr.c: Handle carry-out from a carry propagation
subtract.
* mpn/generic/mu_divappr_q.c: Likewise.
diff -r b9edb959b0b2 -r 7475114f90f5 doc/gmp.texi
--- a/doc/gmp.texi Thu Jan 07 05:16:36 2010 +0100
+++ b/doc/gmp.texi Thu Jan 07 14:10:50 2010 +0100
@@ -5359,44 +5359,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{gp}, mp_limb_t *@var{sp}, mp_size_t *@var{sn}, mp_limb_t *@var{up}, mp_size_t @var{un}, mp_limb_t *@var{vp}, mp_size_t @var{vn})
-Let @m{U, at var{U}} be defined by @{@var{up}, @var{un}@} and
-let @m{V, at var{V}} be defined by @{@var{vp}, @var{vn}@}.
+ 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 calculated but can easily be obtained from @m{(G - US) / V, (@var{G} -
+is not computed but can easily be obtained from @m{(G - US) / V, (@var{G} -
@var{U}*@var{S}) / @var{V}} (the division will be exact). It is required that
@math{U @ge V > 0}.
-FIXME: Say something about the range of @math{S}.
+ 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. Some
-versions of GMP will make @math{S} negative; when this happens *@var{sn} will
-be negative. The areas at @var{gp} and @var{sp} should each have room for
- at math{@var{un}+1} limbs.
-
-The areas @{@var{up}, @math{@var{un}+1}@} and @{@var{vp}, @math{@var{vn}+1}@}
+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})
diff -r b9edb959b0b2 -r 7475114f90f5 mpn/generic/mu_divappr_q.c
--- a/mpn/generic/mu_divappr_q.c Thu Jan 07 05:16:36 2010 +0100
+++ b/mpn/generic/mu_divappr_q.c Thu Jan 07 14:10:50 2010 +0100
@@ -291,14 +291,23 @@
/* FIXME: We should perhaps be somewhat more elegant in our rounding of the
quotient. For now, just make sure the returned quotient is >= the real
- quotient. */
+ quotient; add 3 with saturating arithmetic. */
qn = nn - dn;
cy += mpn_add_1 (qp, qp, qn, 3);
if (cy != 0)
{
- MPN_ZERO (qp, qn);
- mpn_sub_1 (qp, qp, qn, 1);
- qh = 0;
+ if (qh != 0)
+ {
+ /* Return a quotient of just 1-bits, with qh set. */
+ mp_size_t i;
+ for (i = 0; i < qn; i++)
+ qp[i] = GMP_NUMB_MAX;
+ }
+ else
+ {
+ /* Propagate carry into qh. */
+ qh = 1;
+ }
}
return qh;
diff -r b9edb959b0b2 -r 7475114f90f5 tests/mpn/t-div.c
--- a/tests/mpn/t-div.c Thu Jan 07 05:16:36 2010 +0100
+++ b/tests/mpn/t-div.c Thu Jan 07 14:10:50 2010 +0100
@@ -80,7 +80,7 @@
tvalue = "Q*D";
error:
printf ("\r*******************************************************************************\n");
- printf ("%s and failed test %lu: %s\n", fname, test, msg);
+ printf ("%s failed test %lu: %s\n", fname, test, msg);
printf ("N= "); dumpy (np, nn);
printf ("D= "); dumpy (dp, dn);
printf ("Q= "); dumpy (qp, qn);
More information about the gmp-commit
mailing list