Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: OT: Re: Sieve of Erastosthenes optimized to the max Date: Mon, 07 Oct 2024 08:41:21 -0700 Organization: A noiseless patient Spider Lines: 76 Message-ID: <86msjfzzry.fsf@linuxsc.com> References: <86zfr0b9hw.fsf@linuxsc.com> <861q3o5do1.fsf@linuxsc.com> <868qx45v5g.fsf@linuxsc.com> <86r0aojx1m.fsf@linuxsc.com> <86v7zn3xwk.fsf@linuxsc.com> <86tteyrad0.fsf@linuxsc.com> <86wmiw3vk2.fsf@linuxsc.com> <871q13sdv3.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Mon, 07 Oct 2024 17:41:22 +0200 (CEST) Injection-Info: dont-email.me; posting-host="a62c12983f398f111226e581353fb46e"; logging-data="1829219"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+62sEkT/NKKjRKsM6oK67DXWA55Lnboc8=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:9Eunv5IUh+JMxi8EEi7359VSQxY= sha1:ZFpzSwuNn+S1jdNYTJ+0WNaJoKc= Xref: csiph.com comp.lang.c++:120619 Vir Campestris writes: > On 28/09/2024 21:49, Keith Thompson wrote: > >> Tim Rentsch writes: >> >>> Vir Campestris 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 > > > > and to a program > > > > 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.