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

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

* Bill Allombert [2012-10-25 18:27]:
> Dear PARI developers,
> 
> forprime is very slow in 32bit for large primes:
> 
> gettime();my(s);forprime(p=2,6*10^9,s++;if(s%10^7==0,print(p,":",gettime())));s
> 
>   ***   last result computed in 2min, 11,909 ms.
> give time close to 4700 ms/10^7 primes on 64bit.
> 
> On 32bit we get times around 5000ms until we hit 2^32, then:
> 
> 4222234741:4912
> 4444120783:172124
> 4666527007:261320
> 4889388631:266533
> 5112733757:270694
> 5336500537:274085
> 5560695863:274562
> 5785258351:278089
> ? ##
>   ***   last result computed in 36min, 7,175 ms.
> 
> This is a 50x slowdown. This explains why ellheegner is significantly
> slower on 32bit.

Threshold between an efficient sieve and expensive unextprime()...

My sieve implementation (based on the code Charles Greathouse
contributed) is currently restricted to ulongs, so to p < 2^32 on 32-bit
machines. The sieving code itself can handle integers < 2^64 even on
32-bit machines, but I didn't bother to develop a proper interface for
this (ulong -> GEN when computing bounds and initializing sieve chunks),
for the sake of code simplicity.

I would not make it a priority: we have many more projects than we can handle
already :-(. Anyway, the code works also on 32-bit machines, it's just
much slower there; are there still people restricted to 32-bit machines
for heavy duty computations nowadays ?

Cheers,

    K.B.

P.S: I believe unextprime() is expensive because it must certify actual 
primes [ via uisprime() ], probably not because it must eliminate
composite numbers.
-- 
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]
`