Improvement to mpz_nextprime

[Décio Luiz Gazzoni Filho]

Has anyone considered implementing a sieve for mpz_nextprime?  
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. As a  
plus, sieving would help eliminate some pseudoprimes -- but probably  
only an inconsequential amount of them.

If the idea is sound but noone's willing to put the effort to code  
it, I offer my services to write it.

Décio

On Jun 19, 2006, at 9:39 AM, Paul Zimmermann wrote:

>> Though, it might be interesting to verify with different numbers  
>> size.
>
> Below is a test program, which gave on a 3Ghz Pentium 4 with gmp-4.2:
>
> mpz_nextprime1 took 984ms  # original version
> mpz_nextprime2 took 1008ms # suggested 'improvement'
> mpz_nextprime3 took 776ms  # original with 1 Miller-Rabin test  
> instead of 5
>
> Note a significant speedup is obtained with only 1 Miller-Rabin test.
>
> For some applications, it would be very useful to be able to give the
> number of Miller-Rabin tests in argument to mpz_nextprime. I suggest:
>
>    void mpz_nextprime3 (mpz_ptr p, mpz_srcptr t, int REPS)
>    Same as mpz_nextprime, but with REPS Miller-Rabin tests instead  
> of 5.
>
> Paul
>
> #include <stdio.h>
> #include "gmp.h"
> #include <sys/types.h>
> #include <sys/resource.h>
>
> int
> cputime ()
> {
>   struct rusage rus;
>
>   getrusage (0, &rus);
>   return rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000;
> }
>
>    void
>    mpz_nextprime1 (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);
>   }
>
>   void
>   mpz_nextprime2 (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);
>   }
>
>   void
>   mpz_nextprime3 (mpz_ptr p, mpz_srcptr t)
>   {
>     mpz_add_ui (p, t, 1L);
>     while (! mpz_probab_prime_p (p, 1))
>       mpz_add_ui (p, p, 1L);
>   }
>
> int
> main()
> {
>   int st, i;
>
>   mpz_t p;
>   mpz_init (p);
>
>   mpz_set_str (p,  
> "100000000000000000000000000000000000000000000000000", 10);
>   st = cputime ();
>   for (i = 0; i < 1000; i++)
>     mpz_nextprime1 (p, p);
>   printf ("mpz_nextprime1 took %dms\n", cputime () - st);
>
>   mpz_set_str (p,  
> "100000000000000000000000000000000000000000000000000", 10);
>   st = cputime ();
>   for (i = 0; i < 1000; i++)
>     mpz_nextprime2 (p, p);
>   printf ("mpz_nextprime2 took %dms\n", cputime () - st);
>
>   mpz_set_str (p,  
> "100000000000000000000000000000000000000000000000000", 10);
>   st = cputime ();
>   for (i = 0; i < 1000; i++)
>     mpz_nextprime3 (p, p);
>   printf ("mpz_nextprime3 took %dms\n", cputime () - st);
>
>   mpz_clear (p);
>   return 0;
> }
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20060619/9d4999e2/PGP.bin