Re: OT: Re: Sieve of Erastosthenes optimized to the max

Liste des GroupesRevenir à cl c++ 
Sujet : Re: OT: Re: Sieve of Erastosthenes optimized to the max
De : no.spam.here (at) *nospam* its.invalid (red floyd)
Groupes : comp.lang.c++
Date : 20. Aug 2024, 05:08:11
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <va14rc$387ss$1@redfloyd.dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
User-Agent : Mozilla Thunderbird
So I'm a little late, but here's my effort to use the modulo 30 trick.
Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5 5600x, 64GB RAM
g++ -O3 -std=c++17
5761455 primess less than 100 million in 0.182269s
50847534 primes less than 1 billion in 2.841167s
455052511 primes less than 10billion in 53.009133s
-- CUT HERE ---
#include <iostream>
#include <chrono>
#include <stdint.h>
#include <vector>
#include <tuple>
#include <string>
#include <iomanip>
using inttype_t = uint64_t;
using settype_t = unsigned char;
class Sieve {
     static constexpr inttype_t MOD_VALUE { 30ull };
     // 1, 7, 11, 13, 17, 19, 23, 29
     static constexpr settype_t masks[] = {
         0x00, 0x01, 0x00, 0x00, 0x00, 0x00,  // 1
         0x00, 0x02, 0x00, 0x00, 0x00, 0x04,  // 7, 11
         0x00, 0x08, 0x00, 0x00, 0x00, 0x10,  // 13, 17
         0x00, 0x20, 0x00, 0x00, 0x00, 0x40,  // 19, 23
         0x00, 0x00, 0x00, 0x00, 0x00, 0x80   // 29
     };
     inttype_t max_val;
     std::vector<settype_t> sieve;
     inttype_t nprimes;
     using lookup_t = std::tuple<inttype_t, settype_t>;
     inline lookup_t lookup(inttype_t val)
     {
         return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]);
     }
public:
     inline bool is_prime(inttype_t val)
     {
         const auto [index, mask] = lookup(val);
         return static_cast<bool>(sieve[index] & mask);
     }
     inline void mark_prime(inttype_t val)
     {
         ++nprimes;
         const inttype_t incr = val + val;
         for (inttype_t j = val + incr; j <= max_val; j += incr)
         {
             const auto [index, mask] = lookup(j);
             sieve[index] &= ~mask;
         }
     }
     inttype_t get_prime_count() { return nprimes; }
     Sieve(inttype_t max_)
         : max_val(max_)
         , sieve((max_ / MOD_VALUE) + 1, ~settype_t())
         , nprimes(3)
     {
     }
};
int main(int argc, char *argv[])
{
     std::vector<std::string> args(argv, argv+argc);
     constexpr inttype_t default_max = 100ull;
     inttype_t max_val = default_max;
     if (argc > 1)
     {
         max_val = std::stoull(args[1]);
         if (max_val == 0)
             max_val = default_max;
     }
     Sieve sieve(max_val);
     const auto start = std::chrono::steady_clock::now();
     for (inttype_t j = 7 ; j <= max_val ; j += 2)
     {
         if (sieve.is_prime(j))
         {
             sieve.mark_prime(j);
         }
     }
     const auto finish = std::chrono::steady_clock::now();
     const auto diff =
         std::chrono::duration_cast<std::chrono::microseconds>(finish - start);
     constexpr uint64_t us_per_sec = 1'000'000;
     auto us = diff.count();
     std::cout << sieve.get_prime_count()
         << " primes found less than "
         << max_val
         << " in "
         << (us / us_per_sec)
         << "."
         << std::setw(6)
         << std::setfill('0')
         << (us % us_per_sec)
         << "s\n";
     return 0;
}
-- CUT HERE ---

