Skip to content

Latest commit

 

History

History
218 lines (169 loc) · 8.13 KB

libprimecount.md

File metadata and controls

218 lines (169 loc) · 8.13 KB
Raw

libprimecount

primecount can be built as a static and shared C/C++ library for use in other math projects. libprimecount has both a C API (<primecount.h> header) and a C++ API (<primecount.hpp> header) so you are free to pick the one that best fits your needs. The C API has been added to make it easier to write libprimecount bindings for other programming languages.

primecount's prime counting function implementation and nth prime function are generally orders of magnitude faster than other publicly available prime counting function implementations. As of 2021 libprimecount is the only prime counting function library that I am aware of that supports multi-threading. libprimecount is also very portable, it has been tested successfully on a wide range of operating systems, compilers (GCC, Clang, MSVC) and CPU architectures (x86, x64, ARM, ARM64, PowerPC, PP64, Sparc).

libprimecount has been integrated into a few other computer algebra systems: Since 2021 Mathematica's PrimePi(x) uses libprimecount under the hood, primecount is available as an optional package in SageMath and there are bindings available for a few other programming languages. If your company uses primecount then I would greatly appreciate if you would sponsor its maintenance (or donate). The development of primecount has personally cost me a lot of money, as I frequently needed to run extensive benchmarks on a wide variety of high end cloud servers.

Installation

C API reference

Include the <primecount.h> header to use primecount's C API. All functions that are part of primecount's C API return -1 in case an error occurs and print the corresponding error message to the standard error stream.

// Count the number of primes <= x
int64_t primecount_pi(int64_t x);

// Count the number of primes <= x (supports 128-bit)
int primecount_pi_str(const char* x, char* res, size_t len);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount_nth_prime(int64_t n);

// Count the numbers <= x that are not divisible by any of the first a primes
int64_t primecount_phi(int64_t x, int64_t a);

Please see primecount.h for more information.

C example

The C example below counts the primes ≤ 1000 and prints the result to the screen. Note that primecount is multi-threaded by default, it uses all available CPU cores if the input is sufficiently large.

#include <primecount.h>
#include <stdio.h>

int main()
{
    int64_t pix = primecount_pi(1000);
    printf("primes below 1000 = %ld\n", pix);

    return 0;
}

Compile using:

cc -O3 primes.c -o primes -lprimecount

If you have built libprimecount yourself, then the default installation path is usually /usr/local/lib. Running the ldconfig program after make install ensures that Linux's dynamic linker/loader will find the shared primecount library when you execute your program. However, some OSes are missing the ldconfig program or ldconfig does not include /usr/local/lib by default. In these cases you need to export some environment variables:

export LIBRARY_PATH=/usr/local/lib:$LIBRARY_PATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
export C_INCLUDE_PATH=/usr/local/include:$C_INCLUDE_PATH

C++ API reference

Include the <primecount.hpp> header to use primecount's C++ API. All functions that are part of primecount's C++ API throw a primecount_error exception (which is derived from std::exception) in case an error occurs.

// Count the number of primes <= x
int64_t primecount::pi(int64_t x);

// Count the number of primes <= x (supports 128-bit)
std::string primecount::pi(const std::string& x);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount::nth_prime(int64_t n);

// Count the numbers <= x that are not divisible by any of the first a primes
int64_t primecount::phi(int64_t x, int64_t a);

Please see primecount.hpp for more information.

C++ example

The C++ example below counts the primes ≤ 1000 and prints the result to the screen. Note that primecount is multi-threaded by default, it uses all available CPU cores if the input is sufficiently large.

#include <primecount.hpp>
#include <iostream>

int main()
{
    int64_t pix = primecount::pi(1000);
    std::cout << "primes below 1000 = " << pix << std::endl;

    return 0;
}

Compile using:

c++ -O3 primes.cpp -o primes -lprimecount

If you have built libprimecount yourself, then the default installation path is usually /usr/local/lib. Running the ldconfig program after make install ensures that Linux's dynamic linker/loader will find the shared primecount library when you execute your program. However, some OSes are missing the ldconfig program or ldconfig does not include /usr/local/lib by default. In these cases you need to export some environment variables:

export LIBRARY_PATH=/usr/local/lib:$LIBRARY_PATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
export CPLUS_INCLUDE_PATH=/usr/local/include:$CPLUS_INCLUDE_PATH

Build instructions

You need to have installed a C++ compiler, cmake and make. By default, only the static libprimecount is built, but for doing development with libprimecount you will most likely want to use the shared libprimecount. Hence we use the -DBUILD_SHARED_LIBS=ON option to enable building libprimecount as a shared library.

cmake . -DBUILD_SHARED_LIBS=ON
make -j
sudo make install
sudo ldconfig

Maximum portability

For performance reasons primecount uses the POPCNT instruction on all CPU architectures that support it. Enabling the POPCNT instruction usually improves primecount's performance by about 30%.

On x86/x64 CPUs primecount will by default detect at build time if the host CPU supports the POPCNT instruction. If not, the POPCNT instruction will be disabled and a portable alternative algorithm will be used. If you need to build a portable primecount binary package for x86/x64 CPUs that can be distributed to many different PCs, even very old ones without POPCNT support (2008 or earlier), you need to disable the POPCNT instruction at build time. Note that disabling POPCNT only has an effect on x86/x64, on other CPU architectures POPCNT is always used if it is available (as this generally does not cause any issues).

cmake . -DWITH_POPCNT=OFF

CMake build options

Here are all available cmake configuration options:

option(BUILD_PRIMECOUNT    "Build the primecount binary"           ON)
option(BUILD_LIBPRIMESIEVE "Build libprimesieve"                   ON)
option(BUILD_SHARED_LIBS   "Build the shared libprimecount"        OFF)
option(BUILD_STATIC_LIBS   "Build the static libprimecount"        ON)
option(BUILD_MANPAGE       "Regenerate man page using a2x program" OFF)
option(BUILD_TESTS         "Build the test programs"               OFF)

option(WITH_POPCNT          "Use the POPCNT instruction"            ON)
option(WITH_LIBDIVIDE       "Use libdivide.h"                       ON)
option(WITH_OPENMP          "Enable OpenMP multi-threading"         ON)
option(WITH_DIV32           "Use 32-bit division instead of 64-bit division whenever possible" ON)
option(WITH_MSVC_CRT_STATIC "Link primecount.lib with /MT instead of the default /MD" OFF)
option(WITH_FLOAT128        "Use __float128 (requires libquadmath)" OFF)
option(WITH_JEMALLOC        "Use jemalloc allocator"                OFF)