mpz_prevprime

[Seth Troisi]

I see this was pushed, with a few more polishing tweaks.
Thanks for the collaboration to improve my rough code into something much
cleaner.

I see you also added more testing in tests/devel/primes.c which is a great
triple check.
It looks like the usage on line 21-28 / 399 wasn't updated.

Now that this is in I have a much smaller patch to add mpz_prevprime()
My patch includes t-nextprime-tune.c and Makefile.am which should not be
committed but I used
for internal testing and might be useful.



On Tue, Mar 17, 2020 at 10:53 PM Seth Troisi <braintwo at gmail.com> wrote:

>
>
> On Tue, Mar 17, 2020 at 3:04 PM Marco Bodrato <bodrato at mail.dm.unipi.it>
> wrote:
>
>> Ciao,
>>
>> Il 2020-03-16 02:23 Seth Troisi ha scritto:
>> > On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato
>> > <bodrato at mail.dm.unipi.it> wrote:
>> >> May I write a few more comments?
>>
>> > Always, my opinion about being ready is just that it's passed
>> > the bar of being good enough not that it's perfect.
>>
>> I'm tempted to simply commit your proposal and then change it :-)
>> But if we keep on discussing here, we can improving the code with the
>> opinions of two persons...
>>
>> >> I see now:
>> >> + if (nbits <= 32)
>> >> + incr_limit = 336;
>>
>> >> Probably, we should change the name of the variable to
>> >> odd_candidates_in_sieve, then you would probably have written:
>> >> if (nbits <= 32)
>> >> odd_numbers_in_sieve = 168;
>>
>> > Renamed to odds_in_composite_sieve
>>
>> Of course the name is not essential, the values are :-)
>> And they seem correct to me, now.
>>
> I only discovered on experimental verification but the +1 is not needed,
> it took me a while to
> understand why but p is incremented to the first odd after the start of
> the gap by so the gap is -2
>
>>
>> >> Then I wonder if the cost of the /* Sieve next segment */ step
>> [...]
>> >> need to allocate the possibly huge next_mult array?
>> >
>> > You're correct, this reduces the memory use 80%
>>
>> Moreover the code has now the following structure:
>>
>>    SIEVE;
>>    for (;;) {
>>      CHECK_AND_POSSIBLY_BREAK;
>>      SIEVE;
>>    }
>>
>> There is an unneeded code duplication, it should be:
>>
>>    for (;;) {
>>      SIEVE;
>>      CHECK_AND_POSSIBLY_BREAK;
>>    }
>>
> This is a great improvement :) thanks for the additional pair of eyes :)
>
>
>> >> If you need to store larger gaps, you can also save in
>> >> the array gap>>1, because they all are even. The prime
>> >> limit will be able to go beyond 2^37...
>> >
>> >  Updated comment for how this could be done in the future.
>>
>> The first gap larger than 500, if I'm not wrong, is
>> 304599508537+514=304599509051
>>
> I added  "far" so the comment now reads "allow this to go far beyond 436M"
>
>>
>> >> I'd expect a condition like
>> >>
>> >> + if (nbits <= numberof (primegap_small) * 2 + 1)
>> >> + {
>> >> + primegap = primegap_small;
>> >> + prime_limit = nbits / 2;
>> >> + }
>>
>> > Done
>>
>> I read:
>> +  if (2 * nbits <= NUMBER_OF_PRIMES)
>> +    {
>> +      primegap = primegap_small;
>> +      prime_limit = nbits / 2;
>> +    }
>>
>> But ... this means that at most one fourth of the constants in
>> primegap_small are used, am I wrong?
>>
> I was experimenting with using 3 * nbits / 5 and other ratios and
> miscommitted this.
> Thanks again for the 2nd pair of eyes.
>
>>
>> Ĝis,
>> m
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prevprime_all.patch
Type: text/x-patch
Size: 17367 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200321/5a9c8724/attachment-0001.bin>