mpz_prevprime

Sat Oct 3 01:58:54 UTC 2020

I modified the patch a tiny bit. Still hoping to get this in for an
upcoming prime-gap search project.

On Sat, Aug 29, 2020 at 1:24 AM Seth Troisi <braintwo at gmail.com> wrote:

> I made a few improvements.
>
> tested with '--enable-assert' and verified no impact to timing with
> `./tune/speed -f 1.02 -s 10-260 mpz_prevprime -p100000000 -P time_prevprime`
> comparing with mpz_nextprime (before and after my change)
>
> On Fri, Mar 27, 2020 at 2:29 AM Seth Troisi <braintwo at gmail.com> wrote:
>
>> 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: prevprime_20201002.patch
Type: text/x-patch
Size: 15736 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20201002/eea3e1b7/attachment-0001.bin>