Message-ID:

Perfection is achieved only on the point of collapse. -- C. N. Parkinson

devel / comp.lang.c++ / Re: Sieve of Erastosthenes optimized to the max

Re: Sieve of Erastosthenes optimized to the max

<utq0ag$hvrl$3@dont-email.me>

https://www.rocksolidbbs.com/devel/article-flat.php?id=3382&group=comp.lang.c%2B%2B#3382

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m.thomasson.1@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Sun, 24 Mar 2024 12:52:48 -0700
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <utq0ag$hvrl$3@dont-email.me>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<um2dsb$17vgg$2@dont-email.me>
<um2vpr$1e7pn$1@raubtier-asyl.eternal-september.org>
<um31o0$1edq3$1@dont-email.me>
<um4f1l$1l1c2$1@raubtier-asyl.eternal-september.org>
<um7haa$274oh$3@dont-email.me>
<um8vlp$2h8oc$1@raubtier-asyl.eternal-september.org>
<uma7i4$2nagg$1@dont-email.me>
<umdmkf$3clht$1@raubtier-asyl.eternal-september.org>
<umdovb$3cmi3$2@dont-email.me>
<ume6ap$3ecjk$1@raubtier-asyl.eternal-september.org>
<umfcqi$3jktj$2@dont-email.me>
<umgbci$3qpao$1@raubtier-asyl.eternal-september.org>
<utlf3h$393l6$1@dont-email.me>
<utn1fp$3oeks$2@raubtier-asyl.eternal-september.org>
<utng4n$3rn1f$2@dont-email.me>
<utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 24 Mar 2024 19:52:48 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="d025a76bd6d95d530e804f50fadb4211";
logging-data="589685"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18+kpaTdFEhKkrMxqzQa0l/hHxU+Y52aMk="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:zrYzVITTwQsMC3aVFjY+eewg3jw=
Content-Language: en-US
In-Reply-To: <utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>

by: Chris M. Thomasson - Sun, 24 Mar 2024 19:52 UTC

On 3/23/2024 11:30 PM, Bonita Montero wrote:
> Am 23.03.2024 um 22:04 schrieb Chris M. Thomasson:
>> On 3/23/2024 9:54 AM, Bonita Montero wrote:
>>> Am 23.03.2024 um 03:34 schrieb Chris M. Thomasson:
>>>> On 12/26/2023 9:06 PM, Bonita Montero wrote:
>>>>> Am 26.12.2023 um 21:24 schrieb Chris M. Thomasson:
>>>>>
>>>>>> So, are you familiar with Intel's early hyper threading problem?
>>>>>> There was false sharing between the ...
>>>>>
>>>>> False sharing can only happen between different cores.
>>>>
>>>> Sigh.
>>>
>>> Why ? Do you think false sharing can happen between the threads
>>> of a single core ?
>>>
>>
>> Sigh again...
>
> On a single core CPU with two thread's there's never false sharing.
>

Whatever you say man... ;^o

Re: Sieve of Erastosthenes optimized to the max

<utq0os$ibqn$1@raubtier-asyl.eternal-september.org>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3383&group=comp.lang.c%2B%2B#3383

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.Montero@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Sun, 24 Mar 2024 21:00:30 +0100
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <utq0os$ibqn$1@raubtier-asyl.eternal-september.org>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<um2dsb$17vgg$2@dont-email.me>
<um2vpr$1e7pn$1@raubtier-asyl.eternal-september.org>
<um31o0$1edq3$1@dont-email.me>
<um4f1l$1l1c2$1@raubtier-asyl.eternal-september.org>
<um7haa$274oh$3@dont-email.me>
<um8vlp$2h8oc$1@raubtier-asyl.eternal-september.org>
<uma7i4$2nagg$1@dont-email.me>
<umdmkf$3clht$1@raubtier-asyl.eternal-september.org>
<umdovb$3cmi3$2@dont-email.me>
<ume6ap$3ecjk$1@raubtier-asyl.eternal-september.org>
<umfcqi$3jktj$2@dont-email.me>
<umgbci$3qpao$1@raubtier-asyl.eternal-september.org>
<utlf3h$393l6$1@dont-email.me>
<utn1fp$3oeks$2@raubtier-asyl.eternal-september.org>
<utng4n$3rn1f$2@dont-email.me>
<utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>
<utq0ag$hvrl$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 24 Mar 2024 21:00:29 +0100
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="661bbc650b0e553e73b14b7d466277cb";
logging-data="601943"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX181qixhLlfpQ+LVHsJmC9HUwyxl38/uwus="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:rZXcgGGkoi9LiWFfLE9skAcv7PI=
In-Reply-To: <utq0ag$hvrl$3@dont-email.me>
Content-Language: de-DE

