Primesieve

for large sieving primes. By using aligned memory it is possible
to reduce the number of pointer indirections which reduces cache
pollution. I have measured a speed up of 15% near 1e18 and a speed up
of 25% near 1e19.

* EratBig.cpp: Improve cache efficiency.
* MemoryPoop.cpp: Allocate buckets aligned by sizeof(Bucket).
* Bucket.hpp: sizeof(Bucket) is now a power of 2.
* primesieve::iterator: Support C++ move semantics.
* cmdoptions.cpp: Fix array out of bounds bug.
* CpuInfo.cpp: Fix MinGW/MSYS2 -Wcast-function-type warning.

Changes in version 7.2, 26/10/2018
==================================

This is a minor new release, the API and ABI (Application binary
interface) are backwards compatible.

that improves the CPU's branch prediction rate by sorting the sieving
primes (before using them). On AMD EPYC CPUs I have measured a
speedup of up to 15% and on Intel Skylake CPUs I have measured a
speedup of up to 10%. Ever since primesieve was created in 2010 its
algorithm for medium sieving primes has been slower than yafu's
algorithm for medium sieving primes. This performance issue has now
been fixed!

* EratMedium.cpp: New faster sieving algorithm.
* EratSmall.cpp: Slightly reduce the number of instructions.
* MemoryPool.cpp: Move memory pool into its own class.
* CMakeLists.txt: Add support for primesieve.dll.

Changes in version 7.1, 19/08/2018
==================================

This is a minor new release, the API and ABI (Application binary
interface) are backwards compatible.

The default sieve size is now (L2 cache size / 2). Using a sieve size
that is slightly smaller than the L2 cache size reduces the number
of L2 cache misses which improves performance on CPUs with slow L3
caches. primesieve-7.1 will also run slightly faster (< 3%) on most
other Intel CPUs.

* api.cpp: Default sieve size = (L2 cache size / 2).
* CpuInfo.cpp: Improved CPU info detection.
* Erat.cpp: Lazy PreSieve initialization.
* EratSmall.cpp: Fix too large sieve size.
* help.cpp: Update help menu (--help).
* ParallelSieve.cpp: Improved load balancing.
* --cpu-info: New option, prints CPU information.
* Rename kilobytes to KiB because it is more accurate.
* Faster Windows binary built using clang-cl.

Changes in version 7.0, 25/04/2018
==================================

This is a major new release, the API is backwards compatible but the
ABI (Application binary interface) is not backwards compatible.

primesieve's core algorithms have been rewritten using next_prime()
instead of callbacks. The benefit of this redesign is a much improved
primesieve::iterator that runs up to twice as fast and uses only
half as much memory as before!

* primesieve::iterator: Faster next_prime().
* primesieve::iterator: Cache small primes in lookup table.
* PrimeGenerator.cpp: Incrementally store primes in a vector.
* StorePrimes.hpp: Use primesieve::iterator instead of callbacks.
* SievingPrimes.hpp: Use next_prime() instead of callbacks.
* Reduce number of memory allocations by up to 30%.
* Modernize code base using C++11.
* Test suite runs up to twice as fast.

Breaking ABI Changes:

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

Changes in version 6.4, 23/03/2018
==================================

This is a minor new release, the API and ABI are backwards compatible.

* Switch to https: https://primesieve.org.
* Faster printing to stdout.
* Required CMake version is now 3.4 (previously 3.1)
* CMakeLists.txt: Support find_package(primesieve).
* CMakeLists.txt: Add Fedora multiarch support.
* CMakeLists.txt: Fix libatomic detection.
* CMakeLists.txt: Fix make install issue.
* calculator.hpp: Fix integer overflow.
* test/calculator.cpp: Add test for expression parser.

Breaking Changes:

The 2 changes below may potentially break the build of projects that
have hardcoded the src/primesieve path and/or the
src/primesieve/README filename in their build script.

* Move libprimesieve sources from ./src/primesieve to ./src.
* Rename src/primesieve/README to src/README.md.

