Re: Sieve of Erastosthenes optimized to the max

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

Vir Campestris <vir.campestris@invalid.invalid> writes:
 

On 19/06/2024 01:34, Tim Rentsch wrote:
>

Would you mind if I asked you to post the code so I can
take a look at it?  Or if you would rather email it to
me that also works.

>
I've hacked out all my include files, added a GPL licence, and
included build instructions.  It follows in the signature block.
600 lines :(
>
I bet the line wrapping breaks it too.

 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?

The mods and divs should _not_ be in the main path. It would be interesting to see your code. Or for that matter to see a performance report from it.
The template is mostly just to allow me to experiment with the size of the stored data. That's not easy with the mod30 scheme, but with the original one I found the code ran faster when I did everything with uint64_t data.
Perhaps I could use mod (8*30)!
Something that has come to mind as an enhancement - at the moment for larger primes it thinks about all the odd numbers that are a multiple of the prime, and sets them in the mask. It doesn't need to do them all - for each prime there's a set of steps that can be done. For 7, for example, you start at 49, then add at each step 7 multiplied by 4 2 4 2 4 6 2 6. That pattern of 8 repeats infinitely. It's the same for all the other primes, a pattern of 8.
Andy