Path: ...!feeds.phibee-telecom.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Vir Campestris <vir.campestris@invalid.invalid>
Newsgroups: comp.lang.c++
Subject: Re: OT: Re: Sieve of Erastosthenes optimized to the max
Date: Wed, 2 Oct 2024 11:44:50 +0100
Organization: A noiseless patient Spider
Lines: 49
Message-ID: <vdj872$36t95$1@dont-email.me>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
 <867celixcw.fsf@linuxsc.com> <v5sg9s$mat4$1@dont-email.me>
 <86zfr0b9hw.fsf@linuxsc.com> <v638ud$25623$1@dont-email.me>
 <861q3o5do1.fsf@linuxsc.com> <v7tdts$29195$1@dont-email.me>
 <868qx45v5g.fsf@linuxsc.com> <v9lbns$11alj$1@dont-email.me>
 <86r0aojx1m.fsf@linuxsc.com>
 <v9o2kf$1gqv1$1@raubtier-asyl.eternal-september.org>
 <va09jq$30cvv$1@dont-email.me>
 <va2ca2$3e60e$1@raubtier-asyl.eternal-september.org>
 <va2cfr$3e9l1$1@raubtier-asyl.eternal-september.org>
 <va2hq5$3f1gl$1@dont-email.me> <86v7zn3xwk.fsf@linuxsc.com>
 <vajji3$2rbid$1@raubtier-asyl.eternal-september.org>
 <vb2if8$1jqts$2@dont-email.me> <86tteyrad0.fsf@linuxsc.com>
 <vb7efc$3dfh8$1@dont-email.me> <86wmiw3vk2.fsf@linuxsc.com>
 <871q13sdv3.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 02 Oct 2024 12:44:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e56e54daf09c85184a6336540f7aa120";
	logging-data="3372325"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+iDzRKzTjvMlr41W/8C+KXcaaRmj44usc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:jnrOsHj0Zn+a5r7lch4ELi+na1w=
In-Reply-To: <871q13sdv3.fsf@nosuchdomain.example.com>
Content-Language: en-GB
Bytes: 3459

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