[Gmp-commit] /var/hg/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Feb 9 13:14:47 UTC 2020
details: /var/hg/gmp/rev/c2d374e059f2
changeset: 18037:c2d374e059f2
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Feb 09 11:55:39 2020 +0100
description:
tests/mpn/t-mulmod_bnm1.c: Trigger special cases more often.
details: /var/hg/gmp/rev/673dba9f78b2
changeset: 18038:673dba9f78b2
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Feb 09 11:57:53 2020 +0100
description:
mpn/generic/sqrmod_bnm1.c (mpn_bc_sqrmod_bnp1): Shorter mpn_sqr.
details: /var/hg/gmp/rev/37295f6d1447
changeset: 18039:37295f6d1447
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Feb 09 11:58:39 2020 +0100
description:
mpn/generic/mulmod_bnm1.c (mpn_bc_mulmod_bnp1): Shorter mpn_mul_n.
details: /var/hg/gmp/rev/3507f80aee0a
changeset: 18040:3507f80aee0a
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Feb 09 14:14:15 2020 +0100
description:
tests/mpz/t-nextprime.c: Split in sub-tests, with new (disabled) ones, by Seth Troisi.
diffstat:
mpn/generic/mulmod_bnm1.c | 28 +++++++--
mpn/generic/sqrmod_bnm1.c | 18 ++++--
tests/mpn/t-mulmod_bnm1.c | 5 +-
tests/mpz/t-nextprime.c | 125 ++++++++++++++++++++++++++++++++++-----------
4 files changed, 129 insertions(+), 47 deletions(-)
diffs (254 lines):
diff -r b1841e762ccd -r 3507f80aee0a mpn/generic/mulmod_bnm1.c
--- a/mpn/generic/mulmod_bnm1.c Thu Feb 06 17:50:10 2020 +0100
+++ b/mpn/generic/mulmod_bnm1.c Sun Feb 09 14:14:15 2020 +0100
@@ -60,8 +60,8 @@
/* Inputs are {ap,rn+1} and {bp,rn+1}; output is {rp,rn+1}, in
- semi-normalised representation, computation is mod B^rn + 1. Needs
- a scratch area of 2rn + 2 limbs at tp; tp == rp is allowed.
+ normalised representation, computation is mod B^rn + 1. Needs
+ a scratch area of 2rn limbs at tp; tp == rp is allowed.
Output is normalised. */
static void
mpn_bc_mulmod_bnp1 (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t rn,
@@ -71,12 +71,26 @@
ASSERT (0 < rn);
- mpn_mul_n (tp, ap, bp, rn + 1);
- ASSERT (tp[2*rn+1] == 0);
- ASSERT (tp[2*rn] < GMP_NUMB_MAX);
- cy = tp[2*rn] + mpn_sub_n (rp, tp, tp+rn, rn);
+ if (UNLIKELY (ap[rn] | bp [rn]))
+ {
+ if (UNLIKELY (ap[rn] & bp [rn]))
+ {
+ *rp = 1;
+ MPN_FILL (rp + 1, rn, 0);
+ return;
+ }
+ else if (bp[rn] == 0)
+ cy = mpn_neg (rp, bp, rn);
+ else /* ap[rn] == 0 */
+ cy = mpn_neg (rp, ap, rn);
+ }
+ else
+ {
+ mpn_mul_n (tp, ap, bp, rn);
+ cy = mpn_sub_n (rp, tp, tp + rn, rn);
+ }
rp[rn] = 0;
- MPN_INCR_U (rp, rn+1, cy);
+ MPN_INCR_U (rp, rn + 1, cy);
}
diff -r b1841e762ccd -r 3507f80aee0a mpn/generic/sqrmod_bnm1.c
--- a/mpn/generic/sqrmod_bnm1.c Thu Feb 06 17:50:10 2020 +0100
+++ b/mpn/generic/sqrmod_bnm1.c Sun Feb 09 14:14:15 2020 +0100
@@ -59,8 +59,8 @@
/* Input is {ap,rn+1}; output is {rp,rn+1}, in
- semi-normalised representation, computation is mod B^rn + 1. Needs
- a scratch area of 2rn + 2 limbs at tp; tp == rp is allowed.
+ normalised representation, computation is mod B^rn + 1. Needs
+ a scratch area of 2rn limbs at tp; tp == rp is allowed.
Output is normalised. */
static void
mpn_bc_sqrmod_bnp1 (mp_ptr rp, mp_srcptr ap, mp_size_t rn, mp_ptr tp)
@@ -69,12 +69,16 @@
ASSERT (0 < rn);
- mpn_sqr (tp, ap, rn + 1);
- ASSERT (tp[2*rn+1] == 0);
- ASSERT (tp[2*rn] < GMP_NUMB_MAX);
- cy = tp[2*rn] + mpn_sub_n (rp, tp, tp+rn, rn);
+ if (UNLIKELY (ap[rn]))
+ {
+ *rp = 1;
+ MPN_FILL (rp + 1, rn, 0);
+ return;
+ }
+ mpn_sqr (tp, ap, rn);
+ cy = mpn_sub_n (rp, tp, tp + rn, rn);
rp[rn] = 0;
- MPN_INCR_U (rp, rn+1, cy);
+ MPN_INCR_U (rp, rn + 1, cy);
}
diff -r b1841e762ccd -r 3507f80aee0a tests/mpn/t-mulmod_bnm1.c
--- a/tests/mpn/t-mulmod_bnm1.c Thu Feb 06 17:50:10 2020 +0100
+++ b/tests/mpn/t-mulmod_bnm1.c Sun Feb 09 14:14:15 2020 +0100
@@ -148,9 +148,10 @@
MPN_ZERO (ap + an - (n >> 1) , n - an);
MPN_COPY (bp, bp + (n >> 1), bn - (n >> 1));
MPN_ZERO (bp + bn - (n >> 1) , n - bn);
- x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an);
+ x = 0;
+ /* x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an); */
ap[x] += gmp_urandomm_ui (rands, 3) - 1;
- x = (n >> 1) - x % (n >> 1);
+ /* x = (n >> 1) - x % (n >> 1); */
bp[x] += gmp_urandomm_ui (rands, 3) - 1;
/* We don't propagate carry, this means that the desired condition
is not triggered all the times. A few times are enough anyway. */
diff -r b1841e762ccd -r 3507f80aee0a tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c Thu Feb 06 17:50:10 2020 +0100
+++ b/tests/mpz/t-nextprime.c Sun Feb 09 14:14:15 2020 +0100
@@ -33,6 +33,60 @@
}
void
+test_largegap (mpz_t low, const int gap)
+{
+ mpz_t t, nxt;
+
+ mpz_init (t);
+ mpz_init (nxt);
+
+ mpz_nextprime(nxt, low);
+ mpz_sub(t, nxt, low);
+
+ if (mpz_cmp_ui(t, gap) != 0)
+ {
+ gmp_printf ("prime gap %Zd != %d\n", t, gap);
+ abort ();
+ }
+
+ mpz_clear (t);
+ mpz_clear (nxt);
+}
+
+void
+test_largegaps ()
+{
+ mpz_t x;
+
+ mpz_init (x);
+
+ // This takes ~3 seconds on a fast computer.
+ // Gap 33008 from P454 = 55261931 * 1063#/210 - 13116
+ mpz_primorial_ui (x, 1063);
+ mpz_mul_ui (x, x, 55261931);
+ mpz_divexact_ui (x, x, 210);
+ mpz_sub_ui (x, x, 13116);
+
+ test_largegap(x, 33008);
+
+ mpz_clear (x);
+
+
+ /*
+ // This takes ~30 seconds, it test the deep science magic constant in
+ // nextprime.c but takes too long to be always enabled.
+ // Gap 66520 from P816 = 1931 * 1933# / 7230 - 30244
+ mpz_primorial_ui (x, 1933);
+ mpz_mul_ui (x, x, 1931);
+ mpz_divexact_ui (x, x, 7230);
+ mpz_sub_ui (x, x, 30244);
+
+ test_largegap(x, 66520);
+ */
+
+}
+
+void
run (const char *start, int reps, const char *end, short diffs[])
{
mpz_t x, y;
@@ -73,17 +127,51 @@
extern short diff5[];
extern short diff6[];
+void
+test_ref(gmp_randstate_ptr rands, int reps) {
+ int i;
+ mpz_t bs, x, next_p, ref_next_p;
+ unsigned long size_range;
+
+ mpz_init (bs);
+ mpz_init (x);
+ mpz_init (next_p);
+ mpz_init (ref_next_p);
+
+ for (i = 0; i < reps; i++)
+ {
+ mpz_urandomb (bs, rands, 32);
+ size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
+
+ mpz_urandomb (bs, rands, size_range);
+ mpz_rrandomb (x, rands, mpz_get_ui (bs));
+
+/* gmp_printf ("%ld: %Zd\n", mpz_sizeinbase (x, 2), x); */
+
+ mpz_nextprime (next_p, x);
+ refmpz_nextprime (ref_next_p, x);
+ if (mpz_cmp (next_p, ref_next_p) != 0)
+ abort ();
+ }
+
+ mpz_clear (bs);
+ mpz_clear (x);
+ mpz_clear (next_p);
+ mpz_clear (ref_next_p);
+}
+
int
main (int argc, char **argv)
{
- int i;
+ gmp_randstate_ptr rands;
int reps = 20;
- gmp_randstate_ptr rands;
- mpz_t bs, x, nxtp, ref_nxtp;
- unsigned long size_range;
tests_start();
+
rands = RANDS;
+ TESTS_REPS (reps, argv, argc);
+
+ test_ref(rands, reps);
run ("2", 1000, "0x1ef7", diff1);
@@ -101,33 +189,8 @@
run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
"0x10000000000000000000000000000155B", diff6);
- mpz_init (bs);
- mpz_init (x);
- mpz_init (nxtp);
- mpz_init (ref_nxtp);
-
- TESTS_REPS (reps, argv, argc);
-
- for (i = 0; i < reps; i++)
- {
- mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
-
- mpz_urandomb (bs, rands, size_range);
- mpz_rrandomb (x, rands, mpz_get_ui (bs));
-
-/* gmp_printf ("%ld: %Zd\n", mpz_sizeinbase (x, 2), x); */
-
- mpz_nextprime (nxtp, x);
- refmpz_nextprime (ref_nxtp, x);
- if (mpz_cmp (nxtp, ref_nxtp) != 0)
- abort ();
- }
-
- mpz_clear (bs);
- mpz_clear (x);
- mpz_clear (nxtp);
- mpz_clear (ref_nxtp);
+ // Too slow to include in normal testing.
+ //test_largegaps ();
tests_end ();
return 0;
More information about the gmp-commit
mailing list