Re: OT: Re: Sieve of Erastosthenes optimized to the max

On 27/08/2024 05:09, Bonita Montero wrote:

Am 26.08.2024 um 21:08 schrieb Tim Rentsch:
 

One motivation for choosing a mod30 representation is being able to
compute more primes -- almost twice as many.  Any machine with 64GB
of memory should be able to compute primes up to 1.5 trillion.

 You don't need to hold all primes in memory. Just calculate the primes
up to the square root and then you can calculate every segment up to
the maximum from that.

So you compute all the primes up to the square root of a larger number.
I was cleaning up my odds-only code with a view to posting it, when I had an idea.
Take 101 (because I can write things more easily).
I want to mark
10201,10302,10403,10504,10605,10706...
With odds only that becomes
10201,10403,10605,10807,11009,11211...
and as the loop increment is a constant it is nice and fast. With mod30 it isn't a constant, and it hurts to work out the increment.
Except...
If I mark 10201,13231,16261,19291,22321
with an increment of 30*p,
then go back to 10201, add 2p, then increment that by 30
10201 13231 16261
and do that for the other 6 of the 8, my inner loop has a constant increment, and my code is compatible with the mod30 store.
That might be quicker. I also have some thoughts over storing the prime as two parts. It's 30m+r, where m is modulus and r remainder. r maps one-for-one into the byte mask, and m is the index.
I'm going to waste lots more time on this I can see!
Andy