Re: [very-early-bird-PATCH 2.16.1-alpha] Re: NNNx speedup of forprime() etc.

["Edgar Costa" <edgarc@mit.edu>]

For ranges up to 2^64, https://github.com/kimwalisch/primesieve might be a better choice.

And if you can beat that, then I would suggest making a PR there, as primesieve is the current golden standard.

On Tue, Oct 1, 2024 at 7:02 PM Ilya Zakharevich <nospam-abuse@ilyaz.org> wrote:

On Tue, Oct 01, 2024 at 01:03:56AM -0700, Ilya Zakharevich wrote:
> This is a very early variant of the (working) patch for 2.1.16-alpha primediff support.  As I already explained, the code shows:
>
>  • Up to 20x speedup of sieving-for-primes up to 2^64.
>  • More than 1000x speedup of looking for primes between 2^64 to primelimit².
>  • More than 50x (and up to 90x) speedup of looking for pseudoprimes in the same range.
>  • primelimit is only memory-limited, with large prime tables taking¹⁾ about 1.01 bytes per prime.
>  • Speedup up to²⁾ 5x of looping through primes (or pseudoprimes) above primelimit².

Just to make it crystal clear: the listed improvements WOULD NOT
speedup the gp code executed INSIDE forprime().  These are (the
eventual…) improvements to the OVERHEAD of forprime() related to
“finding primes”.

For example, some actual code of mine takes “very long time” inside
every iteration of forprime().  This scenario would not benefit from
the speedups above!

Hope this helps,
Ilya