Re: [pre-announcement of a PATCH 2.16.1-alpha] VERY WRONG: 90x speedup (MUCH MORE!) of forprime() above 2^64

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

On Thu, Aug 29, 2024 at 11:13:57PM -0700, Ilya Zakharevich wrote:
> Currently I’m integrating a patch to 2.16.1 (since 2.16.2 has another
> [unfathomable???] BACKWARDS change) supporting sieving up to about
> 10^290

In the initial message, I said that the speedup was up to ∼90x (for
numbers close to 2^64), and it goes down to ∼18x closer to 10^23.  In
another message, I noted that using a proper arena size, instead of
18x, the gain is improved to ∼60x (when “closer to 10^23”).

  THIS WAS VERY WRONG!  (I did not realize that forprime() is buggy…)

The docs do not say this, but above 2^64, one needs to use forprime()
in a very particular way, like:

  forprime(p=A, B, if(isprime(p), CODE ));

And since this is MUCH slower than “just using forprime()” (which
is — together with nextprime() and precprime() — just a misnomer for
forpseudoprime(), the advantages of using sieving are actually an
order of magnitude more than I thought before:

 SUMMARY: On the whole checked range 2^64…10^23, the advantage is¹⁾
 	  >1000 times. 

    ¹⁾ Cannot be more precise (and/or extrapolate), since (judging by
       the timings) isprime() seems to be also buggy.  At least it
       shows suspiciously irregular averaged timing (I’m going to
       post a separate message about this).

Hope this helps,
Ilya

  P.S.  The patch is almost ready now.  It only touches
  	forprime.c — the rest can keep primes in whatever format one
  	wants.