Improvement to mpz_nextprime

[Torbjorn Granlund]

"Robert Holmes" <robeholmes at gmail.com> writes:

  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);
  }
  
Have you tested your claim?

I doubt it will any measurable speedup for any
(non-constructed) case.

-- 
Torbjörn