Path: ...!news.nobody.at!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: Sieve of Erastosthenes optimized to the max
Date: Tue, 2 Jul 2024 21:24:48 +0100
Organization: A noiseless patient Spider
Lines: 57
Message-ID: <v61nmg$1pb9h$1@dont-email.me>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
 <ume6ap$3ecjk$1@raubtier-asyl.eternal-september.org>
 <umfcqi$3jktj$2@dont-email.me>
 <umgbci$3qpao$1@raubtier-asyl.eternal-september.org>
 <utlf3h$393l6$1@dont-email.me>
 <utn1fp$3oeks$2@raubtier-asyl.eternal-september.org>
 <utng4n$3rn1f$2@dont-email.me>
 <utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>
 <utq0ag$hvrl$3@dont-email.me>
 <utq0os$ibqn$1@raubtier-asyl.eternal-september.org>
 <utq11p$icmm$1@dont-email.me> <v25c87$1ld9m$1@dont-email.me>
 <86r0duwqgg.fsf@linuxsc.com> <v39o3l$1lvju$1@dont-email.me>
 <86o78mpnlf.fsf@linuxsc.com> <v3fv2u$2ursd$1@dont-email.me>
 <86ttibod7n.fsf@linuxsc.com> <86h6eaoi2r.fsf@linuxsc.com>
 <v4sool$1grge$1@dont-email.me> <867celixcw.fsf@linuxsc.com>
 <v5sg9s$mat4$1@dont-email.me> <86zfr0b9hw.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 02 Jul 2024 22:24:49 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5bad8780739df997942d75d9163bd3ac";
	logging-data="1879345"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18E5YtCg3D9LpMCYP3OrhryLpg0b9D6hNA="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:0/YmgvWcKHjxrzJjVzQPDO5mkAA=
Content-Language: en-GB
In-Reply-To: <86zfr0b9hw.fsf@linuxsc.com>
Bytes: 4454

On 02/07/2024 07:20, Tim Rentsch wrote:
> Vir Campestris <vir.campestris@invalid.invalid> writes:
> 
>> On 19/06/2024 01:34, Tim Rentsch wrote:
>>
>>> Would you mind if I asked you to post the code so I can
>>> take a look at it?  Or if you would rather email it to
>>> me that also works.
>>
>> I've hacked out all my include files, added a GPL licence, and
>> included build instructions.  It follows in the signature block.
>> 600 lines :(
>>
>> I bet the line wrapping breaks it too.
> 
> I got the code.  There were some line wrappings but I just went
> through and fixed those by hand.  After fixing the problem line
> wraps I was able to compile and run the code (I used std=c++17,
> which apparently works okay).  I did a simple check to make sure
> the primes being found are right, which they do indeed seem to
> be.  I haven't really experimented with changing the code;  I
> only just ran it with various bounds on what primes to find,
> mostly to get a sense of the performance.
> 
> I admit I don't understand the scheme the code is using.  It
> looks to me like the code is doing divisions and remainders a
> lot, which my code basically doesn't do at all (it does do one
> division for each prime up to the square root of the limit of
> primes being sought, but that's all).  I know the big template
> near the beginning is crucial to understanding what the code is
> doing, but I haven't been able to figure out what abstraction
> that template is supposed to represent.  The core of my program
> is between 50 and 60 lines, and all pretty straightforward.
> 
> Is there some suggestion you could make or a question you would
> like to ask?  What can I do that might be helpful?

The mods and divs should _not_ be in the main path. It would be 
interesting to see your code. Or for that matter to see a performance 
report from it.

The template is mostly just to allow me to experiment with the size of 
the stored data. That's not easy with the mod30 scheme, but with the 
original one I found the code ran faster when I did everything with 
uint64_t data.

Perhaps I could use mod (8*30)!

Something that has come to mind as an enhancement - at the moment for 
larger primes it thinks about all the odd numbers that are a multiple of 
the prime, and sets them in the mask. It doesn't need to do them all - 
for each prime there's a set of steps that can be done. For 7, for 
example, you start at 49, then add at each step 7 multiplied by 4 2 4 2 
4 6 2 6. That pattern of 8 repeats infinitely. It's the same for all the 
other primes, a pattern of 8.

Andy