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

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

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.

>
[...]
>
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.

This reaction, more broadly, has been rather surprising.  The whole
point of using a sieve is that it is asymptotically faster.  Who
cares about how fast primes under a billion, or ten billion, or
fifty billion, can be computed?  It's much more interesting to ask
how high a limit can be searched in a day or a week of computing.
(I don't mean just your comment, but comments from other folks
bragging about how fast they can find all 32-bit primes.)  I ran
my earlier programs up to limits of 3 trillion or so.

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 saw this link but didn't play around with the program.

I'm pleased to be able to report that that program, written for a 1998
CPU, is slower than mine on my modern CPU.

What has been interesting is that these days prime-finding programs
really need to be tailored to the hardware they will be run on.
Somehow that seems like a step backwards.  Fifty years ago programmers
always thought about low-level hardware characteristics when writing
programs.  Over time the fraction of time spent worrying about such
things has gotten smaller and smaller, to the point now where it is
almost never important.  But wanting to write a fast prime-finding
program has taken us back to the glory days of yesteryear. ;)

Incidentally, I found a program primesieve that's available under
Ubuntu Linux.  On a whim I had it find primes less than 2**49,
which took slightly more than 12 hours elapsed time (running on 12
cores).  If computing primes up to N, a nice ratio to compute is

    (number of primes less than N) * log N / N

which converges to 1, but very slowly.  For primes less than 2**49
I got 1.03135087927594382.