Karim Belabas on Thu, 25 Oct 2012 18:58:10 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: forprime in 32bit is 50x slower if p>2^32 |
* 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] `