mpz_prevprime

[Seth Troisi]

On Sat, Oct 3, 2020 at 2:40 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-10-03 03:58 Seth Troisi ha scritto:
> >> On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato
> >> Il 2020-03-25 02:25 Seth Troisi ha scritto:
> >> + t = diff > 0 ? ((t + 1) | (t > 1)) :
> >> + ((t == 3) ? 2 : ((t - 2) | 1));
> >>
> >> Maybe move this to the caller side? Or partially, leaving here just
> >> ASSERT (t >= 2);
> >> t |= (t != 2);
> >>
> >> I moved this to the caller side (so that both findnext and
>
> Really? :-) But it's ok anyway.
>
> >> I would also check many gaps around 2^{16n}, to check if everything
> >> works correctly when the search crosses the limb boundaries.
> >> Maybe structuring the test with a table {"number(base16?)", gap},
> >> i.e.
> >> with (also) something like:
> >> {"65521", 16},
> >> {"4294967291", 20},
> >> {"281474976710597", 80},
> >> {"18446744073709551557", 72},
> >> {"1208925819614629174706111", 78},
> >> {"79228162514264337593543950319", 78},
> >> {"5192296858534827628530496329220021", 100},
> >> {"340282366920938463463374607431768211297", 210},
> >>
> >> I did this (using hex form) I threw in some 16*n-1 also
>
> I'd really add some more tests around boundaries... for both next and
> prec.
>
>
run ("2", 1000, "0x1ef7", diff1);
tests crosses ~10 bit boundaries up to 2^12

there's also an test for crossing 2^128 to 2^129 and 2^148 to 2^149

An easy way to add a small number of these would be these might be

diff -r b811f1fd8ac2 tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c   Fri Oct 02 19:02:13 2020 -0700
+++ b/tests/mpz/t-nextprime.c   Sat Oct 03 04:20:44 2020 -0700
@@ -107,6 +107,43 @@
 }

 void
+test_bitboundaries ()
+{
+  mpz_t n;
+  mpz_init (n);
+
+  mpz_set_str (n, "0xfff1");
+  test_largegap (n, 16);
+
+  mpz_set_str (n, "0xfffffffb");
+  test_largegap (n, 20);
+
+  mpz_set_str (n, "0xffffffffffc5");
+  test_largegap (n, 80);
+
+  mpz_set_str (n, "0xffffffffffffffc5");
+  test_largegap (n, 72);
+
+  mpz_set_str (n, "0xffffffffffffffffffbf");
+  test_largegap (n, 78);
+
+  mpz_set_str (n, "0xffffffffffffffffffffffef");
+  test_largegap (n, 78);
+
+  mpz_set_str (n, "0xffffffffffffffffffffffffffb5");
+  test_largegap (n, 100);
+
+  mpz_set_str (n, "0xffffffffffffffffffffffffffffff61");
+  test_largegap (n, 210);
+
+  mpz_set_str (n, "0xffffffffffffffffffffffffffffffffffffffffffffff13");
+  test_largegap (n, 370);
+
+  mpz_clear (n);
+}

@@ -379,6 +416,7 @@
   test_prevprime(rands, reps);

   test_largegaps ();
+  test_bitboundaries ();

   tests_end ();
   return 0;


My biggest area of concern is that something will not work if starting at
prime-1 or prime+1 so increasing the random tests makes me feel better

@@ -203,7 +240,7 @@
   for (i = 0; i < reps; i++)
     {
       mpz_urandomb (bs, rands, 32);
-      size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
+      size_range = mpz_get_ui (bs) % 7 + 2; /* 2..255 bit operands */

       mpz_urandomb (bs, rands, size_range);
       mpz_rrandomb (x, rands, mpz_get_ui (bs));
@@ -368,7 +405,7 @@
 main (int argc, char **argv)
 {
   gmp_randstate_ptr rands;
-  int reps = 20;
+  int reps = 100;

or even

+      size_range = mpz_get_ui (bs) % 5 + 2; /* 2..63 bit operands */
+  int reps = 1000;


Ĝis,
> m
>