mpz_prevprime

[Seth Troisi]

Thanks for the quick review and probing comments.

On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> 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.".
>
Replaced

>
> 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))?
>
Yes. changed now.

>
> +  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 findnext_small
consider p) and added some comments

>
> -void
> -mpz_nextprime (mpz_ptr p, mpz_srcptr n)
> +int
> +findnext (mpz_ptr p,
>
> If the function is not public any more, use static.
>
Done.

>
> -  mpz_setbit (p, 0);
>
> This line can still be here, maybe converted to
> * PTR (p) |= 1;
>
This has been moved to the outer functions.
Maybe I should add a test that p is odd?
Something like ASSERT (PTR(p) & 1 == 0);


> +  /* 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.
>
Changed back to nbits > 3  and added an ASSERT (SIZ(p) > 0);

>
> +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?
>
This has been reworked but should never have been included.

>
> 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?
>
Yes, I was counting by two but I reverted that at some point.

>
>
>   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},
>
I did this (using hex form) I threw in some 16*n-1 also

>
>
> +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?
>

I modified the tests so that it makes it more clean that it's testing that
it verifies the retval matches
the return of mpz_prob_prime.


> Ok, I'm sleepy now. I hope I did not write wrong things. Good night!
>
Given the number of times you are pointing our real issues, I wouldn't be
worried about writing one or two wrong comments :)

>
> Ĝis,
> m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prevprime2.patch
Type: text/x-patch
Size: 16570 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/061fe3f0/attachment-0001.bin>