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

Groups > comp.lang.c++ > #91282

Re: Sieve of Eratosthenes

From Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups comp.lang.c++
Subject Re: Sieve of Eratosthenes
Date 2023-08-16 19:26 -0700
Organization A noiseless patient Spider
Message-ID <86msyq5rqu.fsf@linuxsc.com> (permalink)
References <ubijff$3ahf3$1@dont-email.me> <ubjedg$3emtj$1@dont-email.me> <ubjrqh$3g7ve$1@redfloyd.dont-email.me>

Show all headers | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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