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

[Charles Greathouse <charles.greathouse@case.edu>]

> 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]