Changes in version 6.3, 12/11/2017
==================================

This is a minor new release, the API and ABI are
backwards compatible.

* test/ilog2.cpp: Fix Linux i386 bug.
* test/floorPower2.cpp: Fix Linux i386 bug.
* CMakeLists.txt: Link against libatomic if needed.
* CMakeLists.txt: Add Debian Multiarch support.

Changes in version 6.2, 12/10/2017
==================================

This is a minor new release which fixes 2 bugs and improves
the primesieve GUI app. The API and ABI are backwards
compatible.

* pmath.hpp: Fix integer overflow.
* EratMedium.cpp: Fix vector out of bounds bugs.
* primesieve GUI app: Silence GCC 7 warnings.
* PrimeSieveGUI.cpp: Add option to sieve using
(CPU cores / 2) threads.

Changes in version 6.1, 12/08/2017
==================================

an L2 cache size optimization contributed by Huang YuanBing
which speeds up sieving by up to 20% on recent CPUs (>= 2012).
By default primesieve now uses a sieve size that fits into the
CPU's L1 cache for small sieving primes and a sieve size that
fits into the CPU's L2 cache for medium and big sieving
primes.

The API and ABI are backwards compatible.

1. CpuInfo.cpp: Runtime CPU cache size detection.
2. api.cpp: sieve size = L2 cache size.
3. EratSmall.cpp: L1 cache size optimization.
4. EratMedium.cpp: Reduce allocations.
5. Silence GCC 7 warnings.
6. Fix GCC 7 performance regression.

Changes in version 6.0, 01/05/2017
==================================

ABI are not backwards compatible, see the "API changes" sections
further down for more information.

1. Use CMake build system instead of Autotools.
2. Use C++11 instead of C++98.
3. Use C++11 threads instead of OpenMP.
4. C/C++ API is now parallel by default.
5. Add many C/C++ libprimesieve tests (./test).
6. Improved error messages.

C++ API changes
---------------

The C++ API is now parallel by default i.e. the
primesieve::count_*() and primesieve::nth_prime() functions use all
CPU cores. Hence the old primesieve::parallel_*() functions have been
removed.

Removed from C++ API:

uint64_t parallel_count_primes(uint64_t start, uint64_t stop);
uint64_t parallel_count_twins(uint64_t start, uint64_t stop);
uint64_t parallel_count_triplets(uint64_t start, uint64_t stop);
uint64_t parallel_count_quadruplets(uint64_t start, uint64_t stop);
uint64_t parallel_count_quintuplets(uint64_t start, uint64_t stop);
uint64_t parallel_count_sextuplets(uint64_t start, uint64_t stop);
uint64_t parallel_nth_prime(int64_t n, uint64_t start = 0);

void callback_primes(uint64_t start, uint64_t stop, void (*callback)(uint64_t prime));
void callback_primes(uint64_t start, uint64_t stop, primesieve::Callback<uint64_t>* callback);
bool primesieve_test();

C API changes
-------------

The C API is now parallel by default i.e. the
primesieve_count_*() and primesieve_nth_prime() functions use all
CPU cores. Hence the old primesieve_parallel_*() functions have been
removed.

Removed from C API:

