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

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 <[email protected]>
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
>
>