Path: ...!weretis.net!feeder8.news.weretis.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: Sieve of Erastosthenes optimized to the max
Date: Wed, 3 Jul 2024 11:25:15 +0100
Organization: A noiseless patient Spider
Lines: 60
Message-ID: <v638ud$25623$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: Wed, 03 Jul 2024 12:25:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="65486462f9b798b7ac9f14c4b0644c84";
	logging-data="2267203"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/EwvdnEyGuGPPRy5HUc2P2Nq0BtSDrz5U="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:wpSfV/cmseKS9cQUcVi3qQjU/uU=
Content-Language: en-GB
In-Reply-To: <86zfr0b9hw.fsf@linuxsc.com>
Bytes: 4569

On 02/07/2024 07:20, Tim Rentsch wrote:
> 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?

I checked. The modulus operations (%) are easy to check for.

There are two for each prime number. Not for each multiple of it, but 
for the primes themselves.

And there's one in the "get" function that checks to see if a number is 
prime.

The complexity is at least partly due to an optimisation.

You'll recall perhaps that Bonita's original code preset the entire 
bitmap to aa - which is faster than setting all the numbers divisible by 
2. I pointed out that you don't even need to set them, and set off to 
write code that stored odd numbers only.

But then I realised that if you store the mask for 3 only you get a 
pattern. It has one odd word at the beginning, then a repeating pattern 
of 3 words. It doesn't matter what the word size is.

This is equally true of 5, 7, 11 and the first few primes. It's also 
true if you set the mask up for 3 and 5 together - except this time the 
repeat length is 15.

And it's far faster to duplicate those 3, or 15, or 3*5*7, words than to 
do each prime individually.

There comes a point where it isn't worth it though - the repeat length 
for all the primes up to 31 is 1.5E12.

Exactly when it stops being worthwhile isn't obvious.

Then you came along with the mod30 suggestion. There is still a repeat 
length though, and it's still worth merging masks for small primes 
together rather than doing each one individually. But the code is 
bigger. MUCH bigger.

Andy