mpz_prevprime

[Marco Bodrato]

Ciao,

Il Mer, 12 Febbraio 2020 7:26 am, Niels Möller ha scritto:
> Marco Bodrato <bodrato at mail.dm.unipi.it> writes:

>> Maybe my estimates are wrong. If they are not, the limit for trial
>> division should be increased more than linearly on the size of the

> And current code uses
>   prime_limit = nbits / 2;

> Why the constant "/ 2"? No idea, this code seems to be written by
> Torbjörn's and me a decade ago.

Before the rewrite, the code was

void
mpz_nextprime (mpz_ptr p, mpz_srcptr t)
{
  mpz_add_ui (p, t, 1L);
  while (! mpz_probab_prime_p (p, 5))
    mpz_add_ui (p, p, 1L);
}

Which had the only benefit (from my personal point of view) of returning
the next (possibly negative) probab_prime when a negative value was given
as an input :-)

The "/2" is one of the many constant that should be interesting to tune,
but it's not easy to understand exactly how to, because we do not even
really know if we need a multiplicative constant or some other curve.

>> A possible error in my analysis: I assumed a "constant cost" for each
>> new prime. That's true when updating the residues, but each new number
>> in the initial loop on _tdiv_ui imply a cost that is linear on the
>> bit-size of the number x.

> And for a small prime gap (common case), this cost should be the main
> part of the sieving. So it would make sense to optimize it. If we also
> use the ptab, we could compute modulo single-limb prime products using
> precomputed constants.

Yes, of course. And the next question will be: should we generate on the
fly an even larger table of primes when the required size grows beyond the
precomputed table?

Ĝis,
m