by: Bonita Montero - Sun, 24 Mar 2024 20:00 UTC

Am 24.03.2024 um 20:52 schrieb Chris M. Thomasson:
> On 3/23/2024 11:30 PM, Bonita Montero wrote:
>> Am 23.03.2024 um 22:04 schrieb Chris M. Thomasson:
>>> On 3/23/2024 9:54 AM, Bonita Montero wrote:
>>>> Am 23.03.2024 um 03:34 schrieb Chris M. Thomasson:
>>>>> On 12/26/2023 9:06 PM, Bonita Montero wrote:
>>>>>> Am 26.12.2023 um 21:24 schrieb Chris M. Thomasson:
>>>>>>
>>>>>>> So, are you familiar with Intel's early hyper threading problem?
>>>>>>> There was false sharing between the ...
>>>>>>
>>>>>> False sharing can only happen between different cores.
>>>>>
>>>>> Sigh.
>>>>
>>>> Why ? Do you think false sharing can happen between the threads
>>>> of a single core ?
>>>>
>>>
>>> Sigh again...
>>
>> On a single core CPU with two thread's there's never false sharing.
>>
>
> Whatever you say man... ;^o

You said:

> So, are you familiar with Intel's early hyper threading problem?
There was false sharing between the hyperhtreads.

False sharing is a kind of cache thrashing, but not every cache
thrashing is false sharing. False sharing can only happen between
different cores and the Pentium 4 HT does only have one core.

Re: Sieve of Erastosthenes optimized to the max

<utq11p$icmm$1@dont-email.me>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3384&group=comp.lang.c%2B%2B#3384

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m.thomasson.1@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Sun, 24 Mar 2024 13:05:12 -0700
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <utq11p$icmm$1@dont-email.me>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<um2dsb$17vgg$2@dont-email.me>
<um2vpr$1e7pn$1@raubtier-asyl.eternal-september.org>
<um31o0$1edq3$1@dont-email.me>
<um4f1l$1l1c2$1@raubtier-asyl.eternal-september.org>
<um7haa$274oh$3@dont-email.me>
<um8vlp$2h8oc$1@raubtier-asyl.eternal-september.org>
<uma7i4$2nagg$1@dont-email.me>
<umdmkf$3clht$1@raubtier-asyl.eternal-september.org>
<umdovb$3cmi3$2@dont-email.me>
<ume6ap$3ecjk$1@raubtier-asyl.eternal-september.org>
<umfcqi$3jktj$2@dont-email.me>
<umgbci$3qpao$1@raubtier-asyl.eternal-september.org>
<utlf3h$393l6$1@dont-email.me>
<utn1fp$3oeks$2@raubtier-asyl.eternal-september.org>
<utng4n$3rn1f$2@dont-email.me>
<utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>
<utq0ag$hvrl$3@dont-email.me>
<utq0os$ibqn$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 24 Mar 2024 21:05:13 +0100
Injection-Info: dont-email.me; posting-host="d025a76bd6d95d530e804f50fadb4211";
logging-data="602838"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+qPVNdvlEYQJao2iDhGczQiWl4rdH2s7k="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:hdwGdawDEcMTNFfQqCUbiM/GRA8=
Content-Language: en-US
In-Reply-To: <utq0os$ibqn$1@raubtier-asyl.eternal-september.org>

by: Chris M. Thomasson - Sun, 24 Mar 2024 20:05 UTC