uint64_t primesieve_parallel_count_primes(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_twins(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_triplets(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_quadruplets(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_quintuplets(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_sextuplets(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_nth_prime(int64_t n, uint64_t start);

void primesieve_callback_primes(uint64_t start, uint64_t stop, void (*callback)(uint64_t prime));
int primesieve_test();

Changes in version 5.7.3, 19/11/2016
====================================

The API and ABI are backwards compatible.

1. New ./configure option: --enable-maintainer-mode
If this option is used the primesieve man page will be
regenerated in the make step.
See doc/README.md for more information.

Changes in version 5.7.2, 21/08/2016
====================================

The API and ABI are backwards compatible.

1. doc/primesieve.1: Add primesieve man page.
2. configure.ac: Add --with-help2man option to regenerate man page.
3. scripts/update_version.sh: Script that automatically updates the
version in all files, see RELEASE.md for more information.

Changes in version 5.7.1, 13/08/2016
====================================

The API and ABI are backwards compatible.

1. New --no-status command-line option to turn off the progressing
status while counting primes or prime k-tuplets.
2. README.md: New "Package managers" section.

Changes in version 5.7.0, 31/07/2016
====================================

1. primesieve can now find primes up to 2^64-1 (UINT64_MAX), the
previous limit was 2^64 - 2^32 * 10. Thanks to Huang Yuanbing
(author of ktprime) for submitting the patch.
2. Cleaned up pre-sieving: uses less memory + faster initialization.
3. Faster primesieve::iterator initialization.

C/C++ API changes
-----------------

The MAX_THREADS constant has been removed.

Changes in version 5.6.0, 29/11/2015
====================================

1. The C API prime generation functions now return true C arrays which
can be deallocated using free() in the user's code.
2. New high resolution icon size for primesieve GUI app.
3. primesieve GUI app: Bug fix for CPUs with L1 data cache size that
is not a power of 2 e.g. Intel Z2480 Atom (24 KB L1 cache).
4. Renamed doxygen directory to doc.
5. doc/Doxyfile.in: Fix out of source builds.

C++ API changes
---------------

All parallel callback functions have been removed. This was just crazy
functionality which I should never have implemented ...

void parallel_callback_primes(uint64_t start, uint64_t stop, void (*callback)(uint64_t prime));
void parallel_callback_primes(uint64_t start, uint64_t stop, primesieve::Callback<uint64_t>* callback);
void parallel_callback_primes(uint64_t start, uint64_t stop, void (*callback)(uint64_t prime, int thread_id));
void parallel_callback_primes(uint64_t start, uint64_t stop, primesieve::Callback<uint64_t, int>* callback);

C API changes
-------------

All parallel callback functions have been removed:

void primesieve_parallel_callback_primes(uint64_t start, uint64_t stop, void (*callback)(uint64_t prime, int thread_id));


Changes in version 5.5.0, 06/11/2015
====================================

This release contains many small incremental improvements. There are
2 minor backwards incompatible API changes which are described further
down.

1. primesieve GUI app: Runtime detection of CPU L1 cache size.
2. primesieve.pc.in: Added support for pkg-config.
3. appveyor.yml: Automated Windows (MSVC++) testing.
4. README.md: New "Bindings for other languages" section.
5. include/config.h: tune for Intel Skylake CPUs.
6. include/WheelFactorization.hpp: Slightly faster initialization.
7. src/primesieve/EratMedium.cpp: Unroll sieving loop, up to 5% speed up.
8. src/primesieve/popcount.cpp: Faster popcount algorithm.
9. examples/c/previous_prime.c: Shows how to use primesieve_previous_prime().

C++ API changes
---------------

primesieve::test() has been renamed to primesieve::primesieve_test()
in order to prevent naming collisions.

primesieve::iterator::previous_prime() now returns 0 if input <= 2,
previously an error was thrown. Rationale of this change:
https://github.com/kimwalisch/primesieve/issues/11#issuecomment-148939336

C API changes
-------------

primesieve_previous_prime() now returns 0 if input <= 2, previously
PRIMESIEVE_ERROR was returned. Rationale of this change:
https://github.com/kimwalisch/primesieve/issues/11#issuecomment-148939336

Changes in version 5.4.2, 04/04/2015
====================================

This is a minor new release, the API and ABI are backwards compatible.

1. Use silent building on Unix-like operating systems.
2. Add screenshot to README.md.
3. Makefile.am: Add autogen.sh to EXTRA_DIST.

Changes in version 5.4.1, 09/11/2014
====================================

This is a minor new release, the API and ABI are backwards compatible.

1. Fixed a bug in the configure.ac script which used SIEVESIZE=0
instead of SIEVESIZE=32 on QEMU virtual machines.
2. Introduce patch version (3rd version number) in order not to
increase the minor version for bug fix only releases.

Changes in version 5.4, 14/09/2014
==================================

This is a minor new release which fixes two bugs in the computation of
prime k-tuplets (twin primes, prime triplets, ...).

1. The primesieve::print_*() functions for prime k-tuplets have been
fixed, they were broken since primesieve-5.1.
https://github.com/kimwalisch/primesieve/commit/ff2fb6f7acfb7c83827803dbb09a73f4a47ab222

2. Prime 7-tuplets have been removed from primesieve (see API changes
further down). Below are the two modulo 30 patterns for prime
7-tuplets:

1) 30*k + { 7, 11, 13, 17, 19, 23, 29}
2) 30*k + {29, 31, 37, 41, 43, 47, 49}

Up until now primesieve only found prime 7-tuplets of the first
pattern e.g. it missed 5610 + {29, 31, ...}. Unfortunately this bug
cannot be fixed because of implementation constraints. Thus I have
decided to completely remove prime 7-tuplets from primesieve.

C++ API changes
---------------

All functions related to prime 7-tuplets have been removed:

uint64_t primesieve::print_septuplets(uint64_t start, uint64_t stop);
uint64_t primesieve::count_septuplets(uint64_t start, uint64_t stop);
uint64_t primesieve::parallel_count_septuplets(uint64_t start, uint64_t stop);

C API changes
-------------

All functions related to prime 7-tuplets have been removed:

uint64_t primesieve_print_septuplets(uint64_t start, uint64_t stop);
uint64_t primesieve_count_septuplets(uint64_t start, uint64_t stop);
uint64_t primesieve_parallel_count_septuplets(uint64_t start, uint64_t stop);

Changes in version 5.3, 06/07/2014
==================================

This is a minor new release with an important bug fix and improved
documentation, the API and ABI are backwards compatible.

1. Fix use of uninitialized variable bug in primesieve::iterator:
https://github.com/kimwalisch/primesieve/commit/006d572ea8fa4958eaf46c1db24c983b1ce27e1b
2. README.md update: Explain how to build from master-branch.
3. New file HACKING.md: Explains source tree, useful for developers.

Changes in version 5.2, 13/04/2014
==================================

1. Added backwards nth prime search, if n < 0
primesieve::nth_prime(int64_t n, uint64_t start);
will find the nth prime < start.
2. Faster nth prime implementation, more accurate guessing of the nth
prime gives up to 20% speed up if n < 10^8.
3. Added continuous integration testing with Travis (travis-ci.org),
files: .travis.yml, Readme.md (shows build status).

API changes!!!

In order to be compatible with other mathematical software like
Mathematica, Maple and SymPy the functions below have been modified
to return a prime > start (or < start), previously these functions
returned a prime >= start (or <= start).

uint64_t primesieve::nth_prime(int64_t n, uint64_t start);
uint64_t primesieve::iterator::next_prime();
uint64_t primesieve::iterator::previous_prime();

Changes in version 5.1, 14/02/2014
==================================

also one API change in the C bindings documented further down.

1. <primesieve.hpp> and <primesieve.h> are now compatible with
<windows.h>, fixed CALLBACK and max() issues.
2. Fixed bug in primesieve::iterator::previous_prime().
3. Fixed bug in primesieve_previous_prime().
4. Added stop_hint optimization to primesieve::iterator which gives a
significant speed up if only few primes are generated.
5. Replaced GENERATE_PRIMES() macro by templatized callbackPrimes()
method (src/primesieve/PrimeFinder.cpp).

C bindings API change:

void primesieve_skipto(primesieve_iterator* pi, uint64_t start, uint64_t stop_hint);

The signature of the primesieve_skipto() function has changed, a new
'stop_hint' parameter has been added. Please refer to
http://primesieve.org/api/primesieve__iterator_8h.html for more
information.

Changes in version 5.0, 11/01/2014
==================================