Path: csiph.com!news.mixmin.net!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: Mon, 26 Aug 2024 09:35:55 -0700
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <864j775jis.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <868qx45v5g.fsf@linuxsc.com> <v9lbns$11alj$1@dont-email.me> <86r0aojx1m.fsf@linuxsc.com> <v9o2kf$1gqv1$1@raubtier-asyl.eternal-september.org> <va0a8b$30cvv$2@dont-email.me> <va14rc$387ss$1@redfloyd.dont-email.me> <va2tf8$3gpbu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 26 Aug 2024 18:35:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d6baed66fa18aad174400126e3461865"; logging-data="2674114"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/XCP9fppFn9gsQDteartukYt3DiGrZUJY="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:mow9b84PSWrufLcom99TWaPfdnI= sha1:Rh3S7t4Az6XVQilIhxqKxkUlsgE=
Xref: csiph.com comp.lang.c++:119912

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

> On 20/08/2024 05:08, red floyd wrote:
>
>> So I'm a little late, but here's my effort to use the modulo
>> 30 trick.
>>
>> Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5
>> 5600x, 64GB RAM
>>
>> g++ -O3 -std=c++17
>> 5761455 primess less than 100 million in 0.182269s
>> 50847534 primes less than 1 billion in 2.841167s
>> 455052511 primes less than 10billion in 53.009133s
>
> It's slow.
>
> Looking quickly at the (remarkably small) code I see line 30:
>
> return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]);
>
> That mod and div are being called for every single time you
> mark a prime in the bitmap.

That is a cost but I'm pretty sure it's not the most important
aspect.