Re: Sieve of Erastosthenes optimized to the max

On 02/07/2024 07:20, Tim Rentsch wrote:

I got the code.  There were some line wrappings but I just went
through and fixed those by hand.  After fixing the problem line
wraps I was able to compile and run the code (I used std=c++17,
which apparently works okay).  I did a simple check to make sure
the primes being found are right, which they do indeed seem to
be.  I haven't really experimented with changing the code;  I
only just ran it with various bounds on what primes to find,
mostly to get a sense of the performance.
 I admit I don't understand the scheme the code is using.  It
looks to me like the code is doing divisions and remainders a
lot, which my code basically doesn't do at all (it does do one
division for each prime up to the square root of the limit of
primes being sought, but that's all).  I know the big template
near the beginning is crucial to understanding what the code is
doing, but I haven't been able to figure out what abstraction
that template is supposed to represent.  The core of my program
is between 50 and 60 lines, and all pretty straightforward.
 Is there some suggestion you could make or a question you would
like to ask?  What can I do that might be helpful?

I checked. The modulus operations (%) are easy to check for.
There are two for each prime number. Not for each multiple of it, but for the primes themselves.
And there's one in the "get" function that checks to see if a number is prime.
The complexity is at least partly due to an optimisation.
You'll recall perhaps that Bonita's original code preset the entire bitmap to aa - which is faster than setting all the numbers divisible by 2. I pointed out that you don't even need to set them, and set off to write code that stored odd numbers only.
But then I realised that if you store the mask for 3 only you get a pattern. It has one odd word at the beginning, then a repeating pattern of 3 words. It doesn't matter what the word size is.
This is equally true of 5, 7, 11 and the first few primes. It's also true if you set the mask up for 3 and 5 together - except this time the repeat length is 15.
And it's far faster to duplicate those 3, or 15, or 3*5*7, words than to do each prime individually.
There comes a point where it isn't worth it though - the repeat length for all the primes up to 31 is 1.5E12.
Exactly when it stops being worthwhile isn't obvious.
Then you came along with the mod30 suggestion. There is still a repeat length though, and it's still worth merging masks for small primes together rather than doing each one individually. But the code is bigger. MUCH bigger.
Andy