hermann on Wed, 20 Mar 2024 15:54:04 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: How to efficiently count Proth primes with GP parfor? 

On 2024-03-20 15:05, Bill Allombert wrote:
On Wed, Mar 20, 2024 at 02:23:49PM +0100, hermann@stamm-wilbrandt.de wrote: 
> You need to do work by batch.
>
> isProth(p)=my(v=valuation(p-1,2));p>>v<2^v;
> export(isProth);
> {
>   my(nbt=default(nbthreads));
>   my(c=0,B=323092481\nbt);
>   parforstep(i=1,323092481,B,
>     my(cc=0);
>     forprime(p=i,min(i+B-1,323092481),cc+=isProth(p));cc
>   ,C,c+=C);c
> }
> %3 = 3000
> ? ##
>   ***   last result: cpu time 17,843 ms, real time 1,070 ms.
>
> (with 20 cores).
>
Which GP version do you run?

The GIT version!

For 2.15.4 you need to replace parforstep by parfor,
for example
{
  my(nbt=default(nbthreads));
  my(c=0,B=323092481\nbt);
  parfor(ii=0,(323092481+B-1)\B,
    my(cc=0,i=ii*B+1);
    forprime(p=i,min(i+B-1,323092481),cc+=isProth(p));cc
  ,C,c+=C);c
}


Wow — I will have to go to git version.

Yours is so much faster, even better with Karim's isProth2:

? isProth2(p) = !(p >> (valuation(p-1,2)<<1))
%8 = (p)->!(p>>(valuation(p-1,2)<<1))
? c=0;forprime(p=3,4636016641,if(isProth2(p),c++));c
cpu time = 47,468 ms, real time = 47,470 ms.
%9 = 10000
? my(nbt=default(nbthreads));my(c=0,B=4636016641\nbt);parfor(ii=0,(4636016641+B-1)\B,my(cc=0,i=ii*B+1);forprime(p=i,min(i+B-1,4636016641),cc+=isProth(p));cc,C,c+=C);c 
cpu time = 3min, 13,707 ms, real time = 6,637 ms.
%10 = 10000
? export(isProth2)
? my(nbt=default(nbthreads));my(c=0,B=4636016641\nbt);parfor(ii=0,(4636016641+B-1)\B,my(cc=0,i=ii*B+1);forprime(p=i,min(i+B-1,4636016641),cc+=isProth2(p));cc,C,c+=C);c 
cpu time = 2min, 27,991 ms, real time = 5,000 ms.
%12 = 10000
?


Wow -- 3193% CPU !!!

Regards,

Hermann.