Changes in version 7.7, 13/11/2021 ================================== The CPU cache size detection has been improved. The code now better handles uncertain situations when CPU cache information is only partially available. If the CPU cache detection fails entirely, then the new code uses a larger sieve size (than before) that will most likely provide a significant speedup. Most BSD operating systems that are currently not supported in CpuInfo.cpp will benefit from this change. The behavior of the -q/--quiet option has been modified. Before it printed e.g. "Primes: 1229", while with the new behavior the "Primes:" label will not be printed anymore. Hence the new output will be "1229". This is a backwards incompatible change, however I won't increase primesieve's major version since this change does not affect primesieve's API/ABI. * CpuInfo.cpp: Fix issues with big.LITTLE CPUs #105. * api.cpp: Simplify private L2 cache size detection #103. * config.cpp: Add fallback sieve size & L1 data cache size. * Erat.cpp: If runtime CPU cache detection fails use config::L1D_CACHE_BYTES. * main.cpp: Improve -q/--quiet option #102. * api-c.cpp: Print error messages to stderr. * iterator-c.cpp: Print error messages to stderr. * doc/primesieve.1: Update man page. * CMakeLists.txt: Add WITH_MSVC_CRT_STATIC option to force static linking. * C_Examples.md: Add CMake build instructions. * CPP_Examples.md: Add CMake build instructions. Changes in version 7.6, 18/12/2020 ================================== * The primesieve GUI application has been deprecated/removed. It only works with QT4 which has reached end-of-life. * Get rid Travis-CI because it is not free anymore. * CpuInfo.cpp: Linux kernel CPU detection has been updated. * CpuInfo.cpp: Add workaround for sysctl bug (macOS & iOS). * Erat.hpp: Use CTZ instruction on x64 and ARM64 CPUs. * config.hpp: Tune FACTOR_ERATSMALL factor. * EratSmall.cpp: Get rid of goto. * EratSmall.cpp: Optimize switch statement. * EratSmall.cpp: Annotate switch cases with fallthrough. * EratMedium.cpp: Get rid of goto. * EratMedium.cpp: Optimize switch statements. * EratMedium.cpp: Annotate switch cases with fallthrough. * EratBig.cpp: Simplify main sieving loop. * doc/C_Examples.md: libprimesieve C code examples. * doc/CPP_Examples.md: libprimesieve C++ code examples. Changes in version 7.5, 27/12/2019 ================================== This is a minor new release, the API and ABI (Application binary interface) are backwards compatible. primesieve::iterator::next_prime() has been sped up by about 10%. Since primesieve::iterator is also used under the hood for generating an array (or vector) of primes that should also run slightly faster. I have also removed the https://primesieve.org website because it simply took too much effort to maintain it and make it look nice across all devices, operating systems and browsers. Hence primesieve's main homepage is now its GitHub repo: https://github.com/kimwalisch/primesieve * Erat.cpp: Silence MSVC debug warning. * StorePrimes.hpp: Add workaround for windows.h max/min macros. * PrimeGenerator.cpp: Cache more primes. * SievingPrimes.cpp: Cache more primes. * cmdoptions.cpp: Support options of type: --option VALUE. * help.cpp: Improve help menu. * CMakeLists.txt: Require CMake 3.4 instead 3.9. * primesieve.pc.in: Fix libdir and includedir. * README.md: Add libprimesieve multi-threading section. * BUILD.md: Add detailed build instructions. * doc/ALGORITHMS.md: Info from https://primesieve.org. * doc/primesieve.txt: New AsciiDoc man page. Changes in version 7.4, 10/02/2019 ================================== This is a minor new release, the API and ABI (Application binary interface) are backwards compatible. * CpuInfo.cpp: Fix MinGW CPU detection. * CMakeLists.txt: Fix cross compilation bug. * Add --test option: Runs self tests. * IteratorHelper.cpp: Improve caching of small primes. * ParallelSieve.cpp: Non-blocking status updates. * PrimeSieve.cpp: Simplify status update. * travis.yml: Test using GCC 5, 6, 7, 8, Clang 7 and MinGW. Changes in version 7.3, 04/01/2019 ================================== This is a minor new release, the API and ABI (Application binary interface) are backwards compatible. primesieve-7.3 improves the cache efficiency of the sieving algorithm 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. primesieve-7.2 features a new algorithm for medium sieving primes 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. primesieve-7.1 runs up to 30% faster on Intel Skylake-X CPUs! 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 ================================== primesieve-6.1 features run-time CPU cache size detection and 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 ================================== primesieve-6.0 is a major new release with many changes. The API and 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* 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* 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* 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 ================================== primesieve-5.1 is a minor new release with mostly bug fixes. There is also one API change in the C bindings documented further down. 1. and are now compatible with , 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 ================================== primesieve-5.0 is a major new release that makes using the primesieve library much more convenient. primesieve now includes C bindings for all of its functions so that it can easily be used in languages other than C++. I moved primesieve's build system to GNU Autotools and Libtool which is more reliable than the hand written Makefile I used previously. primesieve-5.0 features a new API completely written from scratch that is easier to use and that will not break binary compatibility with every new release. The new API is not backwards compatible but porting your code to the new API should be done quickly. You can explore primesieve's new API online at: http://primesieve.org/api. I bought a domain for primesieve and moved primesieve's repository from Google Code (SVN) to GitHub (git): http://primesieve.org http://github.com/kimwalisch/primesieve Other changes: 1. New primesieve::iterator class that provides next_prime() and previous_prime() methods. 2. ParallelPrimeSieve now uses multi-threading by default, it does not care about arithmetic order anymore. Please do not use ParallelPrimeSieve directly anymore instead use the new API. 3. Renamed src/soe to src/primesieve. 4. Renamed PrimeSieveCallback class to Callback. 5. Moved most header files to include/primesieve. Changes in version 4.4, 19/09/2013 ================================== This is a minor release whose sole purpose is to fix a bug in the Makefile which is required for integrating primesieve into Sage (http://www.sagemath.org). 1. Fixed the following bug: $ make shared && make install PREFIX=/user-path 2. PrimeSieve does not throw an exception anymore if (start > stop) instead it simply ignores the invalid input. 3. `make SHARED=yes` has been deprecated, use `make shared` instead. Changes in version 4.3, 05/07/2013 ================================== This release improves primesieve as a library and adds an algorithm to find the nth prime. The API of primesieve 4.3 is backwards compatible but the ABI is not (you must recompile your application if you want to link against a shared libprimesieve 4.3). 1. Support for storing primes in C++ vectors: PrimeSieve::generatePrimes (start, stop, std::vector*); PrimeSieve::generate_N_Primes(start, n, std::vector*); 2. New algorithm to find the nth prime: PrimeSieve::nthPrime(n); PrimeSieve::nthPrime(start, n); 3. The Makefiles now build primesieve and a static libprimesieve by default. A shared libprimesieve can be built using: $ make shared 4. Added a header for this commonly used exception to abort sieving. 5. Updated the documentation files: INSTALL, doc/API, doc/EXAMPLES doc/LIBPRIMESIEVE, doc/FAQ 6. Updated the source code examples in ./examples. 7. Added the scripts/install_primesieve.sh shell script that automatically downloads, builds and installs the latest primesieve and libprimesieve version. Changes in version 4.2, 10/03/2013 ================================== 1. libprimesieve generates (callback) primes up to 5% faster on little-endian CPUs (x86, x86-64) due to improved endiansafe_cast.h (src/soe). 2. The best pre-sieve setting is now automatically chosen at runtime, this speeds up sieving small intervals. 3. The Makefile now supports the Solaris OS. 4. Updated documentation: README, INSTALL, doc/EXAMPLES, doc/FAQ and doc/LIBPRIMESIEVE. New files: AUTHORS and THANKS. 5. Fixed a bug in the primesieve GUI code (doc/BUGS). 6. Updated ExpressionParser.h (src/apps/*) to version 2.5. 7. Added more example programs: examples/store_primes_in_vector.cpp and examples/nth_prime.cpp. 8. Lots of refactoring to make the code easier to understand. API changes ----------- The undocumented pre-sieve methods have been removed (pre-sieving is now automatically configured at runtime). void PrimeSieve::getPreSieve(); void PrimeSieve::setPreSieve(int); Changes in version 4.1, 12/01/2013 ================================== 1. New PrimeSieveCallback interface class that simplifies prime number generation with classes, see doc/EXAMPLES. 2. The primesieve console (terminal) application now supports GNU-style long options e.g. --size=256. 3. Fixed a bug (for sizeof(int) > 4) in the bit population count algorithm, read BUGS file. 4. Updated files: README, INSTALL, doc/EXAMPLES. 5. The Makefile now uses the system's default C++ compiler instead of GNU g++ which makes it more portable. 6. The primesieve_error class has been moved into its own file src/soe/primesieve_error.h (previously PrimeSieve.h). API changes ----------- The following two overly complex PrimeSieve methods have been removed: void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, void (*)(uint32_t, void*), void*); void PrimeSieve::generatePrimes(uint64_t start, uint64_t stop, void (*)(uint64_t, void*), void*); They are replaced by the following two new methods that greatly simplify prime number generation with classes, please refer to doc/EXAMPLES for more information. void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, PrimeSieveCallback*); void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, PrimeSieveCallback*); Changes in version 4.0, 18/10/2012 ================================== primesieve 4.0 is a major new release. A lot of work has been put into documentation and improving primesieve as a library. The API of primesieve 4.0 is backward incompatible with primesieve 3.*, the few changes are documented further down. 1. Added support for OpenMP 2.*, useful for compilers that do not support OpenMP >= 3.0, e.g. MSVC, Apple g++. 2. New examples directory with 12 simple example programs. 3. New doc/API file that lists the public member functions of the PrimeSieve and ParallelPrimeSieve C++ classes. 4. The Makefile is now POSIX compatible, it works with any POSIX shell e.g. sh, bash, ash, ksh, zsh, ... 5. The Makefile now supports MinGW (with MSYS) and Cygwin. 6. Fixed a shared libprimesieve bug (read doc/BUGS). 7. Up to 10 percent faster prime number generation due to new internal 64-bit getNextPrime() (previously 32-bit). 8. New unsynchronized ParallelPrimeSieve::generatePrimes() method that calls back primes in parallel (read EXAMPLES). 9. Faster thread synchronization in ParallelPrimeSieve, replaced slow OpenMP critical directive with faster omp_test_lock(). 10. Optimized prime k-tuplet (twin primes, ...) counting for out-of-order CPUs (src/soe/PrimeNumberFinder.cpp). 11. New primesieve_error() exception used for all exceptions within PrimeSieve and ParallelPrimeSieve (read EXAMPLES). 12. New pre-sieve code (src/soe/PreSieve.cpp). 13. Ported the primesieve GUI application from Qt 4 to Qt 5. API changes ----------- The PrimeSieve 3.* count methods: uint64_t getPrimeCount(uint64_t start, uint64_t stop); uint64_t getTwinCount (uint64_t start, uint64_t stop); ... Have been renamed to: uint64_t countPrimes (uint64_t start, uint64_t stop); uint64_t countTwins (uint64_t start, uint64_t stop); uint64_t countTriplets (uint64_t start, uint64_t stop); uint64_t countQuadruplets(uint64_t start, uint64_t stop); uint64_t countQuintuplets(uint64_t start, uint64_t stop); uint64_t countSextuplets (uint64_t start, uint64_t stop); uint64_t countSeptuplets (uint64_t start, uint64_t stop); Changes in version 3.8, 13/07/2012 ================================== 1. Improved OOP design of WheelFactorization.h. 2. Minor speed up for big sieving primes ~2% (src/soe/EratBig.cpp), reduced the number of operations in the main sieving loop. 3. Minor speed up for small sieving primes ~3% (src/soe/EraSmall.cpp), new inner sieving loop without instruction dependencies that uses only 12 asm instructions (previously 16). 4. Improved OpenMP load balance in src/soe/ParallelPrimeSieve.cpp. 5. Improved code readability of EratSmall.cpp, EratMedium.cpp, EratBig.cpp, Erat.cpp and others. 6. The Makefile now automatically detects the CPU's L1 data cache size on Unix-like OSes (Linux, Mac OS X). 7. Renamed ./docs to ./doc 8. Revised README.txt, added 7. Motivation. 9. Updated INSTALL, LIBPRIMESIEVE and EXAMPLES. 10. Added version #defines to PrimeSieve.h, e.g. for this release: #define PRIMESIEVE_VERSION "3.8" #define PRIMESIEVE_MAJOR_VERSION 3 #define PRIMESIEVE_MINOR_VERSION 8 #define PRIMESIEVE_YEAR 2012 Changes in version 3.7, 31/05/2012 ================================== 1. More aggressive inlining (*-inline.h), up to 10 percent faster prime number generation, up to 20 percent faster initialization. 2. Reduced header file dependencies, libprimesieve now only depends on PrimeSieve.h or ParallelPrimeSieve.h (and PrimeSieve.h). 3. Updated Makefiles. 4. New template imath.h functions: isqrt(), ilog2(), isPow2(), ... isqrt() has been rewritten using Newton's algorithm in order to avoid rounding errors of (int)sqrt((double)n) if n > 10^15. 5. New internal Erat::getNextPrime(...) member function. 6. Replaced old C-style comments with C++ comments. 7. Updated ExpressionParser to version 2.2. 8. uin32_t has been replaced by uint_t in src/soe/*. 9. New int API for PrimeSieve and ParallelPrimeSieve objects, getters and setters now use int instead of uint32_t. 10. Updated documentation files: README, INSTALL, LIBPRIMESIEVE, EXAMPLES, VALGRIND, TODO, BUGS. Changes in version 3.6, 22/04/2012 ================================== 1. Improved code readability and updated source code documentation (src/soe directory). 2. Removed unused source code. The deprecated API of PrimeSieve <= 3.4 is not supported anymore, use PrimeSieve::getStart() instead of PrimeSieve::getStartNumber() ... The file EXAMPLES contains the up-to-date API. 3. src/soe/EratSmall.cpp has been enhanced to better take advantage of Instruction-Level Parallelism. Changes in version 3.5, 07/02/2012 ================================== 1. Bug fix for big-endian CPUs (PowerPC, SPARC), see docs/BUGS. 2. The GNU Makefile now provides an option to build primesieve as a shared library e.g. `make lib SHARED=yes`. 3. I have rewritten the main documentation files docs/LIBPRIMESIEVE and docs/EXAMPLES. 4. I have added convenience functions to the PrimeSieve class: void printPrimes (uint64_t start, uint64_t stop); void printTwins (uint64_t start, uint64_t stop); void printTriplets (uint64_t start, uint64_t stop); void printQuadruplets(uint64_t start, uint64_t stop); void printQuintuplets(uint64_t start, uint64_t stop); void printSextuplets (uint64_t start, uint64_t stop); void printSeptuplets (uint64_t start, uint64_t stop); uint64_t getPrimeCount (uint64_t start, uint64_t stop); uint64_t getTwinCount (uint64_t start, uint64_t stop); uint64_t getTripletCount (uint64_t start, uint64_t stop); uint64_t getQuadrupletCount(uint64_t start, uint64_t stop); uint64_t getQuintupletCount(uint64_t start, uint64_t stop); uint64_t getSextupletCount (uint64_t start, uint64_t stop); uint64_t getSeptupletCount (uint64_t start, uint64_t stop); void sieve(uint64_t start, uint64_t stop); void sieve(uint64_t start, uint64_t stop, uint32_t flags); void sieve(); 5. src/soe/ParallelPrimeSieve.cpp has been rewritten using OpenMP 3.0 (previously OpenMP 2.0). The new OpenMP code is more elegant and scales better when lots of threads (> 32) are used. Compiler notes: OpenMP is now disabled by default for the Microsoft Visual C++ compiler as it currently only supports OpenMP 2.0. Some compilers e.g. g++ 4.2 even build primesieve with OpenMP <= 2.5 but the resulting binary miscalculates when sieving > 2^63. 6. Helper classes and functions within src/soe are now defined in the the newly introduced soe namespace. This makes PrimeSieve more usable as a library. 7. The header file src/soe/defs.h has been renamed to config.h and its code readability has been improved. 8. The code of src/console/test.cpp has been simplified. Changes in version 3.4, 05/01/2012 ================================== 1. I implemented a new algorithm for medium sieving primes that is up to 20 percent faster on todays out-of-order CPUs, see src/soe/EratMedium.cpp. 2. I adapted the constants in defs.h due to the new EratMedium algorithm, the maximum sieveSize is now 4096 kilobytes (previously 2048 kilobytes). 3. I revised the Makefiles and INSTALL file. 4. Added docs/LIBPRIMESIEVE and updated README and docs/EXAMPLES. Changes in version 3.3, 19/12/2011 ================================== 1. Minor optimizations in src/soe/EratBig.cpp (2% speed up). 2. Improved code readability and documentation of src/soe/ParallelPrimeSieve.cpp. 3. The sieveSize must be <= 2048 kilobytes now (previously 8192), this makes the WheelFactorization.h & EratBase.h code easier to understand. Changes in version 3.2, 13/11/2011 ================================== 1. Fixed a bug in src/soe/ParallelPrimeSieve.cpp, see ../docs/BUGS. 2. Added 32-bit prime number generation methods to PrimeSieve. 3. Added a PrimeSieve::cancel_sieving exception that allows to cancel sieving at run time (see docs/EXAMPLES). 4. ParallelPrimeSieve is now able to generate prime numbers using multiple threads (previously only multi-threaded counting). 5. The code readability and documentation of WheelFactorization.h/.cpp has been improved (e.g. renamed sieveIndex to multipleIndex). 6. PreSieve now initializes its preSieved_ array using a 2nd wheel (modulo 6), up to 40 percent faster. 7. I introduced a 'loopLimit' variable in EratSmall that saves some calculations and reduces the code size. 8. Added a testFlags(uint32_t) convenience function to PrimeSieve. 9. EratMedium has been simplified, it runs faster than v. 3.1 using Intel C++ 12.0 but slightly slower with most other compilers. Changes in version 3.1, 24/10/2011 ================================== 1. EratBig::sieve(uint8_t*) now processes multiple sieving primes per iteration, I measured a speed up of about 6 percent near 1E18. 2. STL containers are now used instead of dynamic memory allocation in Erat(Small|Medium) which improves multi-threading performance ~ 3%. 3. The Bucket data structure (WheelFactorization.h) has been modified and it performs well now with more compilers. 4. EratMedium has been simplifed, the new code is far easier to understand and it is faster with the GNU g++ compiler. 5. Fixed an integer overflow bug in EratMedium.cpp (see BUGS file). 6. The -test option (primesieve console) has been reviewed. 7. I improved the code readability and code documentation, the README and INSTALL files have also been revised. Changes in version 3.0, 09/07/2011 ================================== 1. The source code is now licensed under the New BSD License (previously GPL). 2. The source code is now standard C++03 and ISO C99 (stdint.h), i.e. I removed all compiler intrinsics and built-in functions: 80386 BSF, cpuid, SSE4.2 POPCNT. 3. The thread scheduling of ParallelPrimeSieve has been improved, 10 percent speed up. 4. Prime numbers are now generated using bitScanForward() instead of lookup tables, 10 percent speed up. 5. Implemented a fast bit population count function, see popcount_lauradoux() in bithacks.h. 6. Revised the option handling in the console version of primesieve, added two new options: -o and -r 7. README has been rewritten from scratch. 8. Improved the code readability and revised the comments of the sieve of Eratosthenes implementation. 9. ResetSieve has been renamed to PreSieve. Changes in version 2.2, 26/05/2011 ================================== 1. Added the file docs/EXAMPLES which shows how to use PrimeSieve and ParallelPrimeSieve objects. 2. Fixed 4 minor bugs (see BUGS). 3. 10% initialization speedup due to enhancement in ModuloWheel::setWheelPrime(uint64_t, uint32_t*, uint32_t*, uint32_t*) 4. Added prime number generation functions and a convenience function to count prime numbers to PrimeSieve. 5. The thread interface of ParallelPrimeSieve has been simplified. 6. The code now compiles and runs with the sunCC compiler. 7. The code readability has been improved. 8. The documentation has been updated. Changes in version 2.1, 11/04/2011 ================================== 1. Fixed a start number bug (read doc/BUGS). 2. Now supports integer arithmetic expressions as number input. 3. Uses OpenMP instead of processes. 4. Added qt-gui/README file. 5. Fixed a bug in the Makefile (clang++ compiler). 6. Updated the README file. Changes in version 2.0, 15/02/2011 ================================== 1. Added soe/ParallelPrimeSieve.cpp which counts primes in parallel using OpenMP. 2. Added an arithmetic expression parser (./expr) to ease number input. 3. Added a test suite to the console version of primesieve (option: -test) which runs various correctness tests. 4. The console version has been reviewed and is first released. 5. Fixed a minor bug in soe/PrimeNumberFinder.cpp which counts and prints the prime preceding the start number (see BUGS file). 6. Improved the memory pool of soe/EratBig.cpp, primesieve 1.0 ran into trouble when sieving near 2^64. 7. Makefile modified to better support GCC compatible compilers, e.g. make CXX=x86_64-w64-mingw32-g++