Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #120619

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

Show all headers | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 03:46 -0700
  Re: OT: Re: Sieve of Erastosthenes optimized to the max Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-09-28 13:49 -0700
    Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-02 11:44 +0100
      Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-10-02 13:10 +0200
      Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-10-07 08:41 -0700
        Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-20 12:44 +0100
          Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-11-04 03:56 -0800

csiph-web