Path: csiph.com!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: Sat, 10 Aug 2024 17:24:53 -0700
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <86ikw7ykh6.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <v638ud$25623$1@dont-email.me> <861q3o5do1.fsf@linuxsc.com> <v7tdts$29195$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sun, 11 Aug 2024 02:24:54 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e27eccf1f18fd326d4b617bedae077c0"; logging-data="1024249"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19d3oecBCfnVVFmHcTs9QQ17kA6smTWgu0="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:LD1FXFyOVUK+U11fLrqJnkOoJ90= sha1:hoZLxyYYmm/VyaMHLPLDNTBlxvs=
Xref: csiph.com comp.lang.c++:119793

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

This post is my second response to your comments, more
specifically to one part of your comments.

> On 20/07/2024 15:41, Tim Rentsch wrote:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>> On 02/07/2024 07:20, Tim Rentsch wrote:

[...]

> I had also considered looking for a mod-div value greater than 30.
>
> Bonita's original code stored a bit for every prime.  We can call
> that a compression ratio of 1.  I store the odd only, so the
> compression ratio is 2.  By storing mod30 you increase that to
> 3.75.  But there's a cost on modern computers because it implies
> lots of byte level access to store.
>
> If on the other hand we store mod(2*3*5*7*11), which is 2310, we
> get 480 candidates.  480 isn't far off 512 which is a nice size
> for us to handle, and gives us an even better compression ratio of
> just over 4.5.  But of course all those tables with 8 or 30
> entries will be getting a bit big and painful.

I tried using a mod 240 encoding, so the units are 64-bit elements,
to see if the more natural sized access would help.  The result ran
slower than the mod 30 code.

The idea of using more primes seems like a natural extension, and
maybe it can work.  Certainly it can get greater compression, which
is a plus.  I had looked before at using a mod 210 encoding (which
is 30 * 7).  My sense is that, unless the extra compression is
essential, the added code complexity will hurt performance more
than it helps.  But I never got to the point of actually coding
it.