mpz_prevprime

[Seth Troisi]

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: nextprime_sieve_final3.patch
Type: text/x-patch
Size: 7436 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200317/ea55a976/attachment.bin>