Re: [PATCH 2.16-2-beta]: about 20x speedup of forprime() in 10^12 .. 2^64

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Aug 18, 2024 at 06:17:50AM -0700, Ilya Zakharevich wrote:
> On a contemporary low-midlevel CPU (13th Gen Intel(R) Core(TM) i5-13500T), with
> 
>     timeit(s,f) = my(t=gettime(), o=f()); if(#o, o=Str("\t",o)); printf("%s%7.3f%s\n",s,gettime()/1000,o);
>     my(c, L=2*10^9); for(k=8,19, c=0; timeit(Strprintf("10^%d\t",k), (()->forprime(p=10^k,10^k+L,c++);c)))
> 
> SUMMARY: with this patch, the overhead of forprime in the range
> 2^32..2^64 is a constant overhead of “1.5 increments (as in c++)” per
> a found prime, plus the overhead of “√(N/10^19) increments” for
> sieving near N.

Could explain what rem_half does ?

If I understand correctly, 
you are suggesting to change is optimal_chunk:
ulong chunk = 0x80000UL;
to
ulong chunk = 0x800000UL;

Is it correct ?

Cheers,
Bill