[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue May 16 01:52:07 UTC 2017
details: /var/hg/gmp/rev/0830446ebe5c
changeset: 17386:0830446ebe5c
user: Niels Möller <nisse at lysator.liu.se>
date: Tue May 16 03:51:16 2017 +0200
description:
Merge code from gmp-bdiv repo, with minor bug fixes.
details: /var/hg/gmp/rev/c81fb86317c7
changeset: 17387:c81fb86317c7
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue May 16 03:52:04 2017 +0200
description:
Trivial merge.
diffstat:
ChangeLog | 27 ++++++++++++++-
mini-gmp/tests/t-signed.c | 22 ++++++------
mpn/generic/binvert.c | 4 +-
mpn/generic/dcpi1_bdiv_q.c | 16 ++++----
mpn/generic/dcpi1_bdiv_qr.c | 18 +++++-----
mpn/generic/divexact.c | 5 ++-
mpn/generic/divis.c | 22 +++++-------
mpn/generic/mu_bdiv_q.c | 16 +++++++-
mpn/generic/mu_bdiv_qr.c | 47 ++++++++++++++++++++++---
mpn/generic/remove.c | 16 +++++++-
mpn/generic/sbpi1_bdiv_q.c | 76 ++++++++++++++++++++----------------------
mpn/generic/sbpi1_bdiv_qr.c | 81 ++++++++++++--------------------------------
mpz/bin_uiui.c | 1 +
tests/mpn/t-bdiv.c | 14 ++-----
tests/mpz/t-primorial_ui.c | 26 +++++++-------
15 files changed, 212 insertions(+), 179 deletions(-)
diffs (truncated from 827 to 300 lines):
diff -r 1c5099e4d6a0 -r c81fb86317c7 ChangeLog
--- a/ChangeLog Thu May 04 12:58:27 2017 +0200
+++ b/ChangeLog Tue May 16 03:52:04 2017 +0200
@@ -1,3 +1,28 @@
+2017-05-16 Niels Möller <nisse at lysator.liu.se>
+
+ * mpn/generic/divis.c (mpn_divisible_p): Updated the divisibility
+ test; bdiv now returns R = D rather than R = 0 when D divides a
+ non-zero U.
+
+ * mpn/generic/binvert.c (mpn_binvert): Negate bdiv quotient.
+ * mpn/generic/divexact.c (mpn_divexact): Likewise.
+ * mpn/generic/remove.c (mpn_remove): Likewise.
+ * mpz/bin_uiui.c (mpz_bdiv_bin_uiui): Likewise.
+
+ * tests/mpn/t-bdiv.c (check_one): Updated to new convention,
+ B^{qn} R = U + QD.
+
+ * mpn/generic/sbpi1_bdiv_qr.c (mpn_sbpi1_bdiv_qr): Reimplemented,
+ for new bdiv convention.
+ * mpn/generic/sbpi1_bdiv_q.c (mpn_sbpi1_bdiv_q): Likewise.
+ * mpn/generic/dcpi1_bdiv_q.c (mpn_dcpi1_bdiv_q_n)
+ (mpn_dcpi1_bdiv_q): Adapted to new bdiv convention.
+ * mpn/generic/dcpi1_bdiv_qr.c (mpn_dcpi1_bdiv_qr_n)
+ (mpn_dcpi1_bdiv_qr): Likewise.
+ * mpn/generic/mu_bdiv_qr.c (mpn_mu_bdiv_qr): Adapted to new bdiv
+ convention, using a wrapper calling the old function.
+ * mpn/generic/mu_bdiv_q.c (mpn_mu_bdiv_q): Likewise.
+
2017-05-03 Torbjörn Granlund <tg at gmplib.org>
* mpn/x86_64/coreisbr/cnd_aors_n.asm: New file.
@@ -252,7 +277,7 @@
instead of mpn_divexact_1.
* gen-bases.c (binvert): New function, computing modular inverse and
- low zero count.
+p low zero count.
(header): Print MP_BASES_BIG_BASE_CTZ_10 and
MP_BASES_BIG_BASE_BINVERTED_10.
diff -r 1c5099e4d6a0 -r c81fb86317c7 mini-gmp/tests/t-signed.c
--- a/mini-gmp/tests/t-signed.c Thu May 04 12:58:27 2017 +0200
+++ b/mini-gmp/tests/t-signed.c Tue May 16 03:52:04 2017 +0200
@@ -24,7 +24,7 @@
#include "testutils.h"
/* Always called with sz fitting in a signed long, and si is the
- corresponding value. */
+ corresponding value. */
int
check_si (const mpz_t sz, long si)
{
@@ -56,7 +56,7 @@
}
/* Called with mpz_cmp (sz, oz) == c. If sz fits in a signed long,
- si is the coresponding value, and similarly for oz and oi. */
+ si is the coresponding value, and similarly for oz and oi. */
void
check_si_cmp (const mpz_t sz, const mpz_t oz, long si, long oi, int c)
{
@@ -89,7 +89,7 @@
goto fail;
}
}
- if (mpz_fits_slong_p (oz))
+ if (mpz_fits_slong_p (oz))
{
if (!check_si (oz, oi))
goto fail;
@@ -134,15 +134,15 @@
overflow_count++;
check_si_cmp (sz, oz, si, oi, c);
-
+
/* c * (2^k + 1) */
if (c == -1)
mpz_sub_ui (oz, sz, 1);
else
mpz_add_ui (oz, sz, 1);
if (mpz_fits_slong_p (oz))
- oi = si + c;
- else
+ oi = si + c;
+ else
overflow_count++;
check_si_cmp (oz, sz, oi, si, c);
@@ -153,18 +153,18 @@
else
mpz_sub_ui (oz, oz, 1); /* oz = sz * 2 - 1 */
if (mpz_fits_slong_p (oz))
- oi = (si - c) * 2 + c;
- else
+ oi = (si - c) * 2 + c;
+ else
overflow_count++;
-
+
check_si_cmp (oz, sz, oi, si, c);
};
-
+
mpz_clear (sz);
mpz_clear (oz);
}
-void
+void
try_fits_slong_p (void)
{
mpz_t x;
diff -r 1c5099e4d6a0 -r c81fb86317c7 mpn/generic/binvert.c
--- a/mpn/generic/binvert.c Thu May 04 12:58:27 2017 +0200
+++ b/mpn/generic/binvert.c Tue May 16 03:52:04 2017 +0200
@@ -6,7 +6,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
-Copyright (C) 2004-2007, 2009, 2012 Free Software Foundation, Inc.
+Copyright (C) 2004-2007, 2009, 2012, 2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -83,6 +83,8 @@
else
mpn_dcpi1_bdiv_q (rp, xp, rn, up, rn, -di);
+ mpn_neg (rp, rp, rn);
+
/* Use Newton iterations to get the desired precision. */
for (; rn < n; rn = newrn)
{
diff -r 1c5099e4d6a0 -r c81fb86317c7 mpn/generic/dcpi1_bdiv_q.c
--- a/mpn/generic/dcpi1_bdiv_q.c Thu May 04 12:58:27 2017 +0200
+++ b/mpn/generic/dcpi1_bdiv_q.c Tue May 16 03:52:04 2017 +0200
@@ -7,7 +7,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
-Copyright 2006, 2007, 2009-2011 Free Software Foundation, Inc.
+Copyright 2006, 2007, 2009-2011, 2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -45,7 +45,7 @@
return n;
}
-/* Computes Q = N / D mod B^n, destroys N.
+/* Computes Q = - N / D mod B^n, destroys N.
N = {np,n}
D = {dp,n}
@@ -67,12 +67,12 @@
cy = mpn_dcpi1_bdiv_qr_n (qp, np, dp, lo, dinv, tp);
mpn_mullo_n (tp, qp, dp + hi, lo);
- mpn_sub_n (np + hi, np + hi, tp, lo);
+ mpn_add_n (np + hi, np + hi, tp, lo);
if (lo < hi)
{
- cy += mpn_submul_1 (np + lo, qp, lo, dp[lo]);
- np[n - 1] -= cy;
+ cy += mpn_addmul_1 (np + lo, qp, lo, dp[lo]);
+ np[n - 1] += cy;
}
qp += lo;
np += lo;
@@ -81,7 +81,7 @@
mpn_sbpi1_bdiv_q (qp, np, n, dp, n, dinv);
}
-/* Computes Q = N / D mod B^nn, destroys N.
+/* Computes Q = - N / D mod B^nn, destroys N.
N = {np,nn}
D = {dp,dn}
@@ -129,7 +129,7 @@
mpn_mul (tp, dp + qn, dn - qn, qp, qn);
mpn_incr_u (tp + qn, cy);
- mpn_sub (np + qn, np + qn, nn - qn, tp, dn);
+ mpn_add (np + qn, np + qn, nn - qn, tp, dn);
cy = 0;
}
@@ -139,7 +139,7 @@
qn = nn - qn;
while (qn > dn)
{
- mpn_sub_1 (np + dn, np + dn, qn - dn, cy);
+ mpn_add_1 (np + dn, np + dn, qn - dn, cy);
cy = mpn_dcpi1_bdiv_qr_n (qp, np, dp, dn, dinv, tp);
qp += dn;
np += dn;
diff -r 1c5099e4d6a0 -r c81fb86317c7 mpn/generic/dcpi1_bdiv_qr.c
--- a/mpn/generic/dcpi1_bdiv_qr.c Thu May 04 12:58:27 2017 +0200
+++ b/mpn/generic/dcpi1_bdiv_qr.c Tue May 16 03:52:04 2017 +0200
@@ -7,7 +7,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
-Copyright 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
+Copyright 2006, 2007, 2009, 2010, 2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -42,12 +42,12 @@
Output:
- q = n * d^{-1} mod 2^{qn * GMP_NUMB_BITS},
+ q = -n * d^{-1} mod 2^{qn * GMP_NUMB_BITS},
- r = (n - q * d) * 2^{-qn * GMP_NUMB_BITS}
+ r = (n + q * d) * 2^{-qn * GMP_NUMB_BITS}
Stores q at qp. Stores the n least significant limbs of r at the high half
- of np, and returns the borrow from the subtraction n - q*d.
+ of np, and returns the carry from the addition n + q*d.
d must be odd. dinv is (-d)^-1 mod 2^GMP_NUMB_BITS. */
@@ -76,7 +76,7 @@
mpn_mul (tp, dp + lo, hi, qp, lo);
mpn_incr_u (tp + lo, cy);
- rh = mpn_sub (np + lo, np + lo, n + hi, tp, n);
+ rh = mpn_add (np + lo, np + lo, n + hi, tp, n);
if (BELOW_THRESHOLD (hi, DC_BDIV_QR_THRESHOLD))
cy = mpn_sbpi1_bdiv_qr (qp + lo, np + lo, 2 * hi, dp, hi, dinv);
@@ -86,7 +86,7 @@
mpn_mul (tp, qp + lo, hi, dp + hi, lo);
mpn_incr_u (tp + hi, cy);
- rh += mpn_sub_n (np + n, np + n, tp, n);
+ rh += mpn_add_n (np + n, np + n, tp, n);
return rh;
}
@@ -132,7 +132,7 @@
mpn_mul (tp, dp + qn, dn - qn, qp, qn);
mpn_incr_u (tp + qn, cy);
- rr = mpn_sub (np + qn, np + qn, nn - qn, tp, dn);
+ rr = mpn_add (np + qn, np + qn, nn - qn, tp, dn);
cy = 0;
}
@@ -142,7 +142,7 @@
qn = nn - dn - qn;
do
{
- rr += mpn_sub_1 (np + dn, np + dn, qn, cy);
+ rr += mpn_add_1 (np + dn, np + dn, qn, cy);
cy = mpn_dcpi1_bdiv_qr_n (qp, np, dp, dn, dinv, tp);
qp += dn;
np += dn;
@@ -167,7 +167,7 @@
mpn_mul (tp, dp + qn, dn - qn, qp, qn);
mpn_incr_u (tp + qn, cy);
- rr = mpn_sub (np + qn, np + qn, nn - qn, tp, dn);
+ rr = mpn_add (np + qn, np + qn, nn - qn, tp, dn);
cy = 0;
}
diff -r 1c5099e4d6a0 -r c81fb86317c7 mpn/generic/divexact.c
--- a/mpn/generic/divexact.c Thu May 04 12:58:27 2017 +0200
+++ b/mpn/generic/divexact.c Tue May 16 03:52:04 2017 +0200
@@ -8,7 +8,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
-Copyright 2006, 2007, 2009 Free Software Foundation, Inc.
+Copyright 2006, 2007, 2009, 2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -98,6 +98,9 @@
tp = TMP_ALLOC_LIMBS (mpn_bdiv_q_itch (qn, dn));
mpn_bdiv_q (qp, np, qn, dp, dn, tp);
TMP_FREE;
+
+ /* Since bdiv_q computes -N/D (mod B^{qn}), we must negate now. */
+ mpn_neg (qp, qp, qn);
}
#else
diff -r 1c5099e4d6a0 -r c81fb86317c7 mpn/generic/divis.c
--- a/mpn/generic/divis.c Thu May 04 12:58:27 2017 +0200
+++ b/mpn/generic/divis.c Tue May 16 03:52:04 2017 +0200
@@ -4,7 +4,7 @@
CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
FUTURE GNU MP RELEASES.
More information about the gmp-commit
mailing list