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

On 28/09/2024 21:49, Keith Thompson wrote:

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

Vir Campestris <vir.campestris@invalid.invalid> writes:
>
[...]
>
I tried to post a short followup, but I must have done something
wrong because nothing went out.  Long story short, I've been
pulled away from looking at this further due to other tasks
demanding my attention, and also because the Sieve of Aiken
looks more promising (having been reminded recently of
primegen by Daniel Bernstein).

 Typo: Sieve of Atkin.
 https://en.wikipedia.org/wiki/Sieve_of_Atkin
 

In any case, thank you for the back and forth, it's been fun.

 

Well, the holiday was fun (the Zeppelin museum on the Bodensee was especially interesting for geeks) but my wife picked up what we think was COVID in one of the hotels so she was a bit **** towards the end.
Then she gave it to me :(
However...
I now have a working version storing all primes as (prime/30 mask(prime%30) and tuned up.
The disappointing thing is that it's not until you get to seriously big numbers - something in the 1e9 range - that this is faster than the code I posted before. And even then it's not _much_ faster. About 20% at 1e11.
Over in comp.lang.c this came up too, and there's a link there to the Sieve of Atkin
<https://en.wikipedia.org/wiki/Sieve_of_Atkin>
and to a program
<http://cr.yp.to/primegen.html>
which implements it.
I'm pleased to be able to report that that program, written for a 1998 CPU, is slower than mine on my modern CPU.
Andy