Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: OT: Re: Sieve of Erastosthenes optimized to the max
Date: Sun, 01 Sep 2024 20:40:59 -0700
Organization: A noiseless patient Spider
Lines: 71
Message-ID: <86tteyrad0.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 02 Sep 2024 05:41:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8d0da47a40f6e375f3916ecef59d9608";
	logging-data="1937492"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Ye8Ln7+HGyAW8AWG6sdx+fSxYlI1DcM4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:xXczhRLkC0ybJWjNi0r5GdQ30hY=
	sha1:ww9b13OkGIKpp+5ZbFcSLcxC5xw=
Bytes: 4481

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 27/08/2024 05:09, Bonita Montero wrote:
>
>> Am 26.08.2024 um 21:08 schrieb Tim Rentsch:
>>
>>> One motivation for choosing a mod30 representation is being able to
>>> compute more primes -- almost twice as many.  Any machine with 64GB
>>> of memory should be able to compute primes up to 1.5 trillion.
>>
>> You don't need to hold all primes in memory.  Just calculate the primes
>> up to the square root and then you can calculate every segment up to
>> the maximum from that.

This is a brainless statement (and incidentally illustrates why I
was motivated not to read postings from BM).  In fact no primes need
be pre-calculated to determine whether any given number is prime.
The point of using a sieve is the sieve method is much faster than
not using one.  For example, suppose we want to determine all primes
less than a trillion.  Taking the approach of pre-computing only
those primes less than a million (the square root) and then testing
numbers individually takes more than 100 times as many operations as
using a sieve.  Furthermore the operations used are more expensive
for the non-sieve approach - simply setting a bit in the case of a
sieve, versus computing a remainder in the non-sieve case.

> So you compute all the primes up to the square root of a larger number.
>
> I was cleaning up my odds-only code with a view to posting it, when I
> had an idea.
>
> Take 101 (because I can write things more easily).
>
> I want to mark
>
> 10201,10302,10403,10504,10605,10706...
>
> With odds only that becomes
> 10201,10403,10605,10807,11009,11211...

Right.  Marking of multiples needs to start only at p*p, not
at p+2.

> and as the loop increment is a constant it is nice and fast.  With
> mod30 it isn't a constant, and it hurts to work out the increment.
>
> Except...
>
> If I mark 10201,13231,16261,19291,22321
> with an increment of 30*p,
>
> then go back to 10201, add 2p, then increment that by 30
> 10201	13231	16261
> and do that for the other 6 of the 8, my inner loop has a constant
> increment, and my code is compatible with the mod30 store.

Yes, reordering the loops this way might very well make things
work better.  It also has the property, I believe, that the
bit to set is the same in each of the eight outer loops, and
so can be computed only once for each of the eight outer loops.
Very good!

> That might be quicker.  I also have some thoughts over storing the
> prime as two parts.  It's 30m+r, where m is modulus and r remainder. r
> maps one-for-one into the byte mask, and m is the index.

This is what I've been saying all along!

> I'm going to waste lots more time on this I can see!

I'm interested to see what you come up with.