On 3/24/2024 1:00 PM, Bonita Montero wrote:
> Am 24.03.2024 um 20:52 schrieb Chris M. Thomasson:
>> On 3/23/2024 11:30 PM, Bonita Montero wrote:
>>> Am 23.03.2024 um 22:04 schrieb Chris M. Thomasson:
>>>> On 3/23/2024 9:54 AM, Bonita Montero wrote:
>>>>> Am 23.03.2024 um 03:34 schrieb Chris M. Thomasson:
>>>>>> On 12/26/2023 9:06 PM, Bonita Montero wrote:
>>>>>>> Am 26.12.2023 um 21:24 schrieb Chris M. Thomasson:
>>>>>>>
>>>>>>>> So, are you familiar with Intel's early hyper threading problem?
>>>>>>>> There was false sharing between the ...
>>>>>>>
>>>>>>> False sharing can only happen between different cores.
>>>>>>
>>>>>> Sigh.
>>>>>
>>>>> Why ? Do you think false sharing can happen between the threads
>>>>> of a single core ?
>>>>>
>>>>
>>>> Sigh again...
>>>
>>> On a single core CPU with two thread's there's never false sharing.
>>>
>>
>> Whatever you say man... ;^o
>
> You said:
>
> > So, are you familiar with Intel's early hyper threading problem?
> There was false sharing between the hyperhtreads.
>
> False sharing is a kind of cache thrashing, but not every cache
> thrashing is false sharing. False sharing can only happen between
> different cores and the Pentium 4 HT does only have one core.
>

Yawn...

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<86wmosvyh0.fsf@linuxsc.com>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3652&group=comp.lang.c%2B%2B#3652

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17687@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)
Date: Sat, 20 Apr 2024 08:35:23 -0700
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <86wmosvyh0.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <86wmqtszd0.fsf@linuxsc.com> <urfk4u$1tar2$1@raubtier-asyl.eternal-september.org> <86r0ggr8xb.fsf@linuxsc.com> <usp6fv$72id$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 20 Apr 2024 17:35:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9997d8b7c87f6a9dee0ccc592fd139d0";
logging-data="3936409"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/pEOlpoN1+E2S97KZAlfjah9F498y23pk="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:QajQ6jFFlGvpETLvimDmfbTWXcE=
sha1:jq963DBlKip350uj341UZopaF3k=

by: Tim Rentsch - Sat, 20 Apr 2024 15:35 UTC

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

> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>
>> Sounds like you're using 1 bit per number, most of which are
>> wasted. If you use a different encoding the memory requirements
>> can be much smaller. How much memory do you have on the box?
>> If you have 64G you should be able to determine all primes
>> less than 1.5 trillion, using a simple encoding.
>
> I'm omitting even numbers and I handle the number two as a
> special case; that's the fastest solution.
>
>> I've mentioned this encoding before but let me give it again.
>> If numbers are considered mod 30, there are only 8 residues
>> that are not divisible by 2, 3, or 5. The 8 residues are
>> 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
>> hold all the information needed for 30 numbers, which means
>>
>> 1500000000000 / 30 = 50000000000
>>
>> which is to say 50 gigabytes should suffice.
>
> Show me the code.

Apparently you have missed the point.

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3654&group=comp.lang.c%2B%2B#3654

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.Montero@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to
the max)
Date: Sat, 20 Apr 2024 18:34:46 +0200
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<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>
<86wmqtszd0.fsf@linuxsc.com>
<urfk4u$1tar2$1@raubtier-asyl.eternal-september.org>
<86r0ggr8xb.fsf@linuxsc.com>
<usp6fv$72id$1@raubtier-asyl.eternal-september.org>
<86wmosvyh0.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 20 Apr 2024 18:34:47 +0200 (CEST)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="14d6ddb846e8593f63920489669f92c8";
logging-data="3960299"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX185LCxG3RwUWiWItVPc4vpikHHVKSDHoiI="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:xZxS0KeadpGvEeZwqWUjJvcwFvc=
In-Reply-To: <86wmosvyh0.fsf@linuxsc.com>
Content-Language: de-DE

by: Bonita Montero - Sat, 20 Apr 2024 16:34 UTC

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>>
>>> Sounds like you're using 1 bit per number, most of which are
>>> wasted. If you use a different encoding the memory requirements
>>> can be much smaller. How much memory do you have on the box?
>>> If you have 64G you should be able to determine all primes
>>> less than 1.5 trillion, using a simple encoding.
>>
>> I'm omitting even numbers and I handle the number two as a
>> special case; that's the fastest solution.
>>
>>> I've mentioned this encoding before but let me give it again.
>>> If numbers are considered mod 30, there are only 8 residues
>>> that are not divisible by 2, 3, or 5. The 8 residues are
>>> 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
>>> hold all the information needed for 30 numbers, which means
>>>
>>> 1500000000000 / 30 = 50000000000
>>>
>>> which is to say 50 gigabytes should suffice.
>>
>> Show me the code.
>
> Apparently you have missed the point.

