Charles Greathouse on Thu, 25 Oct 2012 19:14:20 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: forprime in 32bit is 50x slower if p>2^32 |
> 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... > My sieve implementation (based on the code Charles Greathouse > contributed) is currently restricted to ulongs, so to p < 2^32 on 32-bit > machines. Correct. I noticed this but never coded an efficient two-word version of the sieve. I don't have a 32-bit system to test and I expect such systems will be less and less popular. Unfortunately without a 64-bit version of Cwgwin (?) Windows users are stuck with the 32-bit version. That's a pity... > I would not make it a priority: we have many more projects than we can handle > already :-(. I feel the same way. Charles Greathouse Analyst/Programmer Case Western Reserve University On Thu, Oct 25, 2012 at 12:58 PM, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote: > * 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]