Re: It is a known bug! Was: 2.16.2-beta: 2.45× slowdown in forprime()

[Ilya Zakharevich <nospam-abuse@ilyaz.org>]

On Thu, Aug 15, 2024 at 05:04:33PM -0700, Ilya Zakharevich wrote:
> On Thu, Aug 15, 2024 at 04:45:42PM -0700, Ilya Zakharevich wrote:
> > Comparing to the older versions, forprime() is perfectly OK at least
> > until 10^17.  However, for 10^18 it slows down 2.45× times:
> 
> 
> > With older PARIs, the speed decreases to about 2*10^17, then practically
> > stabilizes at about 8.8 sec per 10^8 numbers.  Contrary to this, With
> > newer PARIs, it slows down uniformly in the interval 10^17 .. 10^18:
> > 
> >   (16:35) gp > timeit(s,f) = my(t=gettime(), o=f()); if(#o, o=Str("\t",o)); printf("%s%7.3f%s\n",s,gettime()/1000,o);
> 
> In fact, the situation is yet more interesting.  With older PARI, the
> speed decreases to about 1.9e17, then SPEEDS UP abruptly, and keeps
> approximately constant:

Oups, I got hit by the bug which I already reported earlier this year!
It is just that older versions of gp/PARI report primelimit wrong:
they cap it before the gap which is >255 — but lie in the diagnostic
output (as if no capping happened).

So the new summary:
  • The older versions¹⁾ capped the primelimit at 436,273,009.
  • This value is close to the value ∼ 370,000,000 where ON THIS
    PARTICULAR MACHINE is the break-even point between two strategies
    used by forprime().
  • So for values >436,273,009² forprime() was actually using a
    strategy WHICH HAPPENS TO BE BETTER on this particular machine.

Since the artificial limitation for primelimit of the new version is a
bit higher (about 10×),

       ¹⁾ This is due to removal of the code supporting values up to
          (IIRC) 304,599,508,537.

Yours,
Ilya