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: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)
Date: Sun, 25 Feb 2024 00:48:59 -0800
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <86wmqtszd0.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <un0q3n$2ks6a$1@raubtier-asyl.eternal-september.org> <un1l6g$2q1iv$1@dont-email.me> <un2sel$33tna$1@raubtier-asyl.eternal-september.org> <un4jos$3ba8u$1@dont-email.me> <un594t$3hn5o$1@raubtier-asyl.eternal-september.org> <unagvf$ft9g$1@dont-email.me> <unaus6$h9l0$1@raubtier-asyl.eternal-september.org> <20240106000249.177@kylheku.com> <unb6jc$i4of$1@raubtier-asyl.eternal-september.org> <uncfue$ojf6$1@dont-email.me> <undpp4$117ni$1@raubtier-asyl.eternal-september.org> <unf2ip$16tqc$1@dont-email.me> <ung2bt$1eihc$1@raubtier-asyl.eternal-september.org> <20240108175039.572@kylheku.com> <unjk7k$21eto$1@raubtier-asyl.eternal-september.org> <up95f1$kibc$1@dont-email.me> <86frxsz94r.fsf@linuxsc.com> <uqo64i$3usjj$1@raubtier-asyl.eternal-september.org> <86il2fwapd.fsf@linuxsc.com> <urcds6$14fvi$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="d0a541e28d41d50395e069f34372e044"; logging-data="1854706"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+zVA+06vkMkCGyp0UTe6U0RTP2gD36a14="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:JF43wPwblnsZSCe4MtRfq7yU900= sha1:IZtl1l8gNwM0aNP6I5rL51Q1t2o=
Xref: csiph.com comp.lang.c++:118333

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 23.02.2024 um 14:51 schrieb Tim Rentsch:
>
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> Am 16.02.2024 um 17:06 schrieb Tim Rentsch:
>>>
>>>> I have an implementation (written in C) based on this approach that
>>>> determines all primes less than roughly 51.75 billion, taking just
>>>> under 56 seconds to complete.  (No threading is used - code is all
>>>> single threaded.)
>>>
>>> On my 16 core PC this takes 1.73 seconds and 43 seconds
>>> overall CPU time without printing the numbers to a file.
>>>
>>> C:\Users\Boni\Documents\Source\bitmapSieve>timep
>>> "x64\Release-clang++\bitmapSieve.exe" 51750000000 ""
>>> real   1.729s
>>> user   43.094s
>>> sys    0.094s
>>> cylces 194.738.953.589
>>
>> If you run the program as a single thread, what is the
>> elapsed time?
>
> C:\Users\Boni\Documents\Source\bitmapSieve>timep
> "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 1
> real   22.945s
> user   22.672s
> sys    0.234s
> cylces 102.917.207.295

Hmmm.  Interesting that the multi-threaded version uses almost
most twice as much CPU as the single-threaded version.  I might
have guessed more, but not twice as much.

>> Also how long does the program take to determine all
>> primes up to 3 trillion?  Here again I am interested
>> in the single-thread version.
>
> C:\Users\Boni\Documents\Source\bitmapSieve>timep
> "x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1
> real   1.234s
> user   1.203s
> sys    0.031s
> cylces 5.523.677.002

What I asked for was 3 trillion with a T, not 3 billion with
a B.  Not 3000000000 but 3000000000000.