mpz_prevprime

[Niels Möller]

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
> numbers that are tested.

And current code uses 

  prime_limit = nbits / 2;

And here "prime_limit" is a limit on the number of primes, not on the
largest prime. So the largest prime in the list grows slightly faster
than linearly with input bit size.

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

  2008-10-21  Torbjorn Granlund  <tege at gmplib.org>

	With Neils Möller:
	* mpz/nextprime.c: Rewrite.

> 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. Hmm, we wouldn't even need to split them into
separate moduli for each p.

Say we have 

  m = n mod (p_1 p_2 p_3)

Then we can do trial of n + i by testing if (m + i) is divisible by p_1,
p_2, p_3. We only have to ensure that m + i doesn't overflow a limb.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.