primecount-9.0

This is a new major release. The public C and C++ APIs and ABI remain backwards compatible with primecount-8.x. We bumped the major version to highlight the significant algorithmic improvements in this release.

Key Improvements

primecount-9.0 introduces a new algorithm for computing the hard special leaves in Gourdon’s prime counting algorithm, contributed by @ChopperLin in #146. Computing these leaves is one of the most time consuming parts of combinatorial prime counting algorithms, traditionally requiring repeated counts of the unsieved numbers in a segmented sieve. In 2001, Xavier Gourdon improved the Deléglise-Rivat algorithm by using an inversion formula based on the Dirichlet hyperbola method, which reduces the number of easy special leaves that need to be computed. primecount's new algorithm applies a weighted version of the hyperbola method to the hard special leaves. For many hard special leaves, the expensive sieve counting operations cancel out and are replaced by fast π(x) table lookups. This improves primecount's overall performance by up to 35% for large x.

This release also includes several other significant improvements:

• Added AVX2 filtering for Gourdon's D formula #147.
• SIMD runtime dispatching is now also supported for the MSVC compiler #144.
• Faster reciprocal-based integer division using the new FastDivider.hpp implementation #150.
• Improved thread load balancing #153 and smoother progress reporting 0981e7f.

Breaking Changes

1. primecount-9.0 replaces the libdivide C/C++ library with its own custom FastDivider.hpp implementation. Consequently, the CMake build option WITH_LIBDIVIDE has been renamed to WITH_FASTDIVIDER.
2. The primecount command-line program no longer accepts the --alpha-y and --alpha-z options. Use the existing --alpha option to tune Gourdon's algorithm instead.

The public C and C++ APIs and ABI remain backwards compatible with primecount-8.x.