Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Mr. Watson, come here, I want you." -- Alexander Graham Bell


devel / comp.lang.c++ / Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

SubjectAuthor
* Sieve of Erastosthenes optimized to the maxBonita Montero
+* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
| `* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  +* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|  |`* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  | +* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  | |`- Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  | `* Re: Sieve of Erastosthenes optimized to the maxred floyd
|  |  `* Re: Sieve of Erastosthenes optimized to the maxTim Rentsch
|  |   `* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  |    `* Re: Sieve of Erastosthenes optimized to the maxTim Rentsch
|  |     `* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|  |      `- Re: Sieve of Erastosthenes optimized to the maxTim Rentsch
|  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|   `* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|    +- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|    +- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|    `* Re: Sieve of Erastosthenes optimized to the maxTim Rentsch
|     `* Re: Sieve of Erastosthenes optimized to the maxVir Campestris
|      `- Re: Sieve of Erastosthenes optimized to the maxTim Rentsch
+* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
| `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|   `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|    `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|     `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|      `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|       `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|        `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|         `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          +* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |`* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          | `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |   `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |    `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |     `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |      `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       +* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | +* Re: Sieve of Erastosthenes optimized to the maxDavid Brown
|          |       | |`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | | `* Re: Sieve of Erastosthenes optimized to the maxDavid Brown
|          |       | |  +- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  `* Re: Sieve of Erastosthenes optimized to the maxScott Lurndal
|          |       | |   `- Re: Sieve of Erastosthenes optimized to the maxDavid Brown
|          |       | +* Re: Sieve of Erastosthenes optimized to the maxScott Lurndal
|          |       | |+* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | ||`- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | |`* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | | `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | |  +* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |+- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | |  |`* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  | `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |  +* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  |  |`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |  | `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  |  |  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |  |   `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  |  |    `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |  |     `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  |  |      `- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |  `* Re: Sieve of Erastosthenes optimized to the maxScott Lurndal
|          |       | |  |   `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |    `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |  |     `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       | |  |      `- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | |  `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       | |   `- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       | `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       |  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |   `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |    +* Re: Sieve of Erastosthenes optimized to the maxred floyd
|          |       |    |`- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |    `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     +* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |`* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     | `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |  `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |   `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |    `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |     `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |      `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |       `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |        `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |         `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |          `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |           `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       |     |            `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |             `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |              +* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |              |`- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |              `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |               `* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |                `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |                 +* Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |                 |`* Re: Sieve of Erastosthenes optimized to the maxred floyd
|          |       |     |                 | +- Re: Sieve of Erastosthenes optimized to the maxBonita Montero
|          |       |     |                 | `- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       |     |                 `* Re: Sieve of Erastosthenes optimized to the maxKaz Kylheku
|          |       |     `- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          |       `- Re: Sieve of Erastosthenes optimized to the maxChris M. Thomasson
|          `* Re: Sieve of Erastosthenes optimized to the maxBonita Montero
`* Re: Sieve of Erastosthenes optimized to the maxwij

Pages:123456
Re: Sieve of Erastosthenes optimized to the max

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

  copy mid

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

  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....@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.novabbs.com/devel/article-flat.php?id=3376&group=comp.lang.c%2B%2B#3376

  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.M...@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.novabbs.com/devel/article-flat.php?id=3377&group=comp.lang.c%2B%2B#3377

  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....@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.novabbs.com/devel/article-flat.php?id=3645&group=comp.lang.c%2B%2B#3645

  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.17...@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.novabbs.com/devel/article-flat.php?id=3647&group=comp.lang.c%2B%2B#3647

  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.M...@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.novabbs.com/devel/article-flat.php?id=3648&group=comp.lang.c%2B%2B#3648

  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.M...@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.novabbs.com/devel/article-flat.php?id=3708&group=comp.lang.c%2B%2B#3708

  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.17...@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.novabbs.com/devel/article-flat.php?id=3713&group=comp.lang.c%2B%2B#3713

  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.M...@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.novabbs.com/devel/article-flat.php?id=3721&group=comp.lang.c%2B%2B#3721

  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.17...@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.

Re: Sieve of Erastosthenes optimized to the max

<v25c87$1ld9m$1@dont-email.me>

  copy mid

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

  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: vir.camp...@invalid.invalid (Vir Campestris)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Thu, 16 May 2024 17:28:55 +0100
Organization: A noiseless patient Spider
Lines: 45
Message-ID: <v25c87$1ld9m$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>
<utq11p$icmm$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 16 May 2024 18:28:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e247cced23bd79bee244615b2c82aa02";
logging-data="1750326"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/FfzZLm1t4DBTabscRlfHA3nQ0/4uZuKk="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:f+qrgUZjUYqGFbItgS8UEKDShhc=
Content-Language: en-GB
In-Reply-To: <utq11p$icmm$1@dont-email.me>
 by: Vir Campestris - Thu, 16 May 2024 16:28 UTC

I've been playing with this. Has it really been this long? I ought to
have more time than this...

I put together some code, and have been playing with it far too much.

Bonita, I don't know whether to curse you or kiss you. (Though in fact I
suspect you may be a little young for me. Possibly too young for my kids...)

I haven't written any code just for fun in years. Maybe decades!

I missed Tim's Mod 30 trick, and that might well help. But I think I'm
bored with this. It would save a lot of memory, but the extra
computation might make it slower. Maybe I'll try one day ;)

My code isn't as fast as Bonita's code. Even allowing that I didn't put
any threads in there.

But...

When I compared the output there were differences. Specifically your
program claimed that these numbers

