Improvement to mpz_nextprime

[Torbjorn Granlund]

Décio Luiz Gazzoni Filho <decio at decpp.net> writes:

  Has anyone considered implementing a sieve for mpz_nextprime?

The commented-out code in mpz/nextprime.c is a somewhat backwards
sieve.

I have made an unfinished effort at implementing a real sieve.  I
have attached my stuff at the end.  Perhaps it is not useful.

  Estimate the distance to the next prime (crude estimate is log n,
  would have to look up better estimates), add some experimentally-
  determined fudge factor, sieve to a reasonable amount and apply
  mpz_probab_prime() to the survivors. If no primes are found,
  either  keep sieving (probably with a smaller range), or revert
  to the  original sequential algorithm, whichever works best in
  practice.

Makes sense.  Make sure that, if you resieving with a smaller size,
you don't keep decreasing it so that no forward progress is made.

I'd suggest something along these lines:

sievesize = 1.5 * log (n)
small_sievesize = sievesize / 2
if (sievesize > LIMIT_TO_CONSERVE_MEMORY)
  {
    sievesize = LIMIT_TO_CONSERVE_MEMORY;
    small_sievesize = LIMIT_TO_CONSERVE_MEMORY;
  }
success = try_sieve (p, n, sievesize);
if (success)
  return p;
n += sievesize;
for (;;)
  {
    success = try_sieve (p, n, small_sievesize);
    if (success)
      return p;
    n += small_sievesize;
  }  

The next question is how large primes to include in the sieve, and how
to compute these primes.  There have been plans to include a prime
list in GMP; such a list will have to be quite limited in size.

For small enough n, one would include an n dependent number of sieve
primes, over a limit one need to cap the primes and then run a pseudo
prime test for the remaining numbers.

Also mpz_probab_prime_p needs an overhaul, perhaps at the same time.
As Paul suggests, we want a variant of mpz_nextprime with an
repetition argument.  Or, perhaps it is better to add new variants of
mpz_probab_prime_p and mpz_nextprime that accepts some sort of
probability argument, allowing us to more smoothly change from Miller
Rabin to a stronger underlying test.

(The current mpz_nextprime and mpz_probab_prime_p would then perhaps be
implemented in terms of the new functions.)

-------------- next part --------------
A non-text attachment was scrubbed...
Name: nextprime.c
Type: application/octet-stream
Size: 3086 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20060619/72e491b0/nextprime-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nextprime2.c
Type: application/octet-stream
Size: 24050 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20060619/72e491b0/nextprime2-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nextprime123.c
Type: application/octet-stream
Size: 9317 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20060619/72e491b0/nextprime123-0001.obj
-------------- next part --------------

-- 
Torbjörn