Re: OT: Re: Sieve of Erastosthenes optimized to the max
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, 06: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 ---
Haut de la page
Les messages affichés proviennent d'usenet.
NewsPortal