[Gmp-commit] /var/hg/gmp: 5 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Feb 10 22:06:49 CET 2012
details: /var/hg/gmp/rev/2aec52074772
changeset: 14614:2aec52074772
user: Niels M?ller <nisse at lysator.liu.se>
date: Fri Feb 10 21:27:50 2012 +0100
description:
mpn_gcdext_hook: Added comment.
details: /var/hg/gmp/rev/a8c10b8006c0
changeset: 14615:a8c10b8006c0
user: Niels M?ller <nisse at lysator.liu.se>
date: Fri Feb 10 21:46:53 2012 +0100
description:
(hgcd_matrix_update_q): Fixed carry handling bug. Related to bugfix in
the gmp-5.0 repo.
details: /var/hg/gmp/rev/96619bf1e251
changeset: 14616:96619bf1e251
user: Niels M?ller <nisse at lysator.liu.se>
date: Fri Feb 10 21:53:44 2012 +0100
description:
Use mpz_rrandomb for test operands, not mpz_urandomb. Change copied
from gmp-5.0 repo.
details: /var/hg/gmp/rev/a5495daa5504
changeset: 14617:a5495daa5504
user: Niels M?ller <nisse at lysator.liu.se>
date: Fri Feb 10 21:58:29 2012 +0100
description:
Enforce sligthly stricter bound for cofactors.
details: /var/hg/gmp/rev/1cebd6e5fe6e
changeset: 14618:1cebd6e5fe6e
user: Niels M?ller <nisse at lysator.liu.se>
date: Fri Feb 10 22:06:19 2012 +0100
description:
Fixed assert, related to the special case A = (2k+1) G, B = 2 G. Fix
copied from gmp-5.0 repo.
diffstat:
ChangeLog | 20 ++++++++++++++++++++
mpn/generic/gcdext.c | 5 ++++-
mpn/generic/gcdext_lehmer.c | 7 +++++++
mpn/generic/hgcd_matrix.c | 14 ++++++++------
tests/mpn/t-hgcd.c | 4 ++--
tests/mpz/t-gcd.c | 8 ++++----
6 files changed, 45 insertions(+), 13 deletions(-)
diffs (138 lines):
diff -r 0e69009eb933 -r 1cebd6e5fe6e ChangeLog
--- a/ChangeLog Fri Feb 10 21:14:03 2012 +0100
+++ b/ChangeLog Fri Feb 10 22:06:19 2012 +0100
@@ -1,3 +1,23 @@
+2012-02-10 Niels Möller <nisse at lysator.liu.se>
+
+ * mpn/generic/gcdext.c (mpn_gcdext): Fixed assert, related to the
+ special case A = (2k+1) G, B = 2 G. Fix copied from gmp-5.0 repo.
+
+2012-02-10 Niels Möller <nisse at lysator.liu.se>
+
+ * tests/mpz/t-gcd.c (gcdext_valid_p): Enforce sligthly stricter
+ bound for cofactors.
+
+ * tests/mpz/t-gcd.c (main): Use mpz_rrandomb for test operands,
+ not mpz_urandomb. Change copied from gmp-5.0 repo.
+ * tests/mpn/t-hgcd.c (main): Likewise.
+
+2012-02-10 Niels Möller <nisse at lysator.liu.se>
+
+ * mpn/generic/hgcd_matrix.c (hgcd_matrix_update_q): Fixed carry
+ handling bug. Fix copied from gmp-5.0 repo, where the function is
+ found in hgcd.c.
+
2012-02-10 Niels Möller <nisse at lysator.liu.se>
* mpn/generic/gcdext_lehmer.c (mpn_gcdext_hook): Corrected
diff -r 0e69009eb933 -r 1cebd6e5fe6e mpn/generic/gcdext.c
--- a/mpn/generic/gcdext.c Fri Feb 10 21:14:03 2012 +0100
+++ b/mpn/generic/gcdext.c Fri Feb 10 22:06:19 2012 +0100
@@ -396,7 +396,10 @@
MPN_COPY (gp, ap, n);
MPN_CMP (c, u0, u1, un);
- ASSERT (c != 0);
+ /* c == 0 can happen only when A = (2k+1) G, B = 2 G. And in
+ this case we choose the cofactor + 1, corresponding to G = A
+ - k B, rather than -1, corresponding to G = - A + (k+1) B. */
+ ASSERT (c != 0 || (un == 1 && u0[0] == 1 && u1[0] == 1));
if (c < 0)
{
MPN_NORMALIZE (u0, un);
diff -r 0e69009eb933 -r 1cebd6e5fe6e mpn/generic/gcdext_lehmer.c
--- a/mpn/generic/gcdext_lehmer.c Fri Feb 10 21:14:03 2012 +0100
+++ b/mpn/generic/gcdext_lehmer.c Fri Feb 10 22:06:19 2012 +0100
@@ -94,6 +94,13 @@
if (u1n == 0)
return;
+ /* Should always have u1n == un here, and u1 >= u0. The
+ reason is that we alternate adding u0 to u1 and u1 to u0
+ (corresponding to subtractions a - b and b - a), and we
+ can get a large quotient only just after a switch, which
+ means that we'll add (a multiple of) the larger u to the
+ smaller. */
+
tp = ctx->tp;
if (qn > u1n)
diff -r 0e69009eb933 -r 1cebd6e5fe6e mpn/generic/hgcd_matrix.c
--- a/mpn/generic/hgcd_matrix.c Fri Feb 10 21:14:03 2012 +0100
+++ b/mpn/generic/hgcd_matrix.c Fri Feb 10 22:06:19 2012 +0100
@@ -95,19 +95,21 @@
ASSERT (n + qn >= M->n);
c[row] = mpn_add (M->p[row][col], tp, n + qn, M->p[row][col], M->n);
}
+
+ n += qn;
+
if (c[0] | c[1])
{
- M->n = n + qn + 1;
- M->p[0][col][n-1] = c[0];
- M->p[1][col][n-1] = c[1];
+ M->p[0][col][n] = c[0];
+ M->p[1][col][n] = c[1];
+ n++;
}
else
{
- n += qn;
n -= (M->p[0][col][n-1] | M->p[1][col][n-1]) == 0;
- if (n > M->n)
- M->n = n;
+ ASSERT (n >= M->n);
}
+ M->n = n;
}
ASSERT (M->n < M->alloc);
diff -r 0e69009eb933 -r 1cebd6e5fe6e tests/mpn/t-hgcd.c
--- a/tests/mpn/t-hgcd.c Fri Feb 10 21:14:03 2012 +0100
+++ b/tests/mpn/t-hgcd.c Fri Feb 10 22:06:19 2012 +0100
@@ -103,9 +103,9 @@
size_range = mpz_get_ui (bs) % 13 + 2;
mpz_urandomb (bs, rands, size_range);
- mpz_urandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE);
+ mpz_rrandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE);
mpz_urandomb (bs, rands, size_range);
- mpz_urandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE);
+ mpz_rrandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE);
if (mpz_cmp (op1, op2) < 0)
mpz_swap (op1, op2);
diff -r 0e69009eb933 -r 1cebd6e5fe6e tests/mpz/t-gcd.c
--- a/tests/mpz/t-gcd.c Fri Feb 10 21:14:03 2012 +0100
+++ b/tests/mpz/t-gcd.c Fri Feb 10 22:06:19 2012 +0100
@@ -154,9 +154,9 @@
size_range = mpz_get_ui (bs) % 17 + 2;
mpz_urandomb (bs, rands, size_range);
- mpz_urandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_BITSIZE);
+ mpz_rrandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_BITSIZE);
mpz_urandomb (bs, rands, size_range);
- mpz_urandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_BITSIZE);
+ mpz_rrandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_BITSIZE);
mpz_urandomb (bs, rands, 8);
bsi = mpz_get_ui (bs);
@@ -370,7 +370,7 @@
if (mpz_cmpabs_ui (s, 1) > 0)
{
mpz_mul_2exp (temp3, s, 1);
- if (mpz_cmpabs (temp3, temp2) > 0)
+ if (mpz_cmpabs (temp3, temp2) >= 0)
return 0;
}
@@ -386,7 +386,7 @@
if (mpz_cmpabs_ui (temp2, 1) > 0)
{
mpz_mul_2exp (temp2, temp2, 1);
- if (mpz_cmpabs (temp2, temp1) > 0)
+ if (mpz_cmpabs (temp2, temp1) >= 0)
return 0;
}
return 1;
More information about the gmp-commit
mailing list