primesieve-7.0

Performance improvements

The next_prime() function of primesieve::iterator has been improved.

Up until now libprimesieve sieved an interval of size sqrt(n) and stored the primes inside that interval in an array. next_prime() then iterated over the primes in the array. Once there were no more primes available in the array libprimesieve regenerated new primes which incurred an initialization overhead of sqrt(n) * log log sqrt(n) operations to recompute the sieving primes. This initialization overhead has been removed in primesieve-7.0 which gives a 2x speed improvement for next_prime() when iterating over primes ≥ 10^15.

next_prime() benchmark

Start	primesieve 7.0	primesieve 6.4	primegen 0.97	Math-Prime-Util-GMP
0	2.66 sec	3.42 sec	7.50 sec	15.26 sec
1010	2.82 sec	3.53 sec	7.36 sec	17.98 sec
1011	3.19 sec	3.89 sec	7.31 sec	27.05 sec
1012	3.46 sec	4.51 sec	7.70 sec	51.59 sec
1013	3.97 sec	5.63 sec	10.06 sec	112.59 sec
1014	4.46 sec	8.41 sec	17.60 sec	285.31 sec
1015	4.97 sec	10.70 sec	41.45 sec	813.77 sec
1016	5.56 sec	11.29 sec	122.44 sec	2,439.96 sec
1017	6.29 sec	11.69 sec	508.56 sec	9,115.23 sec
1018	7.61 sec	12.24 sec	2,986.10 sec	NaN

primesieve, primegen and Math-Prime-Util are the fastest open source prime number generation libraries. The benchmark above has been run on an Intel Core-i7 6700 CPU and all libraries have been compiled using GCC 8 with -O3. At each start offset the benchmark programs iterated over the primes inside an interval of size 10^10 using next_prime().

API Changes

None, the API is backwards compatible with primesieve-6.x.

Breaking ABI Changes

New variables have been added to the C++ primesieve::iterator class and the C primesieve_iterator struct. Hence applications that link against the shared libprimesieve need to be recompiled. Users that have written primesieve bindings for other programming languages are affected by these ABI changes and need to update their code.