Path: csiph.com!news.mixmin.net!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: Sieve of Eratosthenes
Date: Wed, 16 Aug 2023 19:26:17 -0700
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <86msyq5rqu.fsf@linuxsc.com>
References: <ubijff$3ahf3$1@dont-email.me> <ubjedg$3emtj$1@dont-email.me> <ubjrqh$3g7ve$1@redfloyd.dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="a8782d2d7d1c356e90db8dd7e2df2f84"; logging-data="3822203"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+QfTb0KifPGG3fnJOh3q2+y9GX21swVAw="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:g13KUosUQkvvY3QVOPEouINV8uc= sha1:jKvjtNtQsrGT4lELb7gslX4eMN4=
Xref: csiph.com comp.lang.c++:91282

red floyd <no.spam.here@its.invalid> writes:

> On 8/16/2023 2:17 PM, Alf P. Steinbach wrote:
>
>> On 2023-08-16 3:37 PM, Bonita Montero wrote:
>>
>>> I tried to implement the sieve of Erastosthenes as fast as
>>> possible.  I didn't thought it would make a big difference, but
>>> having a bit-wise vector<bool> instead of a vector<char> makes the
>>> code twice as fast for my AMD 7950X PC and an upper bound of one
>>> billion.  The additional overhead for the bit-wise access is less
>>> than the additional overhead of fetching more memory
>
> [redacted]
>
> Here's mine.  I get rid of the vector<bool> by storing the prime
> factors in their own vector, and only checking for divisibility by
> primes.  [...]

Here are some suggestions for everyone.

Except for 2, 3, and 5, numbers can be considered mod 30, and
there are (conveniently) only 8 candidates:  1, 7, 11, 13, 17,
19, 23, and 29.  For numbers 7 and up, every prime must be
one of those candidates (mod 30).

By storing the results for blocks of 30 in a byte, we can
store results for all 32 bit primes in 143165577 bytes.

There are some extra tricks taking advantage of what happens
with the bit numbers.  For example 7 * 37 has two 7's, which
is 49, which is 19 mod 30, so the bit for that product will
be in the 19 position.  Being clever will avoid any shifting
or modding.

I suggest computing all 32 bit primes for the benchmark
tests.  Shouldn't take too long.