Date Sujet#  Auteur
30 Jun 24 * Re: Sieve of Erastosthenes optimized to the max54Vir Campestris
2 Jul 24 `* Re: Sieve of Erastosthenes optimized to the max53Tim Rentsch
2 Jul 24  +- Re: Sieve of Erastosthenes optimized to the max1Vir Campestris
3 Jul 24  `* Re: Sieve of Erastosthenes optimized to the max51Vir Campestris
15 Jul 24   +- Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
20 Jul 24   +* Re: Sieve of Erastosthenes optimized to the max48Tim Rentsch
25 Jul 24   i`* OT: Re: Sieve of Erastosthenes optimized to the max47Vir Campestris
10 Aug 24   i +* Re: OT: Re: Sieve of Erastosthenes optimized to the max44Tim Rentsch
12 Aug 24   i i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
16 Aug 24   i ii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
15 Aug 24   i i`* Re: OT: Re: Sieve of Erastosthenes optimized to the max41Vir Campestris
16 Aug 24   i i `* Re: OT: Re: Sieve of Erastosthenes optimized to the max40Tim Rentsch
16 Aug 24   i i  +* Re: OT: Re: Sieve of Erastosthenes optimized to the max38Bonita Montero
16 Aug 24   i i  i+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
19 Aug 24   i i  i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max19Vir Campestris
20 Aug 24   i i  ii`* Re: OT: Re: Sieve of Erastosthenes optimized to the max18Bonita Montero
20 Aug 24   i i  ii `* Re: OT: Re: Sieve of Erastosthenes optimized to the max17Bonita Montero
20 Aug 24   i i  ii  +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  ii  `* Re: OT: Re: Sieve of Erastosthenes optimized to the max15Vir Campestris
20 Aug 24   i i  ii   +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
26 Aug 24   i i  ii   `* Re: OT: Re: Sieve of Erastosthenes optimized to the max13Tim Rentsch
27 Aug 24   i i  ii    `* Re: OT: Re: Sieve of Erastosthenes optimized to the max12Bonita Montero
1 Sep 24   i i  ii     `* Re: OT: Re: Sieve of Erastosthenes optimized to the max11Vir Campestris
2 Sep 24   i i  ii      `* Re: OT: Re: Sieve of Erastosthenes optimized to the max10Tim Rentsch
2 Sep 24   i i  ii       +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
3 Sep 24   i i  ii       `* Re: OT: Re: Sieve of Erastosthenes optimized to the max8Vir Campestris
28 Sep 24   i i  ii        `* Re: OT: Re: Sieve of Erastosthenes optimized to the max7Tim Rentsch
28 Sep 24   i i  ii         `* Re: OT: Re: Sieve of Erastosthenes optimized to the max6Keith Thompson
2 Oct 24   i i  ii          `* Re: OT: Re: Sieve of Erastosthenes optimized to the max5Vir Campestris
2 Oct 24   i i  ii           +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
7 Oct 24   i i  ii           `* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Tim Rentsch
20 Oct 24   i i  ii            `* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
4 Nov 24   i i  ii             `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
19 Aug 24   i i  i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max12Vir Campestris
20 Aug 24   i i  ii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max4red floyd
20 Aug 24   i i  iii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
26 Aug 24   i i  iiii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
26 Aug 24   i i  iii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
20 Aug 24   i i  ii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Bonita Montero
20 Aug 24   i i  iii+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  iii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  ii`* Re: OT: Re: Sieve of Erastosthenes optimized to the max4Bonita Montero
22 Aug 24   i i  ii `* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Vir Campestris
22 Aug 24   i i  ii  `* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Bonita Montero
22 Aug 24   i i  ii   `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Vir Campestris
22 Aug 24   i i  i`* Re: OT: Re: Sieve of Erastosthenes optimized to the max5Vir Campestris
23 Aug 24   i i  i +* Re: OT: Re: Sieve of Erastosthenes optimized to the max3red floyd
26 Aug 24   i i  i i+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
28 Sep 24   i i  i i`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Andrey Tarasevich
26 Aug 24   i i  i `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
19 Aug 24   i i  `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
11 Aug 24   i +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
11 Aug 24   i `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
23 Jul 24   `- Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal