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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Jan 27, 2024 at 05:33:15AM -0800, Ilya Zakharevich wrote:
>  — discussed elsewhere on this thread (in the context of
> segfaults) — would be able to go up to the last prime in the list as
> well, when lim is the this largest prime.)
> 
> > Then one can encode “a prime difference of 256*n+m > 255 as a sequence of
> > the form
> >    0 n m
> > so one can process it in the same (rare) branch used to processing the
> > end of the list.
> 
> With the correction above, this can encode ANY prime difference > 0.
> So one can use this to introduce 0-cost¹⁾ “hiccups” in looping over
> primes.  (For example, putting such hiccups at powers of 2 gives a
> chance to switch between different algorithms tuned for particular
> magnitudes of primes.)

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.

This would allow to have a fast version of other GP functions like
prime(), primepi() isprime(), etc. 

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.
A 'smallest prime factor table' for all integers less than 2^20 
would take 4MB (using 32bit entries) and 2MB with 16bit entries
with a marker for primes.

Cheers,
Bill.