Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #91263 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2023-08-16 15:37 +0200 |
| Last post | 2023-08-30 19:02 +0200 |
| Articles | 20 on this page of 146 — 13 participants |
Back to article view | Back to comp.lang.c++
Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-16 15:37 +0200
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 10:57 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-16 20:21 +0200
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 12:17 -0700
Re: Sieve of Eratosthenes Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-16 21:44 +0300
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 12:09 -0700
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:17 +0200
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:21 +0200
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:39 +0200
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:59 +0200
Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-16 16:27 -0700
Re: Sieve of Eratosthenes red floyd <no.spam.here@its.invalid> - 2023-08-16 18:06 -0700
Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-16 19:26 -0700
Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-27 12:26 -0700
Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 00:49 +0100
Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-27 23:23 -0700
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-28 15:53 +0200
Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-28 09:03 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 18:47 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 13:01 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-30 15:38 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 18:31 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 08:22 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 11:00 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:23 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:28 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 11:52 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:22 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:32 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:44 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:50 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 10:26 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 12:59 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 12:30 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 15:33 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 13:49 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 15:59 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 14:03 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 16:15 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 14:39 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 16:59 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 15:01 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 17:05 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 15:08 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 17:15 +0200
Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-31 21:33 +0100
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 05:35 +0200
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 14:43 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 16:57 +0200
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 16:10 +0000
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:25 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:33 +0200
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 16:12 +0000
Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 23:08 +0100
Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-28 15:15 -0700
Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 23:41 +0100
Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-30 17:45 -0700
Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-31 03:18 +0100
Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-28 15:08 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 08:42 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 11:38 +0200
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-17 12:50 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 13:10 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 17:47 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 11:00 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 17:19 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 19:50 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 18:12 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 20:22 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 19:01 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 05:27 +0200
Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-21 23:25 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:23 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:59 +0200
Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-22 05:15 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 14:23 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 06:56 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:27 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:34 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:13 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 16:17 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:27 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 16:48 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:57 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 17:00 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 17:56 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 20:13 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 18:18 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 20:50 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 06:51 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 09:59 +0200
Re: Sieve of Eratosthenes Richard Damon <Richard@Damon-Family.org> - 2023-08-23 07:52 -0400
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 14:40 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:24 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:30 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:36 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:38 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:43 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:45 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 17:49 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:05 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:18 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:20 +0200
Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 11:13 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:17 +0200
Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-23 11:20 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:24 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:25 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:29 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:40 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:49 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:07 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 18:10 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:15 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 18:18 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-26 08:03 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 10:16 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-26 08:27 +0000
Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 11:37 -0700
Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-26 15:33 -0700
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:20 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:32 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:41 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:47 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 17:51 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:09 +0200
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-23 18:51 +0000
Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-24 11:25 -0700
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:22 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:27 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:37 +0000
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:52 +0200
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:07 +0000
Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 08:00 -0700
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-22 15:49 +0000
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 17:58 +0000
Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-22 18:24 +0000
Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 06:50 +0000
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-17 13:43 -0700
Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-18 02:00 +0200
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-18 05:01 -0700
Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-18 17:02 -0700
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 06:15 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 09:43 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-29 20:34 +0200
Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 19:02 +0200
Page 4 of 8 — ← Prev page 1 2 3 [4] 5 6 7 8 Next page →
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-17 11:38 +0200 |
| Message-ID | <ubkpqj$3nra0$1@dont-email.me> |
| In reply to | #91284 |
Am 17.08.2023 um 08:42 schrieb Bonita Montero:
> Am 17.08.2023 um 03:06 schrieb red floyd:
>
>> Here's mine. I get rid of the vector<bool> by storing the prime factors
>> in their own vector, and only checking for divisibility by primes.
>
> If I modify my code to use the same, called Euler's sieve, my code
> becomes 19 times slower on my 7950X with an upper bound of 1E6.
>
This is the code:
#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
using namespace std;
int main( int argc, char **argv )
{
constexpr bool USE_BOOL = true;
constexpr size_t BUF_SIZE = 0x100000;
try
{
size_t max;
if( argc < 2 )
return EXIT_FAILURE;
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen(
sizeStr ), max, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
vector<size_t> primes;
for( size_t p = 2; p < max; ++p )
{
bool has = false;
for( size_t soFar : primes )
if( !(p % soFar) )
{
has = true;
break;
}
if( !has )
primes.emplace_back( p );
}
if( argc >= 3 && !*argv[2] )
return EXIT_SUCCESS;
ofstream ofs;
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
union ndi_t { }; // non-default-initialzied
vector<ndi_t> buf;
buf.resize( BUF_SIZE + 32 );
char
*bufBegin = (char *)buf.data(),
*bufEnd = bufBegin,
*const bufFlush = bufBegin + BUF_SIZE;
for( size_t p : primes )
{
to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, p );
bufEnd = tcr.ptr;
*bufEnd++ = '\n';
if( bufEnd >= bufFlush )
ofs << string_view( bufBegin, bufEnd ),
bufEnd = bufBegin;
}
ofs << string_view( bufBegin, bufEnd );
}
catch( bad_alloc const & )
{
cout << "out of memory" << endl;
}
catch( ios_base::failure const & )
{
cout << "I/O error" << endl;
}
}
I tried that with an upper bound of 1E8 and after 2,5 hours of computing
I stopped the process. With my primary code the process ends after 0.4s.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2023-08-17 12:50 +0200 |
| Message-ID | <ubku1s$3oe7t$1@dont-email.me> |
| In reply to | #91285 |
On 2023-08-17 11:38 AM, Bonita Montero wrote:
> Am 17.08.2023 um 08:42 schrieb Bonita Montero:
>> Am 17.08.2023 um 03:06 schrieb red floyd:
>>
>>> Here's mine. I get rid of the vector<bool> by storing the prime factors
>>> in their own vector, and only checking for divisibility by primes.
>>
>> If I modify my code to use the same, called Euler's sieve, my code
>> becomes 19 times slower on my 7950X with an upper bound of 1E6.
>>
>
> This is the code:
[snip]
> vector<size_t> primes;
> for( size_t p = 2; p < max; ++p )
> {
> bool has = false;
> for( size_t soFar : primes )
> if( !(p % soFar) )
> {
> has = true;
> break;
> }
> if( !has )
> primes.emplace_back( p );
> }
[snip]
> I tried that with an upper bound of 1E8 and after 2,5 hours of computing
> I stopped the process. With my primary code the process ends after 0.4s.
One less unreasonable way to check against already computed primes is to
generate and update the smallest multiple of each already known prime,
that is larger than the current number to be checked.
It reduces the complexity for each number check to roughly logarithmic
in the number of primes so far, instead of linear. And in total roughly
O(n log n) instead of O(n^2). Quadratic is just impractical, as you found.
Code for the collection-of-smallest-multiples approach:
#include <fmt/core.h>
#include "cppm-Timer.hpp"
#include <queue>
#include <vector>
using std::priority_queue,
std::vector;
#include <stdio.h> // fopen, fclose
template< class Item, class Compare_func >
using Priority_q = priority_queue<Item, std::vector<Item>,
Compare_func>;
struct Multiple
{
int base; int n;
auto value() const -> int{ return n*base; }
};
struct Descending_order
{
auto operator()( const Multiple& a, const Multiple& b ) const
-> bool
{ return a.value() > b.value(); } // Note: direction of
comparison.
};
auto main() -> int
{
constexpr int n = 10'000'000;
cppm::Timer timer;
auto primes = vector<int>();
primes.reserve( n/2 );
const auto produce = [&]( const int prime ) { primes.push_back(
prime ); };
produce( 2 );
auto larger_composites = Priority_q<Multiple, Descending_order>();
larger_composites.push( Multiple{2, 2} );
for( int current = 3; current < n; ++current ) {
bool is_composite = false;
for( ;; ) {
const Multiple next_composite = larger_composites.top();
if( current < next_composite.value() ) {
break;
}
larger_composites.pop();
is_composite = true;
larger_composites.push( Multiple{next_composite.base, 1
+ next_composite.n} );
}
if( not is_composite ) {
produce( current );
larger_composites.push( Multiple{current, 2} );
}
}
timer.stop();
fmt::print( "{} seconds.\n", timer.seconds() );
auto f = fopen( "primes.alf-gen.txt", "w" );
if( not f ) { return EXIT_FAILURE; }
for( const int prime: primes ) { fmt::print( f, "{:d}\n", prime
); }
fclose( f );
}
It runs roughly 100 times slower than the unslowest of the earlier
programs I posted in this thread, using 3.5736102 seconds to produce the
primes up to 10'000'000, but I believe still much faster than the
quadratic time code you showed (I would guess maybe 400 seconds = 6'40
minutes for the 1 billion case?), and has the possible advantage that
one doesn't need to know in advance a cap on the prime size.
It can just run and run, gobbling up memory as it goes.
- Alf
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-17 13:10 +0200 |
| Message-ID | <ubkv6h$3oivg$1@dont-email.me> |
| In reply to | #91286 |
Am 17.08.2023 um 12:50 schrieb Alf P. Steinbach: > One less unreasonable way to check against already computed primes is to > generate and update the smallest multiple of each already known prime, > that is larger than the current number to be checked. Beginning with the smaller primes aldready seen does make sense since you can filter the values earlier. F.e. there are more values which are a multiple of two than a multiple of 11.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-17 17:47 +0200 |
| Message-ID | <ublfe8$3qtkn$1@dont-email.me> |
| In reply to | #91286 |
I did it the same way with some simpler code:
#include <iostream>
#include <queue>
#include <vector>
#include <charconv>
#include <fstream>
using namespace std;
int main( int argc, char **argv )
{
constexpr size_t BUF_SIZE = 0x100000;
size_t max;
if( argc < 2 )
return EXIT_FAILURE;
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen(
sizeStr ), max, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
struct next_multiple { size_t p, pNext; };
auto nm_less = []( next_multiple const &left, next_multiple const
&right ) { return left.pNext > right.pNext; };
priority_queue<next_multiple, vector<next_multiple>, decltype(nm_less)>
nextMultiples( nm_less );
nextMultiples.emplace( 2, 4 );
auto *hitOrNot = &nextMultiples.top();
for( size_t p = 3; p <= max; ++p )
{
if( p < hitOrNot->pNext ) [[unlikely]]
{
nextMultiples.emplace( p, p + p );
hitOrNot = &nextMultiples.top();
continue;
}
do
{
auto nextIncr = *hitOrNot;
nextMultiples.pop();
nextIncr.pNext += nextIncr.p;
nextMultiples.emplace( nextIncr );
hitOrNot = &nextMultiples.top();
} while( p == hitOrNot->pNext );
}
vector<size_t> primes;
primes.reserve( nextMultiples.size() );
while( !nextMultiples.empty() )
{
auto const next = nextMultiples.top();
primes.emplace_back( next.p );
nextMultiples.pop();
}
sort( primes.begin(), primes.end() );
if( argc >= 3 && !*argv[2] )
return EXIT_FAILURE;
ofstream ofs;
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
union ndi_t { }; // non-default-initialzied
vector<ndi_t> buf( BUF_SIZE + 32 );
char
*bufBegin = (char*)buf.data(),
*bufEnd = bufBegin,
*bufFlush = bufBegin + BUF_SIZE;
for( size_t p : primes )
{
to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, p );
bufEnd = tcr.ptr;
*bufEnd++ = '\n';
if( bufEnd >= bufFlush )
ofs << string_view( bufBegin, bufEnd ),
bufEnd = bufBegin;
}
ofs << string_view( bufBegin, bufEnd );
}
If I print all primes <= 1E8 that's still 82 times slower than my
initial solution.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-21 11:00 +0200 |
| Message-ID | <ubv92t$1r3l9$1@dont-email.me> |
| In reply to | #91286 |
I tried to combine the bitmap-approach with the heap-approach,
having a bitmap that fits into the cache and which is a window
inside the rows of numbers.
#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
#include <queue>
#if defined(_MSC_VER)
#pragma warning(disable: 26495) // uninitialized member
#endif
using namespace std;
int main( int argc, char **argv )
{
try
{
constexpr size_t
BITMAP_SIZE = 0x80000,
BITS = BITMAP_SIZE * 8;
size_t max;
if( argc < 2 )
return EXIT_FAILURE;
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen(
sizeStr ), max, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
union ndi_t { uint8_t c; ndi_t() {} };
vector<ndi_t> bitmap( BITMAP_SIZE );
struct next_multiple { size_t p, pNext; };
auto nm_less = []( next_multiple const &left, next_multiple const
&right ) { return left.pNext > right.pNext; };
priority_queue<next_multiple, vector<next_multiple>, decltype(nm_less)>
multiples( nm_less );
for( size_t w = 2; w <= max; w += BITS )
{
for_each( bitmap.begin(), bitmap.end(), [&]( ndi_t &n ) { n.c = 0xFF;
} );
size_t wEnd = w + BITS <= max ? w + BITS : max;
auto clearInterval = [&]( next_multiple &nm )
{
size_t b = nm.pNext - w;
for( ; b < wEnd - w; b += nm.p )
bitmap[b / 8].c &= ~(1u << b % 8);
nm.pNext = w + b;
};
if( multiples.size() ) [[likely]]
for( next_multiple const *pNm; (pNm = &multiples.top())->pNext < wEnd; )
{
auto nm = *pNm;
multiples.pop();
clearInterval( nm );
multiples.push( nm );
}
for( size_t b = 0, e = wEnd - w; b != e; ++b )
if( bitmap[b / 8].c >> b % 8 & 1 )
{
next_multiple nm { w + b, 2 * (w + b) };
clearInterval( nm );
multiples.push( nm );
}
}
/*while (multiples.size())
cout << multiples.top().p << endl,
multiples.pop();*/
}
catch( bad_alloc const & )
{
cout << "out of memory" << endl;
}
}
This is faster than the pure heap approach but still not as fast
as the pure bitmap approach.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2023-08-21 17:19 +0000 |
| Message-ID | <uc06bc$203p7$1@dont-email.me> |
| In reply to | #91320 |
On Mon, 21 Aug 2023 11:00:15 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
>I tried to combine the bitmap-approach with the heap-approach,
>having a bitmap that fits into the cache and which is a window
>inside the rows of numbers.
If only erastothenes had had C++20 he too could have come up with some
hopeless complicated solution no one understood. Or maybe he would have
done some simple baby code in C...
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <math.h>
int main(int argc, char **argv)
{
char *primes;
int num;
int sqr;
int i;
int j;
if (argc != 2 || (num = atoi(argv[1])) < 1)
{
printf("Usage: %s <max number>\n",argv[0]);
return 1;
}
primes = (char *)malloc(num);
bzero(primes,num);
sqr = (int)ceil(sqrt(num));
for(i=3;i <= sqr;i+=2)
{
if (!primes[i])
{
for(j=i*2;j <= num;j+=i) primes[j] = 1;
}
}
for(i=1;i <= num;i+=2)
{
if (!primes[i])
{
printf("%d\n",i);
if (i == 1) puts("2");
}
}
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-21 19:50 +0200 |
| Message-ID | <uc0857$20cmk$1@dont-email.me> |
| In reply to | #91321 |
Am 21.08.2023 um 19:19 schrieb Muttley@dastardlyhq.com:
> On Mon, 21 Aug 2023 11:00:15 +0200
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I tried to combine the bitmap-approach with the heap-approach,
>> having a bitmap that fits into the cache and which is a window
>> inside the rows of numbers.
>
> If only erastothenes had had C++20 he too could have come up with some
> hopeless complicated solution no one understood. Or maybe he would have
> done some simple baby code in C...
On my PC printing the all primes below 1E8 takes 0.827s with your
code. With my code it takes about 0.36s. Take this as a reference:
#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
#if defined(_MSC_VER)
#pragma warning(disable: 26495) // uninitialized member
#endif
using namespace std;
int main( int argc, char **argv )
{
constexpr size_t BUF_SIZE = 0x100000;
try
{
size_t max;
if( argc < 2 )
return EXIT_FAILURE;
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen(
sizeStr ), max, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
vector<uint8_t> sieve( (max + 1 + 7) / 8, (uint8_t)-1 );
ofstream ofs;
union ndi_t { char c; ndi_t() {} }; // non-default-initialzied
using ndi_vec = vector<ndi_t>;
using ndi_vec_it = ndi_vec::iterator;
constexpr size_t AHEAD = 32;
ndi_vec printBuf;
ndi_vec_it bufBegin, bufEnd, bufFlush;
if( argc < 3 || *argv[2] )
{
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
printBuf.resize( BUF_SIZE + AHEAD - 1 );
bufBegin = printBuf.begin();
bufEnd = bufBegin;
bufFlush = bufBegin + BUF_SIZE;
}
auto print = [&]() { ofs << string_view( &bufBegin->c, &bufEnd->c ); };
for( size_t p = 2; p <= max; )
{
for( size_t m = 2 * p; m <= max; m += p )
sieve[m / 8] &= ~(1u << m % 8);
while( ++p <= max && !(1 & sieve[p / 8] >> p % 8) );
if( !ofs.is_open() )
continue;
to_chars_result tcr = to_chars( &bufEnd->c, &to_address( bufEnd +
(AHEAD - 1) )->c, p );
bufEnd = tcr.ptr - &bufBegin->c + bufBegin; // NOP
bufEnd++->c = '\n';
if( bufEnd >= bufFlush )
print(),
bufEnd = bufBegin;
}
print();
return EXIT_SUCCESS;
}
catch( bad_alloc const & )
{
cout << "out of memory" << endl;
}
catch( ios_base::failure const & )
{
cout << "I/O error" << endl;
}
}
The complexity is all because of speed. Using a byte-array is much
slower and using C-streams is also slow. I'm using a bit-array and
I'm using my own output buffering.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2023-08-21 18:12 +0000 |
| Message-ID | <uc09e1$20jj6$1@dont-email.me> |
| In reply to | #91322 |
On Mon, 21 Aug 2023 19:50:32 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: >Am 21.08.2023 um 19:19 schrieb Muttley@dastardlyhq.com: >> On Mon, 21 Aug 2023 11:00:15 +0200 >> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>> I tried to combine the bitmap-approach with the heap-approach, >>> having a bitmap that fits into the cache and which is a window >>> inside the rows of numbers. >> >> If only erastothenes had had C++20 he too could have come up with some >> hopeless complicated solution no one understood. Or maybe he would have >> done some simple baby code in C... > >On my PC printing the all primes below 1E8 takes 0.827s with your >code. With my code it takes about 0.36s. I'm fairly sure I could speed it up if I could be bothered. >Take this as a reference: Sorry, can't be bothered to wade through that mess.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-21 20:22 +0200 |
| Message-ID | <uc0a19$20m3n$1@dont-email.me> |
| In reply to | #91323 |
Am 21.08.2023 um 20:12 schrieb Muttley@dastardlyhq.com: > On Mon, 21 Aug 2023 19:50:32 +0200 > Bonita Montero <Bonita.Montero@gmail.com> wrote: >> On my PC printing the all primes below 1E8 takes 0.827s with your >> code. With my code it takes about 0.36s. > I'm fairly sure I could speed it up if I could be bothered. For sure not. >> Take this as a reference: > Sorry, can't be bothered to wade through that mess. It's a mess because you're overburdened with reading the code.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2023-08-21 19:01 +0000 |
| Message-ID | <uc0ca1$213lo$1@dont-email.me> |
| In reply to | #91324 |
On Mon, 21 Aug 2023 20:22:36 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: >Am 21.08.2023 um 20:12 schrieb Muttley@dastardlyhq.com: > >> On Mon, 21 Aug 2023 19:50:32 +0200 >> Bonita Montero <Bonita.Montero@gmail.com> wrote: > >>> On my PC printing the all primes below 1E8 takes 0.827s with your >>> code. With my code it takes about 0.36s. > >> I'm fairly sure I could speed it up if I could be bothered. > >For sure not. And why's that then? Give us your insight. > >>> Take this as a reference: > >> Sorry, can't be bothered to wade through that mess. > >It's a mess because you're overburdened with reading the code. A mess is burdensome.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 05:27 +0200 |
| Message-ID | <uc19v6$28t5s$1@dont-email.me> |
| In reply to | #91325 |
Am 21.08.2023 um 21:01 schrieb Muttley@dastardlyhq.com: > On Mon, 21 Aug 2023 20:22:36 +0200 > Bonita Montero <Bonita.Montero@gmail.com> wrote: >> Am 21.08.2023 um 20:12 schrieb Muttley@dastardlyhq.com: >> >>> On Mon, 21 Aug 2023 19:50:32 +0200 >>> Bonita Montero <Bonita.Montero@gmail.com> wrote: >> >>>> On my PC printing the all primes below 1E8 takes 0.827s with your >>>> code. With my code it takes about 0.36s. >> >>> I'm fairly sure I could speed it up if I could be bothered. >> >> For sure not. > > And why's that then? ... Because you can only write simple code. > >> >>>> Take this as a reference: >> >>> Sorry, can't be bothered to wade through that mess. >> >> It's a mess because you're overburdened with reading the code. > > A mess is burdensome. > >
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2023-08-21 23:25 -0700 |
| Message-ID | <64246adc-0285-4d62-9280-b301c77dfb24n@googlegroups.com> |
| In reply to | #91329 |
On Tuesday, 22 August 2023 at 06:27:51 UTC+3, Bonita Montero wrote: > Am 21.08.2023 um 21:01 schrieb Mut...@dastardlyhq.com: > > On Mon, 21 Aug 2023 20:22:36 +0200 > > Bonita Montero <Bonita....@gmail.com> wrote: > >> Am 21.08.2023 um 20:12 schrieb Mut...@dastardlyhq.com: > >> > >>> On Mon, 21 Aug 2023 19:50:32 +0200 > >>> Bonita Montero <Bonita....@gmail.com> wrote: > >> > >>>> On my PC printing the all primes below 1E8 takes 0.827s with your > >>>> code. With my code it takes about 0.36s. > >> > >>> I'm fairly sure I could speed it up if I could be bothered. > >> > >> For sure not. > > > > And why's that then? ... > > Because you can only write simple code. Do not hijack nice thread of finding primes with your optimising textual output. Store primes however you want to and do not time text streaming whatsoever. The problem was to find primes.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 11:23 +0200 |
| Message-ID | <uc1uqm$2brns$1@dont-email.me> |
| In reply to | #91334 |
Am 22.08.2023 um 08:25 schrieb Öö Tiib: > On Tuesday, 22 August 2023 at 06:27:51 UTC+3, Bonita Montero wrote: >> Am 21.08.2023 um 21:01 schrieb Mut...@dastardlyhq.com: >>> On Mon, 21 Aug 2023 20:22:36 +0200 >>> Bonita Montero <Bonita....@gmail.com> wrote: >>>> Am 21.08.2023 um 20:12 schrieb Mut...@dastardlyhq.com: >>>> >>>>> On Mon, 21 Aug 2023 19:50:32 +0200 >>>>> Bonita Montero <Bonita....@gmail.com> wrote: >>>> >>>>>> On my PC printing the all primes below 1E8 takes 0.827s with your >>>>>> code. With my code it takes about 0.36s. >>>> >>>>> I'm fairly sure I could speed it up if I could be bothered. >>>> >>>> For sure not. >>> >>> And why's that then? ... >> >> Because you can only write simple code. > > Do not hijack nice thread of finding primes with your optimising > textual output. The speedup over cout << p << endl is massive, at least with MSVC; I've measured that, you didn't.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 11:59 +0200 |
| Message-ID | <uc20tm$2c4rd$1@dont-email.me> |
| In reply to | #91336 |
Am 22.08.2023 um 11:23 schrieb Bonita Montero: > Am 22.08.2023 um 08:25 schrieb Öö Tiib: >> On Tuesday, 22 August 2023 at 06:27:51 UTC+3, Bonita Montero wrote: >>> Am 21.08.2023 um 21:01 schrieb Mut...@dastardlyhq.com: >>>> On Mon, 21 Aug 2023 20:22:36 +0200 >>>> Bonita Montero <Bonita....@gmail.com> wrote: >>>>> Am 21.08.2023 um 20:12 schrieb Mut...@dastardlyhq.com: >>>>> >>>>>> On Mon, 21 Aug 2023 19:50:32 +0200 >>>>>> Bonita Montero <Bonita....@gmail.com> wrote: >>>>> >>>>>>> On my PC printing the all primes below 1E8 takes 0.827s with your >>>>>>> code. With my code it takes about 0.36s. >>>>> >>>>>> I'm fairly sure I could speed it up if I could be bothered. >>>>> >>>>> For sure not. >>>> >>>> And why's that then? ... >>> >>> Because you can only write simple code. >> >> Do not hijack nice thread of finding primes with your optimising >> textual output. > > The speedup over cout << p << endl is massive, at least with MSVC; > I've measured that, you didn't. > C:\Users\Boni\Documents\Source\bitmapSieve>bg --times --affinity 1 --high x64\Release\bitmapSieve 100000000 real 9675.36ms user 2875.00ms sys 6718.75ms cycles 43.369.468.839 C:\Users\Boni\Documents\Source\bitmapSieve>bg --times --affinity 1 --high x64\Release\bitmapSieve 100000000 real 370.28ms user 281.25ms sys 62.50ms cycles 1.653.010.785 26 times faster on Windows (Zen4): boni@EliteDesk:~$ g++ -march=native -std=c++20 -O2 bitmapSieve.cpp boni@EliteDesk:~$ time ./a.out 100000000 real 0m17,552s user 0m5,406s sys 0m12,113s boni@EliteDesk:~$ g++ -march=native -std=c++20 -O2 bitmapSieve.cpp boni@EliteDesk:~$ time ./a.out 100000000 real 0m1,808s user 0m1,680s sys 0m0,085s 9.7 times faster on Linux (Skylake).
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2023-08-22 05:15 -0700 |
| Message-ID | <e391d277-849c-4089-9ff5-6c2b9aa240b7n@googlegroups.com> |
| In reply to | #91336 |
On Tuesday, 22 August 2023 at 12:23:53 UTC+3, Bonita Montero wrote: > Am 22.08.2023 um 08:25 schrieb Öö Tiib: > > On Tuesday, 22 August 2023 at 06:27:51 UTC+3, Bonita Montero wrote: > >> Am 21.08.2023 um 21:01 schrieb Mut...@dastardlyhq.com: > >>> On Mon, 21 Aug 2023 20:22:36 +0200 > >>> Bonita Montero <Bonita....@gmail.com> wrote: > >>>> Am 21.08.2023 um 20:12 schrieb Mut...@dastardlyhq.com: > >>>> > >>>>> On Mon, 21 Aug 2023 19:50:32 +0200 > >>>>> Bonita Montero <Bonita....@gmail.com> wrote: > >>>> > >>>>>> On my PC printing the all primes below 1E8 takes 0.827s with your > >>>>>> code. With my code it takes about 0.36s. > >>>> > >>>>> I'm fairly sure I could speed it up if I could be bothered. > >>>> > >>>> For sure not. > >>> > >>> And why's that then? ... > >> > >> Because you can only write simple code. > > > > Do not hijack nice thread of finding primes with your optimising > > textual output. > > The speedup over cout << p << endl is massive, at least with MSVC; > I've measured that, you didn't. > We already know that you are especially daff but I repeat: it does not matter to efficiency of finding primes. Open other thread if you want to discuss text output optimisations not finding primes.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 14:23 +0200 |
| Message-ID | <uc29b2$2df7f$1@dont-email.me> |
| In reply to | #91340 |
Am 22.08.2023 um 14:15 schrieb Öö Tiib: > We already know that you are especially daff but I repeat: it does not > matter to efficiency of finding primes. Open other thread if you want > to discuss text output optimisations not finding primes. I'd optimized both inside the _same_ program. You and Muttley think that simple coding is enough, I've shown multiple times that I can do it much better. Unfortunately printf() and cout << are by far not that fast as they could be, even if the output is redirected to a file.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2023-08-22 06:56 +0000 |
| Message-ID | <uc1m68$2afn4$1@dont-email.me> |
| In reply to | #91329 |
On Tue, 22 Aug 2023 05:27:36 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: >Am 21.08.2023 um 21:01 schrieb Muttley@dastardlyhq.com: >> On Mon, 21 Aug 2023 20:22:36 +0200 >> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>> Am 21.08.2023 um 20:12 schrieb Muttley@dastardlyhq.com: >>> >>>> On Mon, 21 Aug 2023 19:50:32 +0200 >>>> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>> >>>>> On my PC printing the all primes below 1E8 takes 0.827s with your >>>>> code. With my code it takes about 0.36s. >>> >>>> I'm fairly sure I could speed it up if I could be bothered. >>> >>> For sure not. >> >> And why's that then? ... > >Because you can only write simple code. Simpler code = more efficient, less bugs and easier to maintain all other things being equal. Complexity in code isn't a goal, its something to be kept to a minimum. If you were even half the genius coder you seem to think you are you'd already be aware of this.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 11:27 +0200 |
| Message-ID | <uc1v1v$2brns$2@dont-email.me> |
| In reply to | #91335 |
Am 22.08.2023 um 08:56 schrieb Muttley@dastardlyhq.com: > On Tue, 22 Aug 2023 05:27:36 +0200 > Bonita Montero <Bonita.Montero@gmail.com> wrote: >> Am 21.08.2023 um 21:01 schrieb Muttley@dastardlyhq.com: >>> On Mon, 21 Aug 2023 20:22:36 +0200 >>> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>>> Am 21.08.2023 um 20:12 schrieb Muttley@dastardlyhq.com: >>>> >>>>> On Mon, 21 Aug 2023 19:50:32 +0200 >>>>> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>>> >>>>>> On my PC printing the all primes below 1E8 takes 0.827s with your >>>>>> code. With my code it takes about 0.36s. >>>> >>>>> I'm fairly sure I could speed it up if I could be bothered. >>>> >>>> For sure not. >>> >>> And why's that then? ... >> >> Because you can only write simple code. > > Simpler code = more efficient, ... I've shown that my code is 2.3 times more efficient. In most cases more complex code is faster. > ... less bugs ... Show me the bugs. I can manage such code, you don't. I did use iterators as mich as possible to have iterator debugging to find bugs if they would have happened. > Complexity in code isn't a goal, ... It's inevitable if the code should be more efficient. > If you were even half the genius coder you seem to think > you are you'd already be aware of this. I'm not a genius, but I have extreme calm in my head that I can program something like this.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-08-22 11:34 +0200 |
| Message-ID | <uc1vep$2brns$3@dont-email.me> |
| In reply to | #91337 |
Am 22.08.2023 um 11:27 schrieb Bonita Montero: >> Simpler code = more efficient, ... > I've shown that my code is 2.3 times more efficient. > In most cases more complex code is faster. On my secondary Linux PC (Threadripper 3990X) my code is 61% faster.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2023-08-22 14:13 +0000 |
| Message-ID | <uc2fqr$2egkl$1@dont-email.me> |
| In reply to | #91337 |
On Tue, 22 Aug 2023 11:27:29 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: >Am 22.08.2023 um 08:56 schrieb Muttley@dastardlyhq.com: >> Simpler code = more efficient, ... > >I've shown that my code is 2.3 times more efficient. >In most cases more complex code is faster. No, not in most cases as endless bloated frameworks with their huge memory and CPU requirements demonstrate on a daily basis to me. There's a big difference between code thats fully featured and code thats needlessly compicated because the developer(s) were unable to think clearly or see the obvious solution. >> Complexity in code isn't a goal, ... > >It's inevitable if the code should be more efficient. Bollocks. >> If you were even half the genius coder you seem to think >> you are you'd already be aware of this. > >I'm not a genius, but I have extreme calm in my head that >I can program something like this. Oh right, you're a Zen dev are you? :) Whatever you say!
[toc] | [prev] | [next] | [standalone]
Page 4 of 8 — ← Prev page 1 2 3 [4] 5 6 7 8 Next page →
Back to top | Article view | comp.lang.c++
csiph-web