I want to see the code for your idea.

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<v00qs0$3orfb$2@raubtier-asyl.eternal-september.org>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3655&group=comp.lang.c%2B%2B#3655

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.Montero@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to
the max)
Date: Sat, 20 Apr 2024 18:35:12 +0200
Organization: A noiseless patient Spider
Lines: 34
Message-ID: <v00qs0$3orfb$2@raubtier-asyl.eternal-september.org>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<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>
<86wmqtszd0.fsf@linuxsc.com>
<urfk4u$1tar2$1@raubtier-asyl.eternal-september.org>
<86r0ggr8xb.fsf@linuxsc.com>
<usp6fv$72id$1@raubtier-asyl.eternal-september.org>
<86wmosvyh0.fsf@linuxsc.com>
<v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 20 Apr 2024 18:35:13 +0200 (CEST)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="14d6ddb846e8593f63920489669f92c8";
logging-data="3960299"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+cqz7x8F5uAPHKNNHoFraKgx/Ur9xj43E="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:rgwr6lxz8qy0M4QdlabzJ0jW11M=
Content-Language: de-DE
In-Reply-To: <v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>

by: Bonita Montero - Sat, 20 Apr 2024 16:35 UTC

Am 20.04.2024 um 18:34 schrieb Bonita Montero:
> Am 20.04.2024 um 17:35 schrieb Tim Rentsch:
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>>>
>>>> Sounds like you're using 1 bit per number, most of which are
>>>> wasted. If you use a different encoding the memory requirements
>>>> can be much smaller. How much memory do you have on the box?
>>>> If you have 64G you should be able to determine all primes
>>>> less than 1.5 trillion, using a simple encoding.
>>>
>>> I'm omitting even numbers and I handle the number two as a
>>> special case; that's the fastest solution.
>>>
>>>> I've mentioned this encoding before but let me give it again.
>>>> If numbers are considered mod 30, there are only 8 residues
>>>> that are not divisible by 2, 3, or 5. The 8 residues are
>>>> 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
>>>> hold all the information needed for 30 numbers, which means
>>>>
>>>> 1500000000000 / 30 = 50000000000
>>>>
>>>> which is to say 50 gigabytes should suffice.
>>>
>>> Show me the code.
>>
>> Apparently you have missed the point.
>
> I want to see the code for your idea.
>

Eh, wij's idea ...

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<86o79ywofh.fsf@linuxsc.com>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3715&group=comp.lang.c%2B%2B#3715

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17687@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)
Date: Wed, 24 Apr 2024 12:28:18 -0700
Organization: A noiseless patient Spider
Lines: 14
Message-ID: <86o79ywofh.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <86wmqtszd0.fsf@linuxsc.com> <urfk4u$1tar2$1@raubtier-asyl.eternal-september.org> <86r0ggr8xb.fsf@linuxsc.com> <usp6fv$72id$1@raubtier-asyl.eternal-september.org> <86wmosvyh0.fsf@linuxsc.com> <v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 24 Apr 2024 21:28:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d0c198b2e081fbbcaac8aa6bee51e9fa";
logging-data="2634942"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX185K0+mqm38KaLPCnmzPoLvjQZLjpY8MBo="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:YP5f3rC2hsRGlybF7kcfCVmuVlY=
sha1:eVCuCc3MptXeX8TY7WumIKStB5Q=

by: Tim Rentsch - Wed, 24 Apr 2024 19:28 UTC

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

> Am 20.04.2024 um 17:35 schrieb Tim Rentsch:
>
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
[...]
>>> Show me the code.
>>
>> Apparently you have missed the point.
>
> I want to see the code for your idea.

