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

On 16/08/2024 18:35, Bonita Montero wrote:

But basically I don't think it is a good idea to skip numbers exept
multiples of two. With the three you save a sixth of memory, with
the five you save a 15-th and at the end you get about 20% less
storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
for a lot of computation. That's the point where I dropped this
idea and I think this extra computation is higher than the time
for the saved memory loads.

I've been running some experiments.
Skipping evens only is nice and simple on computation; that's good.
Skipping something else requires table lookups. I've knocked up some code that uses the correct table for skipping primes (but not for mask bit selection) and run it for 2*3*5, 2*3*5*7, and 2*3*5*7*11.
Only the last one is faster than just skipping evens. And it's not much faster at the price of much more complexity, and a lot more store use.
My hack will only work with a prime which is 1 modulo(2*3*5*7*11) and it would take a lot more code to make it work for all the other modulo values. And even more if I was to make it work out the bitmaps.
I think we've done this to death now (and still with no C++ content!).
I'm happy with my algorithm:
- Work out a bitmask for some small primes, only as far as is needed to get repeats (the repeat length is the product of the primes)
- Work out bitmasks for the next half a dozen. Each of those will have a repeat the length of the prime.
- Combine those together into the output bitmap. That requires fewer operations than doing each one into the output bitmap
- Process the larger primes. Do the output bitmap in blocks for cache friendliness
Note that the larger the prime the less time it takes.
Andy