Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #91459
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Sieve of Eratosthenes |
| Date | 2023-08-28 18:47 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <ucij2p$1pe53$1@dont-email.me> (permalink) |
| References | (4 earlier) <56146f63-17d7-40cc-8c42-4f29c922a8c4n@googlegroups.com> <874jkknizq.fsf@bsb.me.uk> <4f7eeaa9-47d5-4782-864b-476746654325n@googlegroups.com> <uci8ta$1nj3p$1@dont-email.me> <1872f8f6-4f5a-4059-b717-b40e8b9c5f3cn@googlegroups.com> |
Am 28.08.2023 um 18:03 schrieb Öö Tiib:
> Quite likely Ben's "naive" is better algorithm. Pasted your algorithm to
> Apple M1 Max (that is 3.2 GHz):
>
> sieving 18.1471 seconds.
> counting 1.8121 seconds.
> 203280221 primes.
I'd like to know how this code performs on a Apple
silicon Mac. That's while the M1 Max has a memory
bandwidh slightly below 300GB/s.
#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
#include <bit>
#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 end;
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 ), end, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
if( !++end )
throw bad_alloc();
using word_t = uint64_t;
constexpr size_t BITS = sizeof(word_t) * 8;
size_t bEnd = (end + BITS - 1) & -(ptrdiff_t)BITS;
if( bEnd < end )
throw bad_alloc();
using bit_vec = vector<word_t>;
using bit_it = bit_vec::iterator;
bit_vec sieve( (end + BITS - 1) / BITS, -1 );
ofstream ofs;
union ndi_t { char c; ndi_t() {} };
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( &to_address( bufBegin )->c,
&to_address( bufEnd )->c ); };
for( size_t p = 2; p < end; )
{
bit_it
pSieve = sieve.begin(),
pSieveEnd = sieve.end();
if( size_t m = 2 * p; m < end )
if( p >= BITS )
{
word_t mask = ~((word_t)1 << m % BITS);
do
pSieve[m / BITS] &= mask,
mask = rotl( mask, (int)p % BITS ),
m += p;
while( m < end );
}
else
{
pSieve += m / BITS;
word_t newMask = ~((word_t)1 << m % BITS);
do
{
word_t word = *pSieve, mask;
do
mask = newMask,
word &= mask,
newMask = rotl( mask, (int)p );
while( newMask < mask );
*pSieve = word;
} while( ++pSieve != pSieveEnd );
}
if( ++p == end ) [[unlikely]]
break;
word_t mask = (word_t)1 << p % BITS;
pSieve = sieve.begin() + p / BITS;
do
{
word_t word = *pSieve;
do
if( word & mask ) [[unlikely]]
goto foundNext;
else
++p,
mask = rotl( mask, 1 );
while( mask != 1 );
} while( ++pSieve != pSieveEnd );
foundNext:
if( p >= end ) [[unlikely]]
break;
if( !ofs.is_open() )
continue;
auto [ptr, ec] = to_chars( &bufEnd->c, &to_address( bufEnd + (AHEAD -
1) )->c, p );
if( (bool)ec ) [[unlikely]]
throw system_error( (int)ec, generic_category(), "converson failed" );
bufEnd = 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;
}
catch( system_error const &se )
{
cout << se.what() << endl;
}
}
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web