mpz_prevprime

[Marco Bodrato]

Ciao,

Il 2020-03-25 02:25 Seth Troisi ha scritto:
> I'm back with a new mpz_prevprime patch

diff -r 805304ca965a doc/gmp.texi
+ at deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})

+If previous prime doesn't exist (e.g. @var{op} < 3), rop is unchanged 
and
+0 is returned.

I suggest "i.e." instead of "e.g.".

diff -r 805304ca965a mpz/nextprime.c
+findnext_small (unsigned t, short diff)
[...]
+  ASSERT (t > 0 || (diff < 0 && t > 2));

This is equivalent to (t > 0). Do you mean (t > 2 || (diff > 0 && t > 
0))?

+  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);

-void
-mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+int
+findnext (mpz_ptr p,

If the function is not public any more, use static.

-  mpz_setbit (p, 0);

This line can still be here, maybe converted to
* PTR (p) |= 1;

+  /* smaller numbers handled earlier*/
+  ASSERT (nbits >= 15);

Not needed. Maybe ASSERT (nbits > 3), because we don't want to handle 
very small numbers with this code.

+int
+mpz_prevprime (mpz_ptr p, mpz_srcptr n)
+{
+  /* First handle tiny 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 (SIZ (n) > 0 ? mpz_get_ui (n) : 1, 
-2));
+      return 2;
+    }

The line "if (mpz_cmp_ui (n, 2) <= 0)" already handle the case (SIZ (n) 
<= 0), checking if (SIZ (n) > 0) is a nonsense
Anyway... assume that code is used: what happens if findnext_small(1,-2) 
is called?

diff -r 805304ca965a tests/mpz/t-nextprime.c
[...]
+refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
[...]
+  if (mpz_cmp_ui(t, 3) <= 0)

The loop after that branch handles also that case, don't it?


  test_largegaps ()
  {
[...]
+  mpz_set_ui (n, 3842610773);
[...]
+  mpz_set_ui (n, 18361375334787046697UL);

Those lines can fail at compile time... if 3842610773 does not fit in an 
int and 18361375334787046697 not in an unsigned long. E.g. when 
sizeof(int)==4.
Use _set_str.

+  mpz_mul_ui (n, n, 4280516017);
[...]
+  mpz_mul_ui (n, n, 3483347771);

...

> I also added large negative tests for mpz_nextprime

To be honest... I do not like this (undocumented) detail of the current 
behaviour of _nextprime. I personally do not like the idea to enforce it 
with a test...

> and we can enable test_largegaps now that the default gap is smaller

Yes, we should.
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},


+void
+test_prevprime (gmp_randstate_ptr rands, int reps)
[...]
+  /* Test mpz_prevprime(3 <= n < 2^45) returns 2. */
[...]
+  /* Test mpz_prevprime(n > 2^70) returns 1. */
[...]
+        if ( retval != 1 )
[...]

I do not understand. A test-function should fail if a function behaviour 
does not agree with the documented interface, or it can fail for some 
other kind of regression that we want to avoid...
Your test will warn us against possible improvements! What if the future 
primality testing functions will return 2 on some large primes?

Ok, I'm sleepy now. I hope I did not write wrong things. Good night!

Ĝis,
m