Yes I already understood what you want. That is what
led me to conclude that you have missed the point.

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<v0clk4$2qdj9$1@raubtier-asyl.eternal-september.org>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3720&group=comp.lang.c%2B%2B#3720

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita.Montero@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to
the max)
Date: Thu, 25 Apr 2024 06:19:16 +0200
Organization: A noiseless patient Spider
Lines: 18
Message-ID: <v0clk4$2qdj9$1@raubtier-asyl.eternal-september.org>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
<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>
<86wmqtszd0.fsf@linuxsc.com>
<urfk4u$1tar2$1@raubtier-asyl.eternal-september.org>
<86r0ggr8xb.fsf@linuxsc.com>
<usp6fv$72id$1@raubtier-asyl.eternal-september.org>
<86wmosvyh0.fsf@linuxsc.com>
<v00qr6$3orfb$1@raubtier-asyl.eternal-september.org>
<86o79ywofh.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 25 Apr 2024 06:19:16 +0200 (CEST)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="5efc96809703662e44d9f4c6f0494446";
logging-data="2963049"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+f4VN5AsgN/NN3H1/A6g1w1Q24jCMb+Z4="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:0k7HDkdgDUJCdyGucdtPjFOlSz8=
In-Reply-To: <86o79ywofh.fsf@linuxsc.com>
Content-Language: de-DE

by: Bonita Montero - Thu, 25 Apr 2024 04:19 UTC

Am 24.04.2024 um 21:28 schrieb Tim Rentsch:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> Am 20.04.2024 um 17:35 schrieb Tim Rentsch:
>>
>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
> [...]
>>>> Show me the code.
>>>
>>> Apparently you have missed the point.
>>
>> I want to see the code for your idea.
>
> Yes I already understood what you want. That is what
> led me to conclude that you have missed the point.

I don't have "missed the point"; I just want to see the code
basing on the mentioned idea that is faster than my code.

Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

<867cglw3eb.fsf@linuxsc.com>

copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=3728&group=comp.lang.c%2B%2B#3728

copy link Newsgroups: comp.lang.c++

Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17687@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)
Date: Thu, 25 Apr 2024 14:14:52 -0700
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <867cglw3eb.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <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> <86wmqtszd0.fsf@linuxsc.com> <urfk4u$1tar2$1@raubtier-asyl.eternal-september.org> <86r0ggr8xb.fsf@linuxsc.com> <usp6fv$72id$1@raubtier-asyl.eternal-september.org> <86wmosvyh0.fsf@linuxsc.com> <v00qr6$3orfb$1@raubtier-asyl.eternal-september.org> <86o79ywofh.fsf@linuxsc.com> <v0clk4$2qdj9$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Thu, 25 Apr 2024 23:14:52 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="4d027413e75dd4b7b3c31e0f92925554";
logging-data="3382317"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/f/4VLjLHzosltZkgFRXoI68SfEFQEpkQ="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:7eE054oqhL6MNad/Po3hGD8aUo0=
sha1:fo17arr4hmKFPw+4Wfl2q1HxtEs=

by: Tim Rentsch - Thu, 25 Apr 2024 21:14 UTC

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

> Am 24.04.2024 um 21:28 schrieb Tim Rentsch:
>
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> Am 20.04.2024 um 17:35 schrieb Tim Rentsch:
>>>
>>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>> [...]
>>
>>>>> Show me the code.
>>>>
>>>> Apparently you have missed the point.
>>>
>>> I want to see the code for your idea.
>>
>> Yes I already understood what you want. That is what
>> led me to conclude that you have missed the point.
>
> I don't have "missed the point"; [...]

There is more than one school of thought on that question.

Subject	Author
Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	red floyd
Re: Sieve of Erastosthenes optimized to the max	Tim Rentsch
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Tim Rentsch
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Tim Rentsch
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Tim Rentsch
Re: Sieve of Erastosthenes optimized to the max	Vir Campestris
Re: Sieve of Erastosthenes optimized to the max	Tim Rentsch
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	David Brown
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	David Brown
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Scott Lurndal
Re: Sieve of Erastosthenes optimized to the max	David Brown
Re: Sieve of Erastosthenes optimized to the max	Scott Lurndal
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Scott Lurndal
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	red floyd
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	red floyd
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Kaz Kylheku
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Chris M. Thomasson
Re: Sieve of Erastosthenes optimized to the max	Bonita Montero
Re: Sieve of Erastosthenes optimized to the max	wij