Re: forprime in 32bit is 50x slower if p>2^32

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2012-10-25 21:02]:
> On Thu, Oct 25, 2012 at 01:13:39PM -0400, Charles Greathouse wrote:
> > > Threshold between an efficient sieve and expensive unextprime()...
> > 
> > No, even worse: it has to use nextprime(). This means it loops through
> > the good congruence classes mod 210 and runs BPSW_psp until it finds a
> > hit...
> 
> Maybe we could at least replace 210 by something larger.

I doubt it would help unless you make is *much* larger. BPSW_psp() starts by
trial dividing by all primes <= 101, so all composites with small factors are
quickly detected already. I'd expect most of the computing time (say 50% ?) to
be "wasted" certifying actual primes.

(22:35) gp > B = 2*3*5*7*11*13*17*19*23*29*31*37;

(22:36) gp > forstep(n = 1, B * 10^6, B, isprime(n))
time = 3,597 ms.
(22:36) gp > forstep(n = 2, B * 10^6, B, isprime(n))
time = 188 ms.
(22:36) gp > forstep(n = 3, B * 10^6, B, isprime(n))
time = 665 ms.
(22:37) gp > forstep(n = 11, B * 10^6, B, isprime(n))
time = 644 ms.
(22:37) gp > forstep(n = 37, B * 10^6, B, isprime(n))
time = 641 ms.

Odd composites with obvious small factors are treated in less than 20% of the
time compared to genuine candidates = 1 (mod B) [ about 16% of them are primes
in this range ]. Replacing 210 by 210 * B (for some B coprime with 210) is only
going to reduce the number of treated integers by a factor of B / \phi(B)
only; and you're only removing the fast ones...

Cheers,


    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`