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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/e730fab0c7f2
changeset: 18353:e730fab0c7f2
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sat May 14 19:56:17 2022 +0200
description:
mpz/nextprime.c: Revert nth_nextprime stub, and cleanup

details:   /var/hg/gmp/rev/30bbb7763064
changeset: 18354:30bbb7763064
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sat May 14 20:04:41 2022 +0200
description:
mpz/nextprime.c: Smaller operand for sqrt

diffstat:

 mpz/nextprime.c |  21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)

diffs (83 lines):

diff -r e593a00163f3 -r 30bbb7763064 mpz/nextprime.c
--- a/mpz/nextprime.c	Sat May 14 09:13:49 2022 +0200
+++ b/mpz/nextprime.c	Sat May 14 20:04:41 2022 +0200
@@ -70,14 +70,15 @@
    *      vs
    *   Cost of PRP test O(N^2.55)
    */
-  if (nbits < 12800)
+  if (nbits < 12818)
     {
       mpz_t tmp;
       /* sieve_limit ~= nbits ^ (5/2) / 124 */
       mpz_init (tmp);
       mpz_ui_pow_ui (tmp, nbits, 5);
+      mpz_tdiv_q_ui(tmp, tmp, 124*124);
+      /* tmp < 12818^5/(124*124) < 2^55 < 2^64 */
       mpz_sqrt (tmp, tmp);
-      mpz_tdiv_q_ui(tmp, tmp, 124);
 
       sieve_limit = mpz_get_ui(tmp);
       mpz_clear (tmp);
@@ -91,7 +92,7 @@
       sieve_limit = 150000001;
     }
 
-  ASSERT( 1000 < sieve_limit && sieve_limit <= 150000001 );
+  ASSERT (1000 < sieve_limit && sieve_limit <= 150000001);
   return sieve_limit;
 }
 
@@ -129,7 +130,7 @@
 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), unsigned long nth)
+          void(*increment_ui)(mpz_t, const mpz_t, unsigned long))
 {
   char *composite;
   const unsigned char *primegap;
@@ -180,14 +181,14 @@
 
       i = 0;
       last_prime = 3;
-      /* FIXME: we should get rid of sieve_limit and use (i < prime_limit) */
+      /* THINK: should we get rid of sieve_limit and use (i < prime_limit)? */
       for (mp_limb_t j = 4, *sp = sieve; j < sieve_limit; j += GMP_LIMB_BITS * 3)
 	for (mp_limb_t b = j, x = ~ *(sp++); x != 0; b += 3, x >>= 1)
 	  if (x & 1)
 	    {
 	      mp_limb_t prime = b | 1;
-        primegap_tmp[i++] = prime - last_prime;
-        last_prime = prime;
+	      primegap_tmp[i++] = prime - last_prime;
+	      last_prime = prime;
 	    }
 
       /* Both primesieve and prime_limit ignore the first two primes. */
@@ -239,7 +240,7 @@
 
           /* Miller-Rabin test */
           primetest = mpz_millerrabin (p, 25);
-          if (primetest && (--nth == 0))
+          if (primetest)
 	    {
 	      TMP_FREE;
 	      return primetest;
@@ -265,7 +266,7 @@
   /* First odd greater than n */
   mpz_add_ui (p, n, 1);
 
-  findnext(p, mpz_cdiv_ui, mpz_add_ui, 1);
+  findnext(p, mpz_cdiv_ui, mpz_add_ui);
 }
 
 int
@@ -285,6 +286,6 @@
   /* First odd less than n */
   mpz_sub_ui (p, n, 2);
 
-  return findnext(p, mpz_tdiv_ui, mpz_sub_ui, 1);
+  return findnext(p, mpz_tdiv_ui, mpz_sub_ui);
 }