[Gmp-commit] /var/hg/gmp: 3 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/a37c927980b4
changeset: 18063:a37c927980b4
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Mar 24 22:56:09 2020 +0100
description:
mpz/nextprime.c (mpz_nextprime_small): New fast path for small values, by Troisi-Bodrato

details:   /var/hg/gmp/rev/b1b4fc3b7d4d
changeset: 18064:b1b4fc3b7d4d
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Mar 24 22:56:52 2020 +0100
description:
tests/mpz/t-nextprime.c: Write values when failing, by Troisi

details:   /var/hg/gmp/rev/805304ca965a
changeset: 18065:805304ca965a
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Mar 24 23:13:28 2020 +0100
description:
mpz/nextprime.c: Remove a comment

diffstat:

 mpz/nextprime.c         |  38 ++++++++++++++++++++++++++++++++------
 tests/mpz/t-nextprime.c |   5 ++++-
 2 files changed, 36 insertions(+), 7 deletions(-)

diffs (83 lines):

diff -r 9cabe848100d -r 805304ca965a mpz/nextprime.c
--- a/mpz/nextprime.c	Tue Mar 24 17:50:16 2020 +0100
+++ b/mpz/nextprime.c	Tue Mar 24 23:13:28 2020 +0100
@@ -85,6 +85,9 @@
 };
 
 #define NUMBER_OF_PRIMES 100
+#define LAST_PRIME 557
+/* NP_SMALL_LIMIT = prevprime (LAST_PRIME ^ 2) */
+#define NP_SMALL_LIMIT 310243
 
 static unsigned long
 calculate_sievelimit(mp_bitcnt_t nbits) {
@@ -120,6 +123,31 @@
   return sieve_limit;
 }
 
+static unsigned
+mpz_nextprime_small (unsigned t)
+{
+  ASSERT (t > 0); /* Expect t=1 if the operand was smaller.*/
+  ASSERT (t < NP_SMALL_LIMIT);
+
+  /* Start from next candidate (2 or odd) */
+  t = (t + 1) | (t > 1);
+  for (; ; t += 2)
+    {
+      unsigned prime = 3;
+      for (int i = 0; ; prime += primegap_small[i++])
+	{
+	  unsigned q, r;
+	  q = t / prime;
+	  r = t - q * prime; /* r = t % prime; */
+	  if (q < prime)
+	    return t;
+	  if (r == 0)
+	    break;
+	  ASSERT (i < NUMBER_OF_PRIMES);
+	}
+    }
+}
+
 void
 mpz_nextprime (mpz_ptr p, mpz_srcptr n)
 {
@@ -132,18 +160,16 @@
   unsigned odds_in_composite_sieve;
   TMP_DECL;
 
-  /* First handle tiny numbers */
-  if (mpz_cmp_ui (n, 2) < 0)
+  /* First handle small numbers */
+  if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
     {
-      mpz_set_ui (p, 2);
+      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);
 
-  if (mpz_cmp_ui (p, 7) <= 0)
-    return;
-
   TMP_MARK;
   pn = SIZ(p);
   MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
diff -r 9cabe848100d -r 805304ca965a tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c	Tue Mar 24 17:50:16 2020 +0100
+++ b/tests/mpz/t-nextprime.c	Tue Mar 24 23:13:28 2020 +0100
@@ -151,7 +151,10 @@
       mpz_nextprime (next_p, x);
       refmpz_nextprime (ref_next_p, x);
       if (mpz_cmp (next_p, ref_next_p) != 0)
-	abort ();
+        {
+          gmp_printf ("Ref mismatch %Zd => %Zd vs %Zd\n", x, ref_next_p, next_p);
+	  abort ();
+        }
     }
 
   mpz_clear (bs);