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

[hermann@stamm-wilbrandt.de]

On 2024-03-20 13:04, Karim Belabas wrote:
> > Can it be done faster sequentially?
>
> Sure. Less readable, though:
>
>   isProth2(p) = !(p >> (valuation(p-1,2)<<1))
>
> On my (slow) laptop:
>
>   (12:55) gp > c=0;forprime(p=3,4636016641,c++);c
>   time = 36,980 ms.
>   %1 = 218629816
>
> Your version:
>   (12:56) gp > c=0;forprime(p=3,4636016641,if(isProth(p),c++));c
>   time = 1min, 15,760 ms.
>   %2 = 10000
>
> Mine:
>   (12:57) gp > c=0;forprime(p=3,4636016641,if(isProth2(p),c++));c
>   time = 48,292 ms.
>   %3 = 10000
Thanks, definitely faster.

I cannot see why you name your laptop slow as I get same times on my AMD 
7950X CPU.

That is rank 27 of >3000 CPUs single threaded:
https://www.cpubenchmark.net/singleThread.html
That CPU is much better than the Intel CPUs above it wrt multithreaded.
All CPUs that are better than its multithreaded rank 53 do cost > 1,000$ 
for CPU alone:
https://www.cpubenchmark.net/high_end_cpus.html


I found another implementation that is (simplified, under PROG) roughly 
same speed as yours:
https://oeis.org/A080075

? #
   timer = 1 (on)
? isProth(p)=v=valuation(p-1,2);p>>v<2^v;
? c=0;forprime(p=3,4636016641,if(isProth(p),c++));c
cpu time = 1min, 12,958 ms, real time = 1min, 12,962 ms.
%61 = 10000
? isProth2(p) = !(p >> (valuation(p-1,2)<<1));
? c=0;forprime(p=3,4636016641,if(isProth2(p),c++));c
cpu time = 48,043 ms, real time = 48,045 ms.
%63 = 10000
? isproth(x)=(x>>valuation(x-1, 2))^2 < x;
? c=0;forprime(p=3,4636016641,if(isproth(p),c++));c
cpu time = 49,558 ms, real time = 49,560 ms.
%65 = 10000
?


Regards,

Hermann.