Sujet : Re: OT: Re: Sieve of Erastosthenes optimized to the max
De : tr.17687 (at) *nospam* z991.linuxsc.com (Tim Rentsch)
Groupes : comp.lang.c++Date : 11. Aug 2024, 02:24:53
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <86ikw7ykh6.fsf@linuxsc.com>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
User-Agent : Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
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.