66049,67591,69133,69647,71189,72217,72731,75301,78899,79927,80441,81469,85067,86609,89179,
89693,90721,92263,94319,95861,97403,98431,99973,102029,103057,105113,107683,108197,110767,
111281,112823,113851,115393,117449,118477,118991,120019,123103,125159,126187,128243,129271,
130813,133897,134411,139037,140579,143149,144691,146233,146747,148289,150859,152401,153943,
154457,155999,157541,158569,159083,162167,164737,165251,166279,167821,169363,169877,172961,
173989,175531,177587,180157,182213,184783,186839,188381,189923,190951,193007,194549,195577,
197633,198661,202259,204829,207913,208427,210997,211511,212539,213053,215623,219221,220249,
220763,221791,225389,226417,226931,227959,233099,234127,236183,238753,240809,241837,243379,
244921,248519,249547,251089,252631,254687,256229,259313,260341,261883,262397,264967,265481,
267023,269593,270107,272677,273191,274733,279359,280387,280901,281929,283471,285013,287069,
288611,290153,295807,296321,298891,300947,303517,305059,306601,308657,311741,312769,314311,
315853

are all prime. They aren't. The first one is 257 squared, and the others
all have factors too.

I'd also suggest that you comment demonstration code. It's intended to
show off fancy techniques, and they aren't obvious without explanation.

I learned that lesson when I was a student, when I couldn't understand
something I'd written myself!

Andy

Re: Sieve of Erastosthenes optimized to the max

<87ttixij8d.fsf@bsb.me.uk>

  copy mid

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

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: ben...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Thu, 16 May 2024 21:40:02 +0100
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <87ttixij8d.fsf@bsb.me.uk>
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>
<utq11p$icmm$1@dont-email.me> <v25c87$1ld9m$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Thu, 16 May 2024 22:40:05 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a150a953876bd0c8902d2829177285a5";
logging-data="1856267"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+TvsYeix/q0sEEnWgIemzN5tCVb+SyU7M="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:YPaLbIhWlUOKrPGPQJYYjL9J+1c=
sha1:WHfmANlNObtIa9n0VjQw8puY4PQ=
 by: Ben Bacarisse - Thu, 16 May 2024 20:40 UTC

Vir Campestris <vir.campestris@invalid.invalid> writes:
....
> When I compared the output there were differences. Specifically your
> program claimed that these numbers
>
> 66049,67591,69133,69647,71189,72217,72731,75301,78899,79927,80441,81469,85067,86609,89179,
> 89693,90721,92263,94319,95861,97403,98431,99973,102029,103057,105113,107683,108197,110767,
> 111281,112823,113851,115393,117449,118477,118991,120019,123103,125159,126187,128243,129271,
> 130813,133897,134411,139037,140579,143149,144691,146233,146747,148289,150859,152401,153943,
> 154457,155999,157541,158569,159083,162167,164737,165251,166279,167821,169363,169877,172961,
> 173989,175531,177587,180157,182213,184783,186839,188381,189923,190951,193007,194549,195577,
> 197633,198661,202259,204829,207913,208427,210997,211511,212539,213053,215623,219221,220249,
> 220763,221791,225389,226417,226931,227959,233099,234127,236183,238753,240809,241837,243379,
> 244921,248519,249547,251089,252631,254687,256229,259313,260341,261883,262397,264967,265481,
> 267023,269593,270107,272677,273191,274733,279359,280387,280901,281929,283471,285013,287069,
> 288611,290153,295807,296321,298891,300947,303517,305059,306601,308657,311741,312769,314311,
> 315853
>
> are all prime. They aren't. The first one is 257 squared, and the others
> all have factors too.

In fact they are /all/ 257 times some prime. That must be a big clue as
to where the bug is...

--
Ben.

Re: Sieve of Erastosthenes optimized to the max

<86r0duwqgg.fsf@linuxsc.com>

  copy mid

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

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!rocksolid2!news.neodome.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17...@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Tue, 21 May 2024 19:06:07 -0700
Organization: A noiseless patient Spider
Lines: 23
Message-ID: <86r0duwqgg.fsf@linuxsc.com>
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> <utq11p$icmm$1@dont-email.me> <v25c87$1ld9m$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 22 May 2024 04:06:09 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ef527a1f0ace8b0bcb46bd1e68f4f6ae";
logging-data="1042967"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/OVfKCw9pLdZWtJ8A2c5h5tu8VizIRbU4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:1sqEPJFI8gZU/OWVOL/nO6zybjI=
sha1:8S64xP4DIV0CPcGhbdUsQoGm/c8=
 by: Tim Rentsch - Wed, 22 May 2024 02:06 UTC

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

> I've been playing with this. Has it really been this long? I
> ought to have more time than this... [...]
>
> I missed Tim's Mod 30 trick, and that might well help. But I
> think I'm bored with this. It would save a lot of memory, but
> the extra computation might make it slower.

Two comments. Using the mod 30 encoding can be speed competitive
with simpler encodings. The second comment is, it isn't just
that less memory is used, but that more primes can be found.
Bonita brags about how fast some code is, but it's an apples
and oranges comparison - that code doesn't do the job because
it runs into a memory limit way sooner than using a mod 30
encoding, and trying to run past that limit would make the
code R E A L L Y S L O W.

> Maybe I'll try one day ;)

I hope you do. If you have some difficulty seeing how to
avoid the seeming speed penalties, feel free to ask, I am
happy to help.


devel / comp.lang.c++ / Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)

Pages:123456
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor