Deutsch English Français Italiano |
<864j775jis.fsf@linuxsc.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!2.eu.feeder.erje.net!feeder.erje.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= Bytes: 2432 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.