mpz_prevprime

[Seth Troisi]

On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-03-15 00:07 Seth Troisi ha scritto:
> > New patch which is cleaned up and IMO ready to commit
>
> 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.

>
> > On Mon, Mar 9, 2020 at 5:15 PM Seth Troisi <braintwo at gmail.com> wrote:
>
> >>>> I also dislike the boiler plate of the macros but I didn't
>
> Those macros should probably be moved to gmp-impl.h, to we avoid
> duplication.
> For this to be possible, we should avoid having different versions of
> the same macros in the different files...
>
I removed offset in the most recent version but I'm happy to add it back
and move the macros
into gmp-impl.h in a patch after this goes in.

>
> >> When nbits is small (IMHO the most common case) we'd like to be able
> >> to fallback to a constant array which I don't think exist for
> >> primesieve (because gmp_limb_bits isn't constant).
>
> Only the first "limb" of the sieve is hard-coded in primesieve.c, but it
> is possible to generate a larger "seed" at configure time, if we want.
>
I'm happy to look into this after this goes in.

>
> >>> Why not using a variable for INCR_LIMIT?
>
> I see now:
> +  if (nbits <= 32)
> +    incr_limit = 336;
> +  else if (nbits <= 64)
> +    incr_limit = 1550;
> +  else
> +    /* Corresponds to a merit 10 prime_gap, which is rare. */
> +    incr_limit = 7 * nbits / 2;
>
> 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;
>   else if (nbits <= 64)
>     odd_numbers_in_sieve = 775;
>   else
>    ...
>
Renamed to odds_in_composite_sieve

>
> Then I wonder if the cost of the /* Sieve next segment */ step is so
> high that we really have to try hard to avoid it. And if we are able to
> reduce the probability of its use to very unlikely, do we then really
> need to allocate the possibly huge next_mult array?
>
You're correct, this reduces the memory use 80%

>
> +      mpz_root (tmp, tmp, 2);
>
> I'd use mpz_sqrt.
>
Done

>
> +  // TODO: break the rare gap larger than this into gaps <= 255
>
> 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.

>
> +  /* Avoid having a primegap > 255, first occurence 436,273,009. */
> +  ASSERT( 4000 < sieve_limit && sieve_limit < 436000000 );
>
> Why do you need to check (4000 < sieve_limit)?
>
It's a nice sanity check that sieve_limit was correctly calculated

>
> I'd expect a condition like
>
> +  if (nbits <= numberof (primegap_small) * 2 + 1)
> +    {
> +      primegap = primegap_small;
> +      prime_limit = nbits / 2;
> +    }
>
> so that all primegap_small can be used. If you think this threshold is
> too high, then primegap_small can be reduced...
>
Done

Ĝis,
> m
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nextprime_sieve_final2.patch
Type: text/x-patch
Size: 7983 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200315/75710d54/attachment-0001.bin>