Skip to content

Latest commit

 

History

History
 
 

src

README.md

C++ classes

  • PrimeSieve is a high level class that coordinates prime sieving. It is used for printing and counting primes and for computing the nth prime. PrimeSieve's main method is PrimeSieve::sieve(start, stop) which sieves the primes inside the interval [start, stop]. This class is mainly used by the primesieve command-line app.

  • ParallelSieve launches multiple threads using std::async and each thread sieves a part of the interval [start, stop] using a PrimeSieve object. At the end all partial results are combined to get the final result. This class is mainly used by the primesieve command-line app.

  • Erat is an implementation of the segmented sieve of Eratosthenes using a bit array with 30 numbers per byte, each byte of the sieve array holds the 8 offsets k = { 7, 11, 13, 17, 19, 23, 29, 31 }. Its main methods are addSievingPrime(prime) which is called consecutively for all primes ≤ sqrt(n) and sieveSegment() which sieves the next segment. Erat uses the EratSmall, EratMedium and EratBig classes to cross-off multiples.

  • EratSmall is a segmented sieve of Eratosthenes algorithm with a hard-coded modulo 30 wheel that skips multiples of 2, 3 and 5. This algorithm is optimized for small sieving primes that have many multiples in each segment. EratSmall is a further optimized implementation of Achim Flammenkamp's algorithm [1].

  • EratMedium is a segmented sieve of Eratosthenes algorithm with a hard-coded modulo 30 wheel that skips multiples of 2, 3 and 5. EratMedium is similar to EratSmall except that in EratMedium each sieving prime is sorted (by its wheelIndex) after the sieving step. When we then iterate over the sorted sieving primes in the next segment the initial indirect branch switch (wheelIndex) is predicted correctly by the CPU which gives a speedup of about 20% for medium sieving primes that have a few multiples per segment.

  • EratBig is a segmented sieve of Eratosthenes algorithm with Tomás Oliveira's improvement for big sieving primes [2] and a modulo 210 wheel that skips multiples of 2, 3, 5 and 7. The wheel is implemented using the precomputed wheel210 lookup table. EratBig is optimized for big sieving primes that have very few multiples per segment.

  • MemoryPool is used to reduce the number of memory allocations in EratMedium and EratBig. Up to 1024 sieving primes are stored in a bucket. Whenever the EratMedium and EratBig algorithms run out of buckets for storing sieving primes they request a new bucket from the MemoryPool. The MemoryPool has a stock of buckets and only when there are no more buckets in the stock the MemoryPool will allocate new buckets.

  • PreSieve is used to pre-sieve multiples of small primes ≤ 163 to speed up the sieve of Eratosthenes. The PreSieveTables.hpp header contains 16 static lookup tables which have been sieved using the primes ≤ 163. The total size of all pre-sieve lookup tables is about 123 kilobytes. Whilst sieving, we perform a bitwise AND of the pre-sieve lookup tables and store the result in the sieve array. Pre-sieving provides a speedup of up to 30% when sieving the primes < 10^10.

  • SievingPrimes is used to generate the sieving primes ≤ sqrt(stop). SievingPrimes is used by the CountPrintPrimes and PrimeGenerator classes.

  • CountPrintPrimes is used for counting primes and for printing primes to stdout. After a segment has been sieved (using Erat) CountPrintPrimes is used to reconstruct primes and prime k-tuplets from 1 bits of the sieve array. This class is mainly used by the primesieve command-line app.

  • PrimeGenerator is derived from Erat. primesieve::iterator uses PrimeGenerator under the hood: PrimeGenerator generates a few primes and stores them in a vector, next primesieve::iterator iterates over the vector and returns the primes. When there are no more primes left in the vector PrimeGenerator generates new primes.

  • primesieve::iterator allows to easily iterate over primes. It  provides next_prime() and prev_prime() methods. primesieve::iterator is also used for storing primes in a vector or an array.

  • CpuInfo is used to get the CPU's L1 and L2 cache sizes. The best prime sieving performance is achieved using a sieve array size that matches the CPU's L1 or L2 cache size (depending on the CPU type).

  • Wheel factorization is used to skip multiples of small primes ≤ 7 to speed up the sieve of Eratosthenes. The Wheel class is used to initialize sieving primes i.e. Wheel::addSievingPrime() calculates the first multiple ≥ start of each sieving prime and the position within the sieve array of that multiple. The EratSmall, EratMedium and EratBig classes are derived from Wheel.

References

  1. Achim Flammenkamp, "The Art of Prime Sieving", 1998.
    https://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
  2. Tomás Oliveira e Silva, "Fast implementation of the segmented sieve of Eratosthenes", 2002.
    http://www.ieeta.pt/~tos/software/prime_sieve.html