[Gmp-commit] /var/hg/gmp: 7 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Nov 23 18:31:03 UTC 2020
details: /var/hg/gmp/rev/2e3bcd5976a1
changeset: 18151:2e3bcd5976a1
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:24:39 2020 +0100
description:
tests/mpz/t-pprime_p.c (check_small): Check return value (by Troisi)
details: /var/hg/gmp/rev/dfecd199f1d7
changeset: 18152:dfecd199f1d7
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:25:15 2020 +0100
description:
mpz/nextprime.c (mpz_prevprime): New function. (by Troisi)
details: /var/hg/gmp/rev/8cfedd667eed
changeset: 18153:8cfedd667eed
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:25:48 2020 +0100
description:
gmp-h.in: Declare mpz_prevprime
details: /var/hg/gmp/rev/d41ee63ff981
changeset: 18154:d41ee63ff981
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:29:14 2020 +0100
description:
doc/gmp.texi: Document mpz_prevprime (by Troisi)
details: /var/hg/gmp/rev/5e1c26da2b2c
changeset: 18155:5e1c26da2b2c
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:29:39 2020 +0100
description:
tests/mpz/t-nextprime.c: Test also mpz_prevprime() (by Troisi)
details: /var/hg/gmp/rev/4d8b95fd049f
changeset: 18156:4d8b95fd049f
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:30:11 2020 +0100
description:
tune: Add support for the function mpz_prevprime() to tune/speed (by Troisi)
details: /var/hg/gmp/rev/a2b3babbcc8e
changeset: 18157:a2b3babbcc8e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Nov 23 19:30:19 2020 +0100
description:
ChangeLog
diffstat:
ChangeLog | 13 ++
doc/gmp.texi | 15 ++-
gmp-h.in | 3 +
mpz/nextprime.c | 87 ++++++++++++---
tests/mpz/t-nextprime.c | 260 ++++++++++++++++++++++++++++++++++++++---------
tests/mpz/t-pprime_p.c | 2 +-
tune/common.c | 12 ++
tune/speed.c | 2 +
tune/speed.h | 2 +
9 files changed, 322 insertions(+), 74 deletions(-)
diffs (truncated from 608 to 300 lines):
diff -r 9003dd9f091a -r a2b3babbcc8e ChangeLog
--- a/ChangeLog Thu Nov 19 21:37:20 2020 +0100
+++ b/ChangeLog Mon Nov 23 19:30:19 2020 +0100
@@ -1,3 +1,16 @@
+2020-11-23 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-10 Marco Bodrato <bodrato at mail.dm.unipi.it>
* configure.ac (fat_path): Add bd1, goldmont,silvermont for CPUVEC.
diff -r 9003dd9f091a -r a2b3babbcc8e doc/gmp.texi
--- a/doc/gmp.texi Thu Nov 19 21:37:20 2020 +0100
+++ b/doc/gmp.texi Mon Nov 23 19:30:19 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 9003dd9f091a -r a2b3babbcc8e gmp-h.in
--- a/gmp-h.in Thu Nov 19 21:37:20 2020 +0100
+++ b/gmp-h.in Mon Nov 23 19:30:19 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 9003dd9f091a -r a2b3babbcc8e mpz/nextprime.c
--- a/mpz/nextprime.c Thu Nov 19 21:37:20 2020 +0100
+++ b/mpz/nextprime.c Mon Nov 23 19:30:19 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 9003dd9f091a -r a2b3babbcc8e tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c Thu Nov 19 21:37:20 2020 +0100
+++ b/tests/mpz/t-nextprime.c Mon Nov 23 19:30:19 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);
+
+ // largest gap with start < 2^32.
+ mpz_set_str (n, "3842610773", 10);
+ test_largegap (n, 336);
- mpz_init (x);
+ // largest gap with start < 2^64.
+ mpz_set_str (n, "18361375334787046697", 10);
+ test_largegap (n, 1550);
+
+ // test high merit primegap in the P30 digit range.
+ mpz_set_str (n, "3001549619028223830552751967", 10);
+ test_largegap (n, 2184);
- // 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 high merit primegap in the P100 range.
+ mpz_primorial_ui (n, 257);
+ mpz_divexact_ui (n, n, 5610);
+ mpz_mul_ui (n, n, 4280516017UL);
+ mpz_sub_ui (n, n, 2560);
+ test_largegap (n, 9006);
- test_largegap(x, 33008);
+ // test high merit primegap in the P200 range.
+ mpz_primorial_ui (n, 409);
+ mpz_divexact_ui (n, n, 30);
+ mpz_mul_ui (n, n, 3483347771UL);
+ mpz_sub_ui (n, n, 7016);
+ test_largegap (n, 15900);
+
+ mpz_clear (n);
+}
- mpz_clear (x);
+void
+test_bitboundaries ()
+{
+ mpz_t n;
+ mpz_init (n);
+ mpz_set_str (n, "0xfff1", 0);
More information about the gmp-commit
mailing list