Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #91263 > unrolled thread

Sieve of Eratosthenes

Back to article view | Back to comp.lang.c++

Contents

  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 1 of 8  [1] 2 3 4 5 6 7 8  Next page →

#91263 — Sieve of Eratosthenes

I tried to implement the sieve of Erastosthenes as fast as possible.
I didn't thought it would make a big difference, but having a bit-wise
vector<bool> instead of a vector<char> makes the code twice as fast
for my AMD 7950X PC and an upper bound of one billion. The additional
overhead for the bit-wise access is less than the additional overhead
of fetching more memory.
I also tried Eulers sieve but as I expected filtering the numbers by
modulo operations with the recent prime numbers takes much more time
than simply resetting a bit; the resulting code becomes mulltiple
times slower.

#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>

#if defined(_MSC_VER)
	#pragma warning(disable: 4996)
#endif

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;
		using bool_t = conditional_t<USE_BOOL, bool, char>;
		vector<bool_t> sieve( max, true );
		for( size_t p = 2; p < max; )
		{
			for( size_t m = 2 * p; m < max; m += p )
				sieve[m] = false;
			while( ++p < max && !sieve[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;
		for( size_t i = 2; i != max; ++i )
			if( sieve[i] )
			{
				to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, i );
				(bufEnd = tcr.ptr + 1)[-1] = '\n';
				if( bufEnd - bufBegin >= BUF_SIZE )
					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 also optimized the file output because simply doing a ofs << i << endl
is multiple times slower than buffering a megabyte of data until pushing
it to the file. The numbers printed to the buffer are directly printed
inside the buffer to make the code more efficient. So if the upper bound
is one billion the time taken to print the numbers to the file is within
the measurement error.

[toc] | [next] | [standalone]

#91265

On Wednesday, August 16, 2023 at 9:38:10 PM UTC+8, Bonita Montero wrote:
> I tried to implement the sieve of Erastosthenes as fast as possible. 
> I didn't thought it would make a big difference, but having a bit-wise 
> vector<bool> instead of a vector<char> makes the code twice as fast 
> for my AMD 7950X PC and an upper bound of one billion. The additional 
> overhead for the bit-wise access is less than the additional overhead 
> of fetching more memory. 
> I also tried Eulers sieve but as I expected filtering the numbers by 
> modulo operations with the recent prime numbers takes much more time 
> than simply resetting a bit; the resulting code becomes mulltiple 
> times slower. 
> 
> #include <iostream> 
> #include <vector> 
> #include <charconv> 
> #include <string_view> 
> #include <algorithm> 
> #include <fstream> 
> #include <cctype> 
> #include <cstring> 
> 
> #if defined(_MSC_VER) 
> #pragma warning(disable: 4996) 
> #endif 
> 
> 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; 
> using bool_t = conditional_t<USE_BOOL, bool, char>; 
> vector<bool_t> sieve( max, true ); 
> for( size_t p = 2; p < max; ) 
> { 
> for( size_t m = 2 * p; m < max; m += p ) 
> sieve[m] = false; 
> while( ++p < max && !sieve[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; 
> for( size_t i = 2; i != max; ++i ) 
> if( sieve[i] ) 
> { 
> to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, i ); 
> (bufEnd = tcr.ptr + 1)[-1] = '\n'; 
> if( bufEnd - bufBegin >= BUF_SIZE ) 
> 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 also optimized the file output because simply doing a ofs << i << endl 
> is multiple times slower than buffering a megabyte of data until pushing 
> it to the file. The numbers printed to the buffer are directly printed 
> inside the buffer to make the code more efficient. So if the upper bound 
> is one billion the time taken to print the numbers to the file is within 
> the measurement error.

Confirmed, but you code don't compile.

--------------------------------- t.cpp
#include <Wy.stdio.h>
#include <Wy.time.h>
#include <CSCall/VLInt.h>
#include <vector>

using namespace Wy;

// [Syn] Print prime numbers less or equal to n
//
// Algo: sieve
//
void print_prime1(size_t n)
{
 Errno r;
 VLInt<unsigned int> barr;  // bit=0 =prime

 for(size_t i=2; i<=n; ++i) {
   if(barr.bit(i)) {
     continue;
   }
   // Cond: i is a prime number
   for(size_t j=2*i; j<=n; j+=i) {
     if((r=barr.set_bit(j,true))!=Ok) {
       WY_THROW(r);
     }
   }
 }
};

void print_prime2(size_t n)
{
 Errno r;
 Array<char> barr(n+1,0,0);  // bit=0 =prime

 for(size_t i=2; i<=n; ++i) {
   if(barr[i]) {
     continue;
   }
   // Cond: i is a prime number
   for(size_t j=2*i; j<=n; j+=i) {
     barr[j]=1;
   }
 }
};

void print_prime3(size_t n)
{
 Errno r;
 std::vector<char> barr(n+1,0);  // bit=0 =prime

 for(size_t i=2; i<=n; ++i) {
   if(barr.at(i)) {
     continue;
   }
   // Cond: i is a prime number
   for(size_t j=2*i; j<=n; j+=i) {
     barr.at(j)=1;
   }
 }
};

void print_prime4(size_t n)
{
 Errno r;
 std::vector<bool> barr(n+1,false);  // bit=0 =prime

 for(size_t i=2; i<=n; ++i) {
   if(barr.at(i)) {
     continue;
   }
   // Cond: i is a prime number
   for(size_t j=2*i; j<=n; j+=i) {
     barr.at(j)=true;
   }
 }
};

int main()
try {
 constexpr size_t Cnt=100000000L;
 Timespec tm0;

 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 print_prime1(Cnt);
 cout << "VLInt<unsigned>: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 print_prime2(Cnt);
 cout << "Array<char>: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 print_prime3(Cnt);
 cout << "vector<char>: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 print_prime4(Cnt);
 cout << "vector<bool>: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

 cout << "Ok" WY_ENDL;
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;
}
catch(...) {
 cerr << "unknown stack unwind" << WY_ENDL;
 throw;
};
----------------------------------

[]$ g++ t.cpp -lwy
[]$ ./a.out
VLInt<unsigned>: 6.162083886
Array<char>: 3.555815058
vector<char>: 5.307075961
vector<bool>: 30.257717265

I am surprised std::vector's at(size_t) is unexpected slow.

Note: Wy::Array's operator[] checks index range, should be equ. to std::vector's at(size_t)

[toc] | [prev] | [next] | [standalone]

#91266

Am 16.08.2023 um 19:57 schrieb wij:
> On Wednesday, August 16, 2023 at 9:38:10 PM UTC+8, Bonita Montero wrote:
>> I tried to implement the sieve of Erastosthenes as fast as possible.
>> I didn't thought it would make a big difference, but having a bit-wise
>> vector<bool> instead of a vector<char> makes the code twice as fast
>> for my AMD 7950X PC and an upper bound of one billion. The additional
>> overhead for the bit-wise access is less than the additional overhead
>> of fetching more memory.
>> I also tried Eulers sieve but as I expected filtering the numbers by
>> modulo operations with the recent prime numbers takes much more time
>> than simply resetting a bit; the resulting code becomes mulltiple
>> times slower.
>>
>> #include <iostream>
>> #include <vector>
>> #include <charconv>
>> #include <string_view>
>> #include <algorithm>
>> #include <fstream>
>> #include <cctype>
>> #include <cstring>
>>
>> #if defined(_MSC_VER)
>> #pragma warning(disable: 4996)
>> #endif
>>
>> 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;
>> using bool_t = conditional_t<USE_BOOL, bool, char>;
>> vector<bool_t> sieve( max, true );
>> for( size_t p = 2; p < max; )
>> {
>> for( size_t m = 2 * p; m < max; m += p )
>> sieve[m] = false;
>> while( ++p < max && !sieve[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;
>> for( size_t i = 2; i != max; ++i )
>> if( sieve[i] )
>> {
>> to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, i );
>> (bufEnd = tcr.ptr + 1)[-1] = '\n';
>> if( bufEnd - bufBegin >= BUF_SIZE )
>> 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 also optimized the file output because simply doing a ofs << i << endl
>> is multiple times slower than buffering a megabyte of data until pushing
>> it to the file. The numbers printed to the buffer are directly printed
>> inside the buffer to make the code more efficient. So if the upper bound
>> is one billion the time taken to print the numbers to the file is within
>> the measurement error.
> 
> Confirmed, but you code don't compile.

-std=c++20

> 
> --------------------------------- t.cpp
> #include <Wy.stdio.h>
> #include <Wy.time.h>
> #include <CSCall/VLInt.h>
> #include <vector>
> 
> using namespace Wy;
> 
> // [Syn] Print prime numbers less or equal to n
> //
> // Algo: sieve
> //
> void print_prime1(size_t n)
> {
>   Errno r;
>   VLInt<unsigned int> barr;  // bit=0 =prime
> 
>   for(size_t i=2; i<=n; ++i) {
>     if(barr.bit(i)) {
>       continue;
>     }
>     // Cond: i is a prime number
>     for(size_t j=2*i; j<=n; j+=i) {
>       if((r=barr.set_bit(j,true))!=Ok) {
>         WY_THROW(r);
>       }
>     }
>   }
> };
> 
> void print_prime2(size_t n)
> {
>   Errno r;
>   Array<char> barr(n+1,0,0);  // bit=0 =prime
> 
>   for(size_t i=2; i<=n; ++i) {
>     if(barr[i]) {
>       continue;
>     }
>     // Cond: i is a prime number
>     for(size_t j=2*i; j<=n; j+=i) {
>       barr[j]=1;
>     }
>   }
> };
> 
> void print_prime3(size_t n)
> {
>   Errno r;
>   std::vector<char> barr(n+1,0);  // bit=0 =prime
> 
>   for(size_t i=2; i<=n; ++i) {
>     if(barr.at(i)) {
>       continue;
>     }
>     // Cond: i is a prime number
>     for(size_t j=2*i; j<=n; j+=i) {
>       barr.at(j)=1;
>     }
>   }
> };
> 
> void print_prime4(size_t n)
> {
>   Errno r;
>   std::vector<bool> barr(n+1,false);  // bit=0 =prime
> 
>   for(size_t i=2; i<=n; ++i) {
>     if(barr.at(i)) {
>       continue;
>     }
>     // Cond: i is a prime number
>     for(size_t j=2*i; j<=n; j+=i) {
>       barr.at(j)=true;
>     }
>   }
> };

Show me the times to print primes below 10000000.

[toc] | [prev] | [next] | [standalone]

#91269

On Thursday, August 17, 2023 at 2:22:02 AM UTC+8, Bonita Montero wrote:
> Am 16.08.2023 um 19:57 schrieb wij: 
> > On Wednesday, August 16, 2023 at 9:38:10 PM UTC+8, Bonita Montero wrote: 
> >> I tried to implement the sieve of Erastosthenes as fast as possible. 
> >> I didn't thought it would make a big difference, but having a bit-wise 
> >> vector<bool> instead of a vector<char> makes the code twice as fast 
> >> for my AMD 7950X PC and an upper bound of one billion. The additional 
> >> overhead for the bit-wise access is less than the additional overhead 
> >> of fetching more memory. 
> >> I also tried Eulers sieve but as I expected filtering the numbers by 
> >> modulo operations with the recent prime numbers takes much more time 
> >> than simply resetting a bit; the resulting code becomes mulltiple 
> >> times slower. 
> >> 
> >> #include <iostream> 
> >> #include <vector> 
> >> #include <charconv> 
> >> #include <string_view> 
> >> #include <algorithm> 
> >> #include <fstream> 
> >> #include <cctype> 
> >> #include <cstring> 
> >> 
> >> #if defined(_MSC_VER) 
> >> #pragma warning(disable: 4996) 
> >> #endif 
> >> 
> >> 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; 
> >> using bool_t = conditional_t<USE_BOOL, bool, char>; 
> >> vector<bool_t> sieve( max, true ); 
> >> for( size_t p = 2; p < max; ) 
> >> { 
> >> for( size_t m = 2 * p; m < max; m += p ) 
> >> sieve[m] = false; 
> >> while( ++p < max && !sieve[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; 
> >> for( size_t i = 2; i != max; ++i ) 
> >> if( sieve[i] ) 
> >> { 
> >> to_chars_result tcr = to_chars( bufEnd, bufEnd + 32, i ); 
> >> (bufEnd = tcr.ptr + 1)[-1] = '\n'; 
> >> if( bufEnd - bufBegin >= BUF_SIZE ) 
> >> 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 also optimized the file output because simply doing a ofs << i << endl 
> >> is multiple times slower than buffering a megabyte of data until pushing 
> >> it to the file. The numbers printed to the buffer are directly printed 
> >> inside the buffer to make the code more efficient. So if the upper bound 
> >> is one billion the time taken to print the numbers to the file is within 
> >> the measurement error. 
> > 
> > Confirmed, but you code don't compile.
> -std=c++20
> > 
> > --------------------------------- t.cpp 
> > #include <Wy.stdio.h> 
> > #include <Wy.time.h> 
> > #include <CSCall/VLInt.h> 
> > #include <vector> 
> > 
> > using namespace Wy; 
> > 
> > // [Syn] Print prime numbers less or equal to n 
> > // 
> > // Algo: sieve 
> > // 
> > void print_prime1(size_t n) 
> > { 
> > Errno r; 
> > VLInt<unsigned int> barr; // bit=0 =prime 
> > 
> > for(size_t i=2; i<=n; ++i) { 
> > if(barr.bit(i)) { 
> > continue; 
> > } 
> > // Cond: i is a prime number 
> > for(size_t j=2*i; j<=n; j+=i) { 
> > if((r=barr.set_bit(j,true))!=Ok) { 
> > WY_THROW(r); 
> > } 
> > } 
> > } 
> > }; 
> > 
> > void print_prime2(size_t n) 
> > { 
> > Errno r; 
> > Array<char> barr(n+1,0,0); // bit=0 =prime 
> > 
> > for(size_t i=2; i<=n; ++i) { 
> > if(barr[i]) { 
> > continue; 
> > } 
> > // Cond: i is a prime number 
> > for(size_t j=2*i; j<=n; j+=i) { 
> > barr[j]=1; 
> > } 
> > } 
> > }; 
> > 
> > void print_prime3(size_t n) 
> > { 
> > Errno r; 
> > std::vector<char> barr(n+1,0); // bit=0 =prime 
> > 
> > for(size_t i=2; i<=n; ++i) { 
> > if(barr.at(i)) { 
> > continue; 
> > } 
> > // Cond: i is a prime number 
> > for(size_t j=2*i; j<=n; j+=i) { 
> > barr.at(j)=1; 
> > } 
> > } 
> > }; 
> > 
> > void print_prime4(size_t n) 
> > { 
> > Errno r; 
> > std::vector<bool> barr(n+1,false); // bit=0 =prime 
> > 
> > for(size_t i=2; i<=n; ++i) { 
> > if(barr.at(i)) { 
> > continue; 
> > } 
> > // Cond: i is a prime number 
> > for(size_t j=2*i; j<=n; j+=i) { 
> > barr.at(j)=true; 
> > } 
> > } 
> > };
> Show me the times to print primes below 10000000.

[]$ g++ t12.cpp -lwy -std=c++20
[]$ ./a.out
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 2
...(cut)
889 9999901 9999907 9999929 9999931 9999937 9999943 9999971 9999973 9999991
pi(10000000)= 664579
print_prime: 2.740338666
Ok

--------------------- t12.cpp
#include <Wy.stdio.h>
#include <Wy.time.h>
#include <CSCall/VLInt.h>

using namespace Wy;

// [Syn] Print prime numbers less or equal to n
//
// Algo: sieve
//
void print_prime(size_t n)
{
 Errno r;
 VLInt<unsigned int> barr;  // bit=0 =prime

 for(size_t i=2; i<=n; ++i) {
   if(barr.bit(i)) {
     continue;
   }
   // Cond: i is a prime number
   for(size_t j=2*i; j<=n; j+=i) {
     if((r=barr.set_bit(j,true))!=Ok) {
       WY_THROW(r);
     }
   }
 }

 // print prime number (from 2)
 size_t pcnt=0;
 for(size_t i=2; i<=n; ++i) {
   if(barr.bit(i)==false) {
     cout << wrd(i) << ' ';
     ++pcnt;
   }
 }
 cout << WY_ENDL;
 cout << "pi(" << n << ")= " << pcnt << WY_ENDL;
};

int main()
try {
 Timespec tm0;

 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 print_prime(10000000);
 cout << "print_prime: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;
 cout << "Ok" WY_ENDL;
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;
}
catch(...) {
 cerr << "unknown stack unwind" << WY_ENDL;
 throw;
};

[toc] | [prev] | [next] | [standalone]

#91267

16.08.2023 20:57 wij kirjutas:
> 
> []$ g++ t.cpp -lwy
> 
> I am surprised std::vector's at(size_t) is unexpected slow.

You are missing -O2 or -O3. There is no point to talk about the speed of 
unoptimized code.

[toc] | [prev] | [next] | [standalone]

#91268

On Thursday, August 17, 2023 at 2:45:12 AM UTC+8, Paavo Helde wrote:
> 16.08.2023 20:57 wij kirjutas: 
> > 
> > []$ g++ t.cpp -lwy
> > 
> > I am surprised std::vector's at(size_t) is unexpected slow.
> You are missing -O2 or -O3. There is no point to talk about the speed of 
> unoptimized code.

[]$ g++ t.cpp -lwy -O2
[]$ ./a.out 
VLInt<unsigned>: 1.259642293
Array<char>: 1.525368272
vector<char>: 1.484200452
vector<bool>: 1.533252238

----------------
-O2 makes sense. But the problem now is why VLInt is faster? (VLInt allocates memory on demand)

[toc] | [prev] | [next] | [standalone]

#91271

On 2023-08-16 3:37 PM, Bonita Montero wrote:
> I tried to implement the sieve of Erastosthenes as fast as possible.
> I didn't thought it would make a big difference, but having a bit-wise
> vector<bool> instead of a vector<char> makes the code twice as fast
> for my AMD 7950X PC and an upper bound of one billion. The additional
> overhead for the bit-wise access is less than the additional overhead
> of fetching more memory.


An apparent mystery, because I get only a marginal difference, down at 
10% or less.

On my computer the code below is slightly faster than yours for a 
10'000'000 sieve, respectively (typical results, three runs, only the 
vector allocation + sieve code measured, not file i/o)

     0.0477802 seconds.
     0.0466974 seconds.
     0.0472202 seconds.

... for my code, versus

     0.0502888 seconds.
     0.0482821 seconds.
     0.0505414 seconds.

... for yours with the `std::string_view` instantiations fixed, 
producing the same file contents.


     #include <fmt/core.h>
     #include "cppm-Timer.hpp"

     #include <vector>
     using   std::ofstream,
             std::vector;

     #include <stdlib.h>         // EXIT_FAILURE
     #include <stdio.h>          // fopen, fclose

     auto main() -> int
     {
         constexpr int n = 10'000'000;

         cppm::Timer timer;
         auto is_composite = vector<bool>( n + 1 );
         for( int i = 2; i < n; ) {
             while( is_composite[i] ) { ++i; }
             const int prime = i;
             for( int j = 2*prime; j < n; j += prime ) { is_composite[j] 
= true; }
             ++i;
         }
         timer.stop();
         fmt::print( "{} seconds.\n", timer.seconds() );

         auto f = fopen( "primes.alf.txt", "w" );
         if( not f ) { return EXIT_FAILURE; }
         for( int i = 2; i < n; ++i ) {
             if( not is_composite[i] ) {
                 fmt::print( f, "{:d}\n", i );
             }
         }
         fclose( f );
     }


The timer code:


     #pragma once

     #include <chrono>
     #include <optional>
     #include <type_traits>

     namespace cppm {
         namespace chrono = std::chrono;
         using   std::optional,          // <optional>
                 std::conditional_t;     // <type_traits>

         using Duration      = chrono::duration<double>;

         class Timer
         {
             using Hrc = chrono::high_resolution_clock;  using Sc = 
chrono::steady_clock;

         public:
             using Clock         = conditional_t<Hrc::is_steady, Hrc, Sc>;
             using Time_point    = chrono::time_point<Clock>;

         private:
             Time_point              m_start_time;
             optional<Time_point>    m_opt_end_time;

         public:
             Timer(): m_start_time( Clock::now() ), m_opt_end_time() {}

             void stop() { if( not m_opt_end_time ) { m_opt_end_time = 
Clock::now(); } }

             auto duration() const   -> Duration { return 
m_opt_end_time.value() - m_start_time; }
             auto seconds() const    -> double   { return 
duration().count(); }
         };
     }  // namespace cppm


I have some other more advanced prime sieve code that I made for an 
example, but I think it's much slower, it's just a way that can go on 
and on forever, or more precisely till the end of the integer type's 
range or it runs out of memory for a map of the deduces primes.


- Alf

[toc] | [prev] | [next] | [standalone]

#91272

On 2023-08-16 11:17 PM, Alf P. Steinbach wrote:
> ...

Unfortunately the `using std::ofstream`, left in the code due to 
imperfect editing, compiled -- with Visual C++. Gah! Not used.


- Alf (wishing for old Modula-2, just with better syntax etc.)

[toc] | [prev] | [next] | [standalone]

#91274

On 2023-08-16 11:17 PM, Alf P. Steinbach wrote:
> On 2023-08-16 3:37 PM, Bonita Montero wrote:
>> I tried to implement the sieve of Erastosthenes as fast as possible.
>> I didn't thought it would make a big difference, but having a bit-wise
>> vector<bool> instead of a vector<char> makes the code twice as fast
>> for my AMD 7950X PC and an upper bound of one billion. The additional
>> overhead for the bit-wise access is less than the additional overhead
>> of fetching more memory.
> 
> 
> An apparent mystery, because I get only a marginal difference, down at 
> 10% or less.
> 
> On my computer the code below is slightly faster than yours for a 
> 10'000'000 sieve, respectively (typical results, three runs, only the 
> vector allocation + sieve code measured, not file i/o)
> 
>      0.0477802 seconds.
>      0.0466974 seconds.
>      0.0472202 seconds.
> 
> ... for my code, versus
> 
>      0.0502888 seconds.
>      0.0482821 seconds.
>      0.0505414 seconds.
> 
> ... for yours with the `std::string_view` instantiations fixed, 
> producing the same file contents.
> 
> 
>      #include <fmt/core.h>
>      #include "cppm-Timer.hpp"
> 
>      #include <vector>
>      using   std::ofstream,
>              std::vector;
> 
>      #include <stdlib.h>         // EXIT_FAILURE
>      #include <stdio.h>          // fopen, fclose
> 
>      auto main() -> int
>      {
>          constexpr int n = 10'000'000;
> 
>          cppm::Timer timer;
>          auto is_composite = vector<bool>( n + 1 );
>          for( int i = 2; i < n; ) {
>              while( is_composite[i] ) { ++i; }
>              const int prime = i;
>              for( int j = 2*prime; j < n; j += prime ) { is_composite[j] 
> = true; }
>              ++i;
>          }
>          timer.stop();
>          fmt::print( "{} seconds.\n", timer.seconds() );
> 
>          auto f = fopen( "primes.alf.txt", "w" );
>          if( not f ) { return EXIT_FAILURE; }
>          for( int i = 2; i < n; ++i ) {
>              if( not is_composite[i] ) {
>                  fmt::print( f, "{:d}\n", i );
>              }
>          }
>          fclose( f );
>      }
> 
> 
> The timer code:
> 
> 
>      #pragma once
> 
>      #include <chrono>
>      #include <optional>
>      #include <type_traits>
> 
>      namespace cppm {
>          namespace chrono = std::chrono;
>          using   std::optional,          // <optional>
>                  std::conditional_t;     // <type_traits>
> 
>          using Duration      = chrono::duration<double>;
> 
>          class Timer
>          {
>              using Hrc = chrono::high_resolution_clock;  using Sc = 
> chrono::steady_clock;
> 
>          public:
>              using Clock         = conditional_t<Hrc::is_steady, Hrc, Sc>;
>              using Time_point    = chrono::time_point<Clock>;
> 
>          private:
>              Time_point              m_start_time;
>              optional<Time_point>    m_opt_end_time;
> 
>          public:
>              Timer(): m_start_time( Clock::now() ), m_opt_end_time() {}
> 
>              void stop() { if( not m_opt_end_time ) { m_opt_end_time = 
> Clock::now(); } }
> 
>              auto duration() const   -> Duration { return 
> m_opt_end_time.value() - m_start_time; }
>              auto seconds() const    -> double   { return 
> duration().count(); }
>          };
>      }  // namespace cppm
> 
> 
> I have some other more advanced prime sieve code that I made for an 
> example, but I think it's much slower, it's just a way that can go on 
> and on forever, or more precisely till the end of the integer type's 
> range or it runs out of memory for a map of the deduces primes.

Well, I've become stupid in my old days. Reduced running time by say 25% 
or so by very simple optimization. I did not think of that until /after/ 
I'd posted.

New running time, three tries:

     0.0365686 seconds.
     0.0362102 seconds.
     0.0359283 seconds.

New better shiny sparkling code:

     #include <fmt/core.h>
     #include "cppm-Timer.hpp"

     #include <vector>
     using   std::vector;

     #include <stdlib.h>         // EXIT_FAILURE
     #include <stdio.h>          // fopen, fclose

     auto main() -> int
     {
         constexpr int n = 10'000'000;
         constexpr int sqrt_n = 3'162;

         cppm::Timer timer;
         auto is_composite = vector<bool>( n + 1 );
         for( int i = 2; i < n; ) {
             while( is_composite[i] ) { ++i; }
             const int prime = i;
             if( prime < sqrt_n ) {
                 for( int j = prime*prime; j < n; j += prime ) {
                     is_composite[j] = true;
                 }
             }
             ++i;
         }
         timer.stop();
         fmt::print( "{} seconds.\n", timer.seconds() );

         auto f = fopen( "primes.alf.txt", "w" );
         if( not f ) { return EXIT_FAILURE; }
         for( int i = 2; i < n; ++i ) {
             if( not is_composite[i] ) {
                 fmt::print( f, "{:d}\n", i );
             }
         }
         fclose( f );
     }

Clue: for efficiency, avoid totally needless work.


- Alf

[toc] | [prev] | [next] | [standalone]

#91276

On 2023-08-16 11:39 PM, Alf P. Steinbach wrote:
> On 2023-08-16 11:17 PM, Alf P. Steinbach wrote:
>> On 2023-08-16 3:37 PM, Bonita Montero wrote:
>>> I tried to implement the sieve of Erastosthenes as fast as possible.
>>> I didn't thought it would make a big difference, but having a bit-wise
>>> vector<bool> instead of a vector<char> makes the code twice as fast
>>> for my AMD 7950X PC and an upper bound of one billion. The additional
>>> overhead for the bit-wise access is less than the additional overhead
>>> of fetching more memory.
>>
>>
>> An apparent mystery, because I get only a marginal difference, down at 
>> 10% or less.
>>
>> On my computer the code below is slightly faster than yours for a 
>> 10'000'000 sieve, respectively (typical results, three runs, only the 
>> vector allocation + sieve code measured, not file i/o)
>>
>>      0.0477802 seconds.
>>      0.0466974 seconds.
>>      0.0472202 seconds.
>>
>> ... for my code, versus
>>
>>      0.0502888 seconds.
>>      0.0482821 seconds.
>>      0.0505414 seconds.
>>
>> ... for yours with the `std::string_view` instantiations fixed, 
>> producing the same file contents.
>>
>>
>>      #include <fmt/core.h>
>>      #include "cppm-Timer.hpp"
>>
>>      #include <vector>
>>      using   std::ofstream,
>>              std::vector;
>>
>>      #include <stdlib.h>         // EXIT_FAILURE
>>      #include <stdio.h>          // fopen, fclose
>>
>>      auto main() -> int
>>      {
>>          constexpr int n = 10'000'000;
>>
>>          cppm::Timer timer;
>>          auto is_composite = vector<bool>( n + 1 );
>>          for( int i = 2; i < n; ) {
>>              while( is_composite[i] ) { ++i; }
>>              const int prime = i;
>>              for( int j = 2*prime; j < n; j += prime ) { 
>> is_composite[j] = true; }
>>              ++i;
>>          }
>>          timer.stop();
>>          fmt::print( "{} seconds.\n", timer.seconds() );
>>
>>          auto f = fopen( "primes.alf.txt", "w" );
>>          if( not f ) { return EXIT_FAILURE; }
>>          for( int i = 2; i < n; ++i ) {
>>              if( not is_composite[i] ) {
>>                  fmt::print( f, "{:d}\n", i );
>>              }
>>          }
>>          fclose( f );
>>      }
>>
>>
>> The timer code:
>>
>>
>>      #pragma once
>>
>>      #include <chrono>
>>      #include <optional>
>>      #include <type_traits>
>>
>>      namespace cppm {
>>          namespace chrono = std::chrono;
>>          using   std::optional,          // <optional>
>>                  std::conditional_t;     // <type_traits>
>>
>>          using Duration      = chrono::duration<double>;
>>
>>          class Timer
>>          {
>>              using Hrc = chrono::high_resolution_clock;  using Sc = 
>> chrono::steady_clock;
>>
>>          public:
>>              using Clock         = conditional_t<Hrc::is_steady, Hrc, 
>> Sc>;
>>              using Time_point    = chrono::time_point<Clock>;
>>
>>          private:
>>              Time_point              m_start_time;
>>              optional<Time_point>    m_opt_end_time;
>>
>>          public:
>>              Timer(): m_start_time( Clock::now() ), m_opt_end_time() {}
>>
>>              void stop() { if( not m_opt_end_time ) { m_opt_end_time = 
>> Clock::now(); } }
>>
>>              auto duration() const   -> Duration { return 
>> m_opt_end_time.value() - m_start_time; }
>>              auto seconds() const    -> double   { return 
>> duration().count(); }
>>          };
>>      }  // namespace cppm
>>
>>
>> I have some other more advanced prime sieve code that I made for an 
>> example, but I think it's much slower, it's just a way that can go on 
>> and on forever, or more precisely till the end of the integer type's 
>> range or it runs out of memory for a map of the deduces primes.
> 
> Well, I've become stupid in my old days. Reduced running time by say 25% 
> or so by very simple optimization. I did not think of that until /after/ 
> I'd posted.
> 
> New running time, three tries:
> 
>      0.0365686 seconds.
>      0.0362102 seconds.
>      0.0359283 seconds.
> 
> New better shiny sparkling code:
> 
>      #include <fmt/core.h>
>      #include "cppm-Timer.hpp"
> 
>      #include <vector>
>      using   std::vector;
> 
>      #include <stdlib.h>         // EXIT_FAILURE
>      #include <stdio.h>          // fopen, fclose
> 
>      auto main() -> int
>      {
>          constexpr int n = 10'000'000;
>          constexpr int sqrt_n = 3'162;
> 
>          cppm::Timer timer;
>          auto is_composite = vector<bool>( n + 1 );
>          for( int i = 2; i < n; ) {
>              while( is_composite[i] ) { ++i; }
>              const int prime = i;
>              if( prime < sqrt_n ) {
>                  for( int j = prime*prime; j < n; j += prime ) {
>                      is_composite[j] = true;
>                  }
>              }
>              ++i;
>          }
>          timer.stop();
>          fmt::print( "{} seconds.\n", timer.seconds() );
> 
>          auto f = fopen( "primes.alf.txt", "w" );
>          if( not f ) { return EXIT_FAILURE; }
>          for( int i = 2; i < n; ++i ) {
>              if( not is_composite[i] ) {
>                  fmt::print( f, "{:d}\n", i );
>              }
>          }
>          fclose( f );
>      }
> 
> Clue: for efficiency, avoid totally needless work.

Oh, I'm REALLY old.

Even less slow, now clocking in at

     0.0260816 seconds.
     0.0267381 seconds.
     0.0269437 seconds.

Code:

     #include <fmt/core.h>
     #include "cppm-Timer.hpp"

     #include <vector>
     using   std::vector;

     #include <stdlib.h>         // EXIT_FAILURE
     #include <stdio.h>          // fopen, fclose

     auto main() -> int
     {
         constexpr int n = 10'000'000;
         constexpr int sqrt_n = 3'162;

         cppm::Timer timer;
         auto is_composite = vector<bool>( n + 1 );
         for( int i = 4; i < n; i += 2 ) { is_composite[i] = true; }
         for( int i = 3; i < n; ) {
             while( is_composite[i] ) { ++i; }
             const int prime = i;
             if( prime <= sqrt_n ) {
                 for( int j = prime*prime; j < n; j += 2*prime ) {
                     is_composite[j] = true;
                 }
             }
             ++i;
         }
         timer.stop();
         fmt::print( "{} seconds.\n", timer.seconds() );

         auto f = fopen( "primes.alf.txt", "w" );
         if( not f ) { return EXIT_FAILURE; }
         for( int i = 2; i < n; ++i ) {
             if( not is_composite[i] ) {
                 fmt::print( f, "{:d}\n", i );
             }
         }
         fclose( f );
     }

But every little optimization adds complexity and verbosity.

- Alf

[toc] | [prev] | [next] | [standalone]

#91279

On 8/16/2023 2:59 PM, Alf P. Steinbach wrote:
[...]

Fwiw, keep in mind what your system is currently doing when you run a 
benchmark. Personally, I shutdown as many unnecessary processes as I can 
before I run any benchmark. Bare bones.

[toc] | [prev] | [next] | [standalone]

#91280

On 8/16/2023 2:17 PM, Alf P. Steinbach wrote:
> On 2023-08-16 3:37 PM, Bonita Montero wrote:
>> I tried to implement the sieve of Erastosthenes as fast as possible.
>> I didn't thought it would make a big difference, but having a bit-wise
>> vector<bool> instead of a vector<char> makes the code twice as fast
>> for my AMD 7950X PC and an upper bound of one billion. The additional
>> overhead for the bit-wise access is less than the additional overhead
>> of fetching more memory
[redacted]

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.

It can be sped up by checking for divisibility only by values less than
or equal to sqrt(candidate value).

I only check up to 1 million, but you can obviously change max_prime.
Also change to long long for values greater than 2 billion.

--- cut here --

#include <iostream>
#include <ostream>
#include <vector>
#include <cmath>
#include <cstdlib>

const long max_prime = 1000000;
const long max_factor =
   static_cast<long>(std::sqrt(static_cast<double>(max_prime))) + 1;

int main(int, char *[])
{
	std::vector<long> factors;

	std::cout << "2" << std::endl;
	for (long n = 3; n < max_prime ; n += 2 )
	{
		bool composite;
		composite = false;
		for (std::vector<long>::iterator it = factors.begin();
				!composite && it != factors.end();
				++it)
		{
			if ((n % *it) == 0)
				composite = true;
		}
		if (!composite)
		{
			std::cout << n << std::endl;

			if (n < max_factor)
			    factors.push_back(n);
		}
	}

	return EXIT_SUCCESS;
}

[toc] | [prev] | [next] | [standalone]

#91282

red floyd <no.spam.here@its.invalid> writes:

> On 8/16/2023 2:17 PM, Alf P. Steinbach wrote:
>
>> On 2023-08-16 3:37 PM, Bonita Montero wrote:
>>
>>> I tried to implement the sieve of Erastosthenes as fast as
>>> possible.  I didn't thought it would make a big difference, but
>>> having a bit-wise vector<bool> instead of a vector<char> makes the
>>> code twice as fast for my AMD 7950X PC and an upper bound of one
>>> billion.  The additional overhead for the bit-wise access is less
>>> than the additional overhead of fetching more memory
>
> [redacted]
>
> 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.  [...]

Here are some suggestions for everyone.

Except for 2, 3, and 5, numbers can be considered mod 30, and
there are (conveniently) only 8 candidates:  1, 7, 11, 13, 17,
19, 23, and 29.  For numbers 7 and up, every prime must be
one of those candidates (mod 30).

By storing the results for blocks of 30 in a byte, we can
store results for all 32 bit primes in 143165577 bytes.

There are some extra tricks taking advantage of what happens
with the bit numbers.  For example 7 * 37 has two 7's, which
is 49, which is 19 mod 30, so the bit for that product will
be in the 19 position.  Being clever will avoid any shifting
or modding.

I suggest computing all 32 bit primes for the benchmark
tests.  Shouldn't take too long.

[toc] | [prev] | [next] | [standalone]

#91450

On Thursday, 17 August 2023 at 05:26:37 UTC+3, Tim Rentsch wrote:
> 
> I suggest computing all 32 bit primes for the benchmark 
> tests. Shouldn't take too long.
> 
Took 14 minutes to find those 203280221 primes single threaded
on i7-8550U.

[toc] | [prev] | [next] | [standalone]

#91452

Öö Tiib <ootiib@hot.ee> writes:

> On Thursday, 17 August 2023 at 05:26:37 UTC+3, Tim Rentsch wrote:
>> 
>> I suggest computing all 32 bit primes for the benchmark 
>> tests. Shouldn't take too long.
>> 
> Took 14 minutes to find those 203280221 primes single threaded
> on i7-8550U.

What do you mean by find?  Do you include printing them out because that
will depend rather more on the OS.

I wanted to try a newer algorithm, so I coded up a rather naive version
of Atkin & Bernstein's sieve in C.  It needs some tidying and I imagine
a bit can be shaved off the time.

It can generate a bitmap of the 203280221 primes and then count them in
about 40 seconds on an i5-8265U CPU @ 1.60GHz (single threaded).  It
takes about 55 seconds to write them (in decimal) to a file.  The result
is over 2GB:

$ wc primes
 203280221  203280221 2178719347 primes

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#91454

On Monday, 28 August 2023 at 02:50:05 UTC+3, Ben Bacarisse wrote:
> Öö Tiib <oot...@hot.ee> writes: 
> 
> > On Thursday, 17 August 2023 at 05:26:37 UTC+3, Tim Rentsch wrote: 
> >> 
> >> I suggest computing all 32 bit primes for the benchmark 
> >> tests. Shouldn't take too long. 
> >> 
> > Took 14 minutes to find those 203280221 primes single threaded 
> > on i7-8550U.
> What do you mean by find? Do you include printing them out because that 
> will depend rather more on the OS. 
> 
I did try to invent a sieve algorithm this weekend, it worked, but bit
sluggish, so I posted it.
I did not measure printing or storing to file, only sieving and counting
(to test that there are 203280221).

> I wanted to try a newer algorithm, so I coded up a rather naive version 
> of Atkin & Bernstein's sieve in C. It needs some tidying and I imagine 
> a bit can be shaved off the time. 
> 
> It can generate a bitmap of the 203280221 primes and then count them in 
> about 40 seconds on an i5-8265U CPU @ 1.60GHz (single threaded). It 
> takes about 55 seconds to write them (in decimal) to a file. The result 
> is over 2GB: 
> 
> $ wc primes 
> 203280221 203280221 2178719347 primes 
> 
Thanks, so I apparently need to optimize my algorithm at least 30 times
faster for it to be worth anything. Maybe next weekend.

[toc] | [prev] | [next] | [standalone]

#91457

On 2023-08-28 8:23 AM, Öö Tiib wrote:
> On Monday, 28 August 2023 at 02:50:05 UTC+3, Ben Bacarisse wrote:
>> Öö Tiib <oot...@hot.ee> writes:
>>
>>> On Thursday, 17 August 2023 at 05:26:37 UTC+3, Tim Rentsch wrote:
>>>>
>>>> I suggest computing all 32 bit primes for the benchmark
>>>> tests. Shouldn't take too long.
>>>>
>>> Took 14 minutes to find those 203280221 primes single threaded
>>> on i7-8550U.
>> What do you mean by find? Do you include printing them out because that
>> will depend rather more on the OS.
>>
> I did try to invent a sieve algorithm this weekend, it worked, but bit
> sluggish, so I posted it.
> I did not measure printing or storing to file, only sieving and counting
> (to test that there are 203280221).
> 
>> I wanted to try a newer algorithm, so I coded up a rather naive version
>> of Atkin & Bernstein's sieve in C. It needs some tidying and I imagine
>> a bit can be shaved off the time.
>>
>> It can generate a bitmap of the 203280221 primes and then count them in
>> about 40 seconds on an i5-8265U CPU @ 1.60GHz (single threaded). It
>> takes about 55 seconds to write them (in decimal) to a file. The result
>> is over 2GB:
>>
>> $ wc primes
>> 203280221 203280221 2178719347 primes
>>
> Thanks, so I apparently need to optimize my algorithm at least 30 times
> faster for it to be worth anything. Maybe next weekend.

The code I posted earlier, with limits changed to compute primes up to 
32^2 - 1 and with `int` changed to `int64_t`, reports

28.9473339 seconds.
203280221 primes.

msinfo32 says "Processor Intel(R) Core(TM) i7-8700T CPU @ 2.40GHz, 2400 
Mhz, 6 Core(s), 12 Logical Processor(s)"

so accounting for clock rate it seems a little bit slower than Ben's.

- Alf


#include <fmt/core.h>
#include "cppm-Timer.hpp"

#include <vector>
using   std::vector;

#include <stdint.h>         // int64_t
#include <stdlib.h>         // EXIT_FAILURE
#include <stdio.h>          // fopen, fclose

using Int64 = int64_t;

auto main() -> int
{
     constexpr Int64 n = 4'294'967'295;      // 2^32 - 1
     constexpr Int64 sqrt_n = 65'535;

     cppm::Timer timer;
     auto is_composite = vector<bool>( n + 1 );
     for( Int64 i = 4; i < n; i += 2 ) { is_composite[i] = true; }
     for( Int64 i = 3; i < n; ) {
         while( is_composite[i] ) { ++i; }
         const Int64 prime = i;
         if( prime <= sqrt_n ) {
             for( Int64 j = prime*prime; j < n; j += 2*prime ) {
                 is_composite[j] = true;
             }
         }
         ++i;
     }
     timer.stop();
     fmt::print( "{} seconds.\n", timer.seconds() );

     Int64 count = 0;
     for( Int64 i = 2; i < n; ++i ) {
         if( not is_composite[i] ) {
             ++count;
         }
     }
     fmt::print( "{} primes.\n", count );

     auto f = fopen( "primes.alf.txt", "w" );
     if( not f ) { return EXIT_FAILURE; }
     for( Int64 i = 2; i < n; ++i ) {
         if( not is_composite[i] ) {
             fmt::print( f, "{:d}\n", i );
         }
     }
     fclose( f );
}

[toc] | [prev] | [next] | [standalone]

#91458

On Monday, 28 August 2023 at 16:54:04 UTC+3, Alf P. Steinbach wrote:
> On 2023-08-28 8:23 AM, Öö Tiib wrote: 
> > On Monday, 28 August 2023 at 02:50:05 UTC+3, Ben Bacarisse wrote: 
> >> Öö Tiib <oot...@hot.ee> writes: 
> >> 
> >>> On Thursday, 17 August 2023 at 05:26:37 UTC+3, Tim Rentsch wrote: 
> >>>> 
> >>>> I suggest computing all 32 bit primes for the benchmark 
> >>>> tests. Shouldn't take too long. 
> >>>> 
> >>> Took 14 minutes to find those 203280221 primes single threaded 
> >>> on i7-8550U. 
> >> What do you mean by find? Do you include printing them out because that 
> >> will depend rather more on the OS. 
> >> 
> > I did try to invent a sieve algorithm this weekend, it worked, but bit 
> > sluggish, so I posted it. 
> > I did not measure printing or storing to file, only sieving and counting 
> > (to test that there are 203280221). 
> > 
> >> I wanted to try a newer algorithm, so I coded up a rather naive version 
> >> of Atkin & Bernstein's sieve in C. It needs some tidying and I imagine 
> >> a bit can be shaved off the time. 
> >> 
> >> It can generate a bitmap of the 203280221 primes and then count them in 
> >> about 40 seconds on an i5-8265U CPU @ 1.60GHz (single threaded). It 
> >> takes about 55 seconds to write them (in decimal) to a file. The result 
> >> is over 2GB: 
> >> 
> >> $ wc primes 
> >> 203280221 203280221 2178719347 primes 
> >> 
> > Thanks, so I apparently need to optimize my algorithm at least 30 times 
> > faster for it to be worth anything. Maybe next weekend. 
> 
> The code I posted earlier, with limits changed to compute primes up to 
> 32^2 - 1 and with `int` changed to `int64_t`, reports 
> 
> 28.9473339 seconds. 
> 203280221 primes. 
> 
> msinfo32 says "Processor Intel(R) Core(TM) i7-8700T CPU @ 2.40GHz, 2400 
> Mhz, 6 Core(s), 12 Logical Processor(s)" 
> 
> so accounting for clock rate it seems a little bit slower than Ben's. 
> 
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.

[toc] | [prev] | [next] | [standalone]

#91459

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;
	}
}

[toc] | [prev] | [next] | [standalone]

#91471

I implemented Alf's code according to my taste. The code has
about 40% the performance of my code if I don't output a file
with the numbers on Sklyake CPU with g++ 12 and -march=native.

#include <iostream>
#include <vector>
#include <charconv>
#include <fstream>
#include <cmath>
#include <cstring>

using namespace std;

int main( int argc, char **argv )
{
	constexpr size_t BUF_SIZE = 0x100000;
	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();
	vector<bool> primes( end, true );
	ofstream ofs;
	string printBuf;
	if( argc < 3 || *argv[2] )
		ofs.exceptions( ofstream::failbit | ofstream::badbit ),
		ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc ),
		printBuf.reserve( BUF_SIZE + 31 );
	size_t sqr = (ptrdiff_t)ceil( sqrt( (ptrdiff_t)end ) );
	for( size_t p = 2; p < end; ++p )
	{
		while( !primes[p] )
			if( ++p == end )
				goto end;
		if( p < sqr )
		{
			size_t m = p * p;
			do
				primes[m] = false;
			while( (m += p) < end );
		}
		if( !ofs.is_open() )
			continue;
		char strPrime[32];
		auto [ptr, ec] = to_chars( strPrime, std::end( strPrime ), p );
		if( (bool)ec ) [[unlikely]]
			throw system_error( (int)ec, generic_category(), "converson failed" );
		*ptr++ = '\n';
		printBuf += string_view( strPrime, ptr );
		if( printBuf.size() >= BUF_SIZE )
			ofs << printBuf,
			printBuf.resize( 0 );
	}
end:
	if( ofs.is_open() )
		ofs << printBuf;
}

[toc] | [prev] | [next] | [standalone]

Page 1 of 8  [1] 2 3 4 5 6 7 8  Next page →

Back to top | Article view | comp.lang.c++

csiph-web