Re: Implementation of forprime() and unextprime()

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

On Thu, Jan 11, 2024 at 07:09:51PM -0800, Ilya Zakharevich wrote:
>   B) unextprime() (the ulong version of nextprime() from
>      basemath/ifactor1.c) has a rather convoluted code to sieve mod
>      210.  Why not:
> 
>       • just store tables with a bitmap of a few (say 8) next odd
>       	residues mod N which are mutually prime with N.  (Indexed by
>       	“an odd” residue mod N.)
>       • For a given odd number, extract the corresponding bitmaps from
>       	the tables for a few values of N (such as 210, 11*19, 13*17, 23 and 29).
>       • “bit-AND” these bitmaps.
>       • Use the count of trailing/leading 0 bits (should be cheap) to
>       	jump ahead.
> 
>      I would not be surprised if this can speedup the code by 20%
>      (maybe even a bit more for numbers closer to 2^64).

I have made a branch bill-unextprime with a simpler algorithm,
but the speed is exactly the same, which means that all the time is
spent in uisprime.

Cheers,
Bill.