[Gmp-commit] /var/hg/gmp: 11 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Nov 16 18:55:06 UTC 2020
details: /var/hg/gmp/rev/dbb1ec0ffee7
changeset: 18152:dbb1ec0ffee7
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:24:55 2020 +0100
description:
mini-gmp/mini-gmp.c (mpz_gcd): Better way to support large limbs.
details: /var/hg/gmp/rev/72a5e731f6df
changeset: 18153:72a5e731f6df
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:25:31 2020 +0100
description:
mpn/generic/mu_divappr_q.c: Better way to write a loop.
details: /var/hg/gmp/rev/5cedff35f7bb
changeset: 18154:5cedff35f7bb
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:26:54 2020 +0100
description:
tests/mpf/t-get_d_2exp.c: Remove unused parameter.
details: /var/hg/gmp/rev/66d9b8969b7c
changeset: 18155:66d9b8969b7c
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:33:31 2020 +0100
description:
tests/mpz/t-pprime_p.c (check_small): Check return value
details: /var/hg/gmp/rev/818a54895f28
changeset: 18156:818a54895f28
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:34:07 2020 +0100
description:
mpz/nextprime.c (mpz_prevprime): New function.
details: /var/hg/gmp/rev/c9e204fc93a2
changeset: 18157:c9e204fc93a2
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:35:19 2020 +0100
description:
gmp-h.in: Declare mpz_prevprime
details: /var/hg/gmp/rev/8d157f648333
changeset: 18158:8d157f648333
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:36:07 2020 +0100
description:
doc/gmp.texi: Document mpz_prevprime
details: /var/hg/gmp/rev/5846d735dc4b
changeset: 18159:5846d735dc4b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:39:21 2020 +0100
description:
tests/mpz/t-nextprime.c: Test also mpz_prevprime()
details: /var/hg/gmp/rev/778b7c0dc0ba
changeset: 18160:778b7c0dc0ba
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:39:45 2020 +0100
description:
tune: Add support for the function mpz_prevprime() to tune/speed
details: /var/hg/gmp/rev/b6681dbe0af4
changeset: 18161:b6681dbe0af4
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:40:03 2020 +0100
description:
ChangeLog
details: /var/hg/gmp/rev/970b7221873f
changeset: 18162:970b7221873f
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 16 19:48:04 2020 +0100
description:
tests/mpz/t-pprime_p.c (check_fermat_mersenne): Changes similar to Troisi's
diffstat:
ChangeLog | 13 ++
doc/gmp.texi | 15 ++-
gmp-h.in | 3 +
mini-gmp/mini-gmp.c | 10 +-
mpn/generic/mu_divappr_q.c | 2 +-
mpz/nextprime.c | 87 +++++++++++---
tests/mpf/t-get_d_2exp.c | 2 +-
tests/mpz/t-nextprime.c | 260 ++++++++++++++++++++++++++++++++++++--------
tests/mpz/t-pprime_p.c | 7 +-
tune/common.c | 12 ++
tune/speed.c | 2 +
tune/speed.h | 2 +
12 files changed, 332 insertions(+), 83 deletions(-)
diffs (truncated from 673 to 300 lines):
diff -r 7f9a2376d6a6 -r 970b7221873f ChangeLog
--- a/ChangeLog Sun Nov 15 15:39:24 2020 +0100
+++ b/ChangeLog Mon Nov 16 19:48:04 2020 +0100
@@ -1,3 +1,16 @@
+2020-11-16 Seth Troisi <sethtroisi at google.com>
+
+ * mpz/nextprime.c (mpz_prevprime): New function.
+ * gmp-h.in: Declare it.
+ * doc/gmp.texi: Document it.
+ * tests/mpz/t-nextprime.c: Test it.
+
+ * tests/mpz/t-pprime_p.c (check_small): Check return value.
+
+ * tune/common.c (speed_mpz_prevprime{,_1}): New functions.
+ * tune/speed.h: Declare them.
+ * tune/speed.c (routine): Add mpz_nextprime{,_1}.
+
2020-11-15 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpn/generic/mu_divappr_q.c: Remove unused exit condition;
diff -r 7f9a2376d6a6 -r 970b7221873f doc/gmp.texi
--- a/doc/gmp.texi Sun Nov 15 15:39:24 2020 +0100
+++ b/doc/gmp.texi Mon Nov 16 19:48:04 2020 +0100
@@ -3563,8 +3563,19 @@
@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op})
@cindex Next prime function
Set @var{rop} to the next prime greater than @var{op}.
-
-This function uses a probabilistic algorithm to identify primes. For
+ at end deftypefun
+
+ at deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})
+ at cindex Previous prime function
+Set @var{rop} to the greatest prime less than @var{op}.
+
+If a previous prime doesn't exist (i.e. @var{op} < 3), rop is unchanged and
+0 is returned.
+
+Return 1 if @var{rop} is a probably prime, and 2 if @var{rop} is definitely
+prime.
+
+These functions use a probabilistic algorithm to identify primes. For
practical purposes it's adequate, the chance of a composite passing will be
extremely small.
@end deftypefun
diff -r 7f9a2376d6a6 -r 970b7221873f gmp-h.in
--- a/gmp-h.in Sun Nov 15 15:39:24 2020 +0100
+++ b/gmp-h.in Mon Nov 16 19:48:04 2020 +0100
@@ -947,6 +947,9 @@
#define mpz_nextprime __gmpz_nextprime
__GMP_DECLSPEC void mpz_nextprime (mpz_ptr, mpz_srcptr);
+#define mpz_prevprime __gmpz_prevprime
+__GMP_DECLSPEC int mpz_prevprime (mpz_ptr, mpz_srcptr);
+
#define mpz_out_raw __gmpz_out_raw
#ifdef _GMP_H_HAVE_FILE
__GMP_DECLSPEC size_t mpz_out_raw (FILE *, mpz_srcptr);
diff -r 7f9a2376d6a6 -r 970b7221873f mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Sun Nov 15 15:39:24 2020 +0100
+++ b/mini-gmp/mini-gmp.c Mon Nov 16 19:48:04 2020 +0100
@@ -2777,13 +2777,13 @@
if (tv->_mp_size == 1)
{
- mp_limb_t gl;
- mpz_t tg;
+ mp_limb_t *gp;
mpz_tdiv_r (tu, tu, tv);
- gl = mpn_gcd_11 (tu->_mp_d[0], tv->_mp_d[0]);
-
- mpz_set (g, mpz_roinit_n (tg, &gl, 1));
+ gp = MPZ_REALLOC (g, 1); /* gp = mpz_limbs_modify (g, 1); */
+ *gp = mpn_gcd_11 (tu->_mp_d[0], tv->_mp_d[0]);
+
+ g->_mp_size = *gp != 0; /* mpz_limbs_finish (g, 1); */
break;
}
mpz_sub (tu, tu, tv);
diff -r 7f9a2376d6a6 -r 970b7221873f mpn/generic/mu_divappr_q.c
--- a/mpn/generic/mu_divappr_q.c Sun Nov 15 15:39:24 2020 +0100
+++ b/mpn/generic/mu_divappr_q.c Mon Nov 16 19:48:04 2020 +0100
@@ -191,7 +191,7 @@
if (UNLIKELY (qn == 0))
return qh; /* Degenerate use. Should we allow this? */
- while (1) /* The exit condition (qn == 0) is verified in the loop. */
+ for (;;) /* The exit condition (qn == 0) is verified in the loop. */
{
if (qn < in)
{
diff -r 7f9a2376d6a6 -r 970b7221873f mpz/nextprime.c
--- a/mpz/nextprime.c Sun Nov 15 15:39:24 2020 +0100
+++ b/mpz/nextprime.c Mon Nov 16 19:48:04 2020 +0100
@@ -124,14 +124,20 @@
}
static unsigned
-mpz_nextprime_small (unsigned t)
+findnext_small (unsigned t, short diff)
{
- ASSERT (t > 0); /* Expect t=1 if the operand was smaller.*/
+ /* For diff= 2, expect t = 1 if operand was negative.
+ * For diff=-2, expect t >= 3
+ */
+ ASSERT (t >= 3 || (diff > 0 && t >= 1));
ASSERT (t < NP_SMALL_LIMIT);
/* Start from next candidate (2 or odd) */
- t = (t + 1) | (t > 1);
- for (; ; t += 2)
+ t = diff > 0 ?
+ (t + 1) | (t != 1) :
+ ((t - 2) | 1) + (t == 3);
+
+ for (; ; t += diff)
{
unsigned prime = 3;
for (int i = 0; ; prime += primegap_small[i++])
@@ -148,8 +154,10 @@
}
}
-void
-mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+static int
+findnext (mpz_ptr p,
+ unsigned long(*negative_mod_ui)(const mpz_t, unsigned long),
+ void(*increment_ui)(mpz_t, const mpz_t, unsigned long))
{
char *composite;
const unsigned char *primegap;
@@ -160,19 +168,14 @@
unsigned odds_in_composite_sieve;
TMP_DECL;
- /* First handle small numbers */
- if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
- {
- ASSERT (NP_SMALL_LIMIT < UINT_MAX);
- mpz_set_ui (p, mpz_nextprime_small (SIZ (n) > 0 ? mpz_get_ui (n) : 1));
- return;
- }
- mpz_add_ui (p, n, 1);
- mpz_setbit (p, 0);
-
TMP_MARK;
pn = SIZ(p);
MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
+ /* Smaller numbers handled earlier */
+ ASSERT (nbits >= 3);
+ /* p odd */
+ ASSERT ((PTR(p)[0] & 1) == 1);
+
if (nbits / 2 <= NUMBER_OF_PRIMES)
{
primegap = primegap_small;
@@ -229,12 +232,14 @@
{
unsigned long difference;
unsigned long incr, prime;
+ int primetest;
memset (composite, 0, odds_in_composite_sieve);
prime = 3;
for (i = 0; i < prime_limit; i++)
{
- m = mpz_cdiv_ui(p, prime);
+ /* Distance to next multiple of prime */
+ m = negative_mod_ui(p, prime);
/* Only care about odd multiplies of prime. */
if (m & 1)
m += prime;
@@ -252,20 +257,60 @@
if (composite[incr])
continue;
- mpz_add_ui (p, p, difference);
+ increment_ui(p, p, difference);
difference = 0;
/* Miller-Rabin test */
- if (mpz_millerrabin (p, 25))
+ primetest = mpz_millerrabin (p, 25);
+ if (primetest)
{
TMP_FREE;
- return;
+ return primetest;
}
}
/* Sieve next segment, very rare */
- mpz_add_ui (p, p, difference);
+ increment_ui(p, p, difference);
+ }
+}
+
+void
+mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+{
+ /* Handle negative and small numbers */
+ if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
+ {
+ ASSERT (NP_SMALL_LIMIT < UINT_MAX);
+ mpz_set_ui (p, findnext_small (SIZ (n) > 0 ? mpz_get_ui (n) : 1, +2));
+ return;
}
+
+ /* First odd greater than n */
+ mpz_add_ui (p, n, 1);
+ mpz_setbit (p, 0);
+
+ findnext(p, mpz_cdiv_ui, mpz_add_ui);
+}
+
+int
+mpz_prevprime (mpz_ptr p, mpz_srcptr n)
+{
+ /* Handle negative and small numbers */
+ if (mpz_cmp_ui (n, 2) <= 0)
+ return 0;
+
+ if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
+ {
+ ASSERT (NP_SMALL_LIMIT < UINT_MAX);
+ mpz_set_ui (p, findnext_small (mpz_get_ui (n), -2));
+ return 2;
+ }
+
+ /* First odd less than n */
+ mpz_sub_ui (p, n, 2);
+ mpz_setbit (p, 0);
+
+ return findnext(p, mpz_fdiv_ui, mpz_sub_ui);
}
#undef LOOP_ON_SIEVE_END
diff -r 7f9a2376d6a6 -r 970b7221873f tests/mpf/t-get_d_2exp.c
--- a/tests/mpf/t-get_d_2exp.c Sun Nov 15 15:39:24 2020 +0100
+++ b/tests/mpf/t-get_d_2exp.c Mon Nov 16 19:48:04 2020 +0100
@@ -42,7 +42,7 @@
got = mpf_get_d_2exp (&got_exp, f);
if (got != 0 || got_exp != 0)
{
- printf ("mpf_get_d_2exp wrong on zero\n", exp);
+ printf ("mpf_get_d_2exp wrong on zero\n");
mpf_trace (" f ", f);
d_trace (" got ", got);
printf (" got exp %ld\n", got_exp);
diff -r 7f9a2376d6a6 -r 970b7221873f tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c Sun Nov 15 15:39:24 2020 +0100
+++ b/tests/mpz/t-nextprime.c Mon Nov 16 19:48:04 2020 +0100
@@ -33,10 +33,20 @@
}
void
+refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
+{
+ if (mpz_cmp_ui(t, 2) <= 0)
+ return;
+
+ mpz_sub_ui (p, t, 1L);
+ while (! mpz_probab_prime_p (p, 10))
+ mpz_sub_ui (p, p, 1L);
+}
+
+void
test_largegap (mpz_t low, const int gap)
{
mpz_t t, nxt;
-
mpz_init (t);
mpz_init (nxt);
@@ -45,7 +55,14 @@
if (mpz_cmp_ui(t, gap) != 0)
{
- gmp_printf ("prime gap %Zd != %d\n", t, gap);
+ gmp_printf ("nextprime gap %Zd => %Zd != %d\n", low, nxt, gap);
+ abort ();
+ }
+
+ mpz_prevprime(t, nxt);
+ if (mpz_cmp(t, low) != 0)
+ {
+ gmp_printf ("prevprime gap %Zd => %Zd != %d\n", nxt, t, gap);
abort ();
}
@@ -56,34 +73,73 @@
void
test_largegaps ()
{
- mpz_t x;
+ mpz_t n;
+
+ mpz_init (n);
More information about the gmp-commit
mailing list