mpz_prevprime
Marco Bodrato
bodrato at mail.dm.unipi.it
Wed Feb 12 10:35:44 UTC 2020
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
More information about the gmp-devel
mailing list