yase is a Sieve of Eratosthenes-based single-threaded prime finding program. It is invoked with a single argument, which gives the highest number to be checked for primality. It currently employs the following methods to speed up its computations:
- Efficient implementation of modulo 210 wheel factorization
- Segmented sieve that fits in CPU L1 data cache
- Use of an efficient lookup table to count primes after sieving
- Processing of two sieving primes at once, to leverage instruction-level parallelism
- Pre-sieving of multiples of the first few sieving primes
- Specialized, highly-optimized sieve for small sieving primes
- Sorting of large sieving primes based on the next segment in which they appear
- Storage of sieving primes in linked lists of "buckets" containing many primes each
Additionally, each byte of the bit array used to sieve for primes covers a range of 30 numbers. With a 32 KB sieve (fitting a common CPU L1 data cache size), this gives a total range of 983,040 numbers checked per segment sieved.
Many of the ideas in this program are taken from other prime-sieving programs, especially primesieve. The ideas of sorting large sieving primes and bucket storage come from Tomás Oliveira e Silva. These ideas are described at his web page here.
yase is built using CMake. Before you build,
copy config.cmake.default to config.cmake and make any edits you
desire. Each configuration item in config.cmake.default is documented
in-line and set to a reasonable default value. After you finish, run
CMake to generate the build files, and build using whatever build
environment you had CMake target.
It is possible to perform out-of-source builds of yase with CMake. Just
make sure to place config.cmake in your build directory, not the yase
source distribution.
Additionally, you can use CPack to create binary or source distributions
of yase if you desire. The default CPack configurations generated by
CMake will have CPack build .tar.gz, .tar.bz2, and .zip archives
of each distribution type. It should also be possible to produce
.deb (dpkg) and .rpm (RPM) binary packages.
yase has only been tested using GCC and Clang. However, yase is written in portable C99, and should work with other C99 compilers. Some manual configuration of compiler flags (to turn on C99, if necessary, and enable warnings) will be necessary in these cases.