Re: Big GOTCHAs WITH forprime() (correction to the “new end-encoding scheme”)

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

Testing whether the mail glitch disappeared…  It seems that the
following message did not make it out in January:  (One more missing
message pending…)

On Tue, Jan 30, 2024 at 05:10:26PM -0800, Ilya Zakharevich wrote:
> On Sun, Jan 28, 2024 at 04:02:01PM +0100, Bill Allombert wrote:
> > Nowadays, we could just get rid of the difference table and store
> > the prime directly. Even if we use a 32bit array, we can go farther than 
> > with the current scheme.
> 
> The current scheme (together with — speedwise-free — “hiccups”) can
> work to primes of about 1<<1600.  (Although I expect it should become
> not very efficient about 1<<100…)  Do not see how you can fit this
> table into 32 bits.  ;―]
> 
> > This would allow to have a fast version of other GP functions like
> > prime(), primepi() isprime(), etc. 
> 
> Easy to do with primediff — with an external binary-search tree.
> 
> > For maxprime=2^20 (the default in 2.16)
> > The current prime difference table take 80kB.
> > Using 32bit per entry would increase that to 320kB.
> > Storing isprime as a bit vector would take 128kB.
> 
> The default of 2^20 is useless when one wants to check larger primes
> (last I checked, it was about 30x slowdown when primelimit² is
> exceeded.)
> 
>   (Although — I repeat — with the current unoptimized forprime() it is
>    not clear whether primelimit above 1e8 can give advantages.)
> 
> Hope this helps,
> Ilya