Improvement to mpz_nextprime

[Robert Holmes]

I had a quick look at the mpz_nextprime code. While I noticed the new code
which is not yet enabled, it surprised me how naïve the current
implementation is.

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);
}


You can easily get a 2x speedup just by doing:

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

This probably is like it is for a reason, but I just wanted to give my input
on this

Best Regards,
Rob Holmes
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20060618/be8153ad/attachment.html