Int — Arbitrary-Precision Integer

Overview

Int is an arbitrary-precision integer class comparable to Python's int or Java's BigInteger. It is designed for fields such as cryptography, number theory, and combinatorics where C++ built-in types (int, int64_t) cannot represent sufficiently large integers, as well as for use as a foundation for high-precision floating-point arithmetic.

The low-level routines are written in assembly language, and automatic algorithm selection based on operand size ensures high performance.

Values are represented as a variable-length array of 64-bit words, with no upper limit on the number of digits (the only constraint is available memory).

Note: All major current processors (x64, ARM, RISC-V) are little-endian, so calx also adopts little-endian representation.

The namespace is calx.

Key Features

• Natural operator syntax: Write expressions like a + b, a * b, a ^ b (exponentiation) just as in mathematical notation. Also supports C++20 three-way comparison (operator<=>) and std::format
• Safe NaN / $\pm\infty$ propagation: Division by zero does not crash but returns NaN. Rules like $\infty + 1 = \infty$ and $\infty + (-\infty) = \text{NaN}$ follow IEEE 754-style semantics, similar to double
• Bitwise operations on negative values: Processed using two's complement semantics (same as Python and Java BigInteger)

Quick Start

#include <math/core/mp/Int.hpp>
#include <iostream>

int main() {
    using namespace calx;

    // Numbers with 100 digits are handled without issues
    Int a("12345678901234567890123456789012345678901234567890"
          "12345678901234567890123456789012345678901234567890");
    Int b = a * a;
    std::cout << "a² = " << b << "\n";
    std::cout << "digits = " << b.digitCount() << "\n";

    // Division by zero returns NaN (no exception thrown)
    Int c = a / Int(0);
    std::cout << "a/0 = " << c << "\n";           // NaN
    std::cout << "NaN? " << c.isNaN() << "\n";    // true
}

Build

Required Header

#include <math/core/mp/Int.hpp>

Link library: calx_int.lib (CMake target name: calx_int)

Direct MSVC Compilation

cl /std:c++latest /EHsc /O2 /MD /utf-8 /I<calx>/include your_code.cpp ^
   /link calx_int.lib /MACHINE:X64

CMake

find_package(calx REQUIRED)
target_link_libraries(your_target PRIVATE calx::calx_int)

Constructors

Int()

Default constructor. The value is initialized to $0$. It is never left in an uninitialized state.

Int()

Int a;
std::cout << a << std::endl;

0

Numeric Constructors

Construction from built-in integer types. Implicit conversion is allowed, enabling natural initialization such as Int a = 42;.

Int(int8_t value)
Int(uint8_t value)
Int(short value)
Int(unsigned short value)
Int(int value)
Int(uint64_t value)
Int(int64_t value)

Int a = 42;
Int b = int64_t(-9223372036854775807);
Int c = uint64_t(18446744073709551615ULL);
std::cout << a << "\n" << b << "\n" << c << std::endl;

42
-9223372036854775807
18446744073709551615

Int(std::string_view, int)

Construction from a string. Marked explicit. There is no limit on the number of digits; numbers with tens of thousands of digits can be constructed. A leading - is recognized as a negative sign. Whitespace is not allowed.

explicit Int(std::string_view str, int base = 10)

// Explicitly specify the radix
Int dec("123456789012345678901234567890");
Int hex("DEADBEEF", 16);
Int bin("11111111", 2);
std::cout << dec << "\n" << hex << "\n" << bin << "\n";

// Auto-detect from prefix with base=0
Int autoHex("0xDEADBEEF");
Int autoBin("0b11111111");
Int autoOct("0377");
std::cout << autoHex << "\n" << autoBin << "\n" << autoOct << std::endl;

123456789012345678901234567890
3735928559
255
3735928559
255
255

Copy / Move

Copying performs a deep copy of the value (duplicating the entire word array). Moving transfers ownership of the internal buffer, completing in $O(1)$. After a move, the source is reset to zero.

Int(const Int& other)
Int(Int&& other) noexcept
Int& operator=(const Int& other)
Int& operator=(Int&& other) noexcept
Int& operator=(int value)

Int a = 100;
Int b = a;            // Copy (b = 100, a = 100)
Int c = std::move(a); // Move (c = 100, a = 0)

Special Value Factory

In addition to normal integer values, Int can represent NaN (Not a Number) and $\pm\infty$ (infinity). This design follows IEEE 754 for floating-point numbers, enabling safe propagation of division-by-zero and invalid operation results without exceptions. This feature is not available in common arbitrary-precision integer libraries (GMP, Java BigInteger).

All methods are static.

static Int Zero()
static Int One()
static Int NaN()
static Int PositiveInfinity()
static Int NegativeInfinity()
static Int nan()              // Alias for NaN()
static Int infinity()         // Alias for PositiveInfinity()
static Int negInfinity()      // Alias for NegativeInfinity()

Int inf = Int::infinity();
Int nan = Int::NaN();
std::cout << inf << "\n" << nan << "\n";
std::cout << (inf + Int(1)) << "\n";   // Infinity + 1 = Infinity
std::cout << (inf + Int::negInfinity()) << std::endl; // Infinity + (-Infinity) = NaN

Infinity
NaN
Infinity
NaN

NaN / $\pm\infty$ Propagation Rules

The result of operations involving special values is determined by the following rules. The basic principles, including NaN propagation and the absorption law of $\infty$, follow IEEE 754 floating-point semantics.

Differences from IEEE 754

NaN Cause Classification (NumericError)

An Int object, along with its NaN state, internally stores information about why it became NaN. This can be retrieved as a NumericError enumeration value via the getError() method.

Int a = 42;
Int zero;
Int result = a / zero;  // Division by zero -> NaN

std::cout << std::boolalpha;
std::cout << result.isNaN() << "\n";  // true
std::cout << (result.getError() == NumericError::DivideByZero) << "\n";  // true

Int inf = Int::infinity();
Int indef = inf - inf;  // Infinity - Infinity -> NaN (indeterminate)
std::cout << (indef.getError() == NumericError::InfiniteIndeterminate) << "\n";  // true

Int propagated = result + Int(1);  // NaN + 1 -> NaN (propagation)
std::cout << (propagated.getError() == NumericError::NaNPropagation) << "\n";  // true

true
true
true
true

fromState

Constructs a special Int by directly specifying an internal state code. For normal application code, NaN() and infinity() are sufficient. This method is intended for library internals and advanced error handling.

static Int fromState(NumericState state, NumericError error = NumericError::None)

Return value: An Int with the specified state.

// Construct a NaN with division-by-zero error information
Int result = Int::fromState(NumericState::NaN, NumericError::DivideByZero);
std::cout << result.isNaN() << "\n";  // true

fromRawWords

Constructs an Int directly from a 64-bit word array. Used for data exchange with external libraries or restoration from binary serialization.

static Int fromRawWords(const std::vector<uint64_t>& words, int sign)
static Int fromRawWords(std::span<const uint64_t> words, int sign)

Return value: An Int constructed from the specified word array.

// Construct 2^64 + 1 = 0x10000000000000001 directly from words
std::vector<uint64_t> w = {1, 1};  // w[0]=1 (low), w[1]=1 (high)
Int n = Int::fromRawWords(w, +1);
std::cout << n.toString(16) << "\n";  // 10000000000000001

State Inspection

In addition to "normal integer values," Int can be in special states such as "NaN," "$\pm\infty$," or "divergent." The following methods query the current state. All are const member functions with constexpr support.

constexpr bool isZero() const
constexpr bool isOne() const
constexpr bool isPositive() const
constexpr bool isNegative() const
bool isEven() const
bool isOdd() const
constexpr bool isNaN() const
constexpr bool isInfinite() const
constexpr bool isNormal() const
constexpr bool isSpecialState() const
constexpr int getSign() const
constexpr NumericState getState() const
constexpr NumericError getError() const
constexpr bool isDivergent() const
constexpr DivergenceDetail getDivergenceDetail() const

Int a(42);
Int b(-7);
Int z(0);
std::cout << std::boolalpha;
std::cout << a.isPositive() << "\n";  // true
std::cout << b.isNegative() << "\n";  // true
std::cout << z.isZero() << "\n";      // true
std::cout << a.isEven() << "\n";      // true
std::cout << b.isOdd() << "\n";       // true
std::cout << Int::NaN().isNaN() << std::endl; // true

true
true
true
true
true
true

Free function versions are also provided:

bool isNormal(const Int& value)
bool isNaN(const Int& value)
bool isInfinite(const Int& value)
bool isPosInfinite(const Int& value)
bool isNegInfinite(const Int& value)
bool isOverflow(const Int& value)
bool isDivergent(const Int& value)
std::string getStateDescription(const Int& value)

Type Range Checks

Methods to check whether the value of an Int is within the representable range of a C++ built-in integer type before conversion. Converting a value outside the range results in undefined behavior, so always check before conversion.

constexpr bool fitsByte() const
constexpr bool fitsUByte() const
constexpr bool fitsShort() const
constexpr bool fitsUShort() const
constexpr bool fitsInt() const
constexpr bool fitsUInt() const
constexpr bool fitsInt64() const
constexpr bool fitsUInt64() const

Int small(100);
Int medium(40000);
Int big("99999999999999999999");
std::cout << std::boolalpha;
std::cout << small.fitsByte() << "\n";    // true   (100 <= 127)
std::cout << small.fitsUByte() << "\n";   // true   (100 <= 255)
std::cout << medium.fitsShort() << "\n";  // false  (40000 > 32767)
std::cout << medium.fitsUShort() << "\n"; // true   (40000 <= 65535)
std::cout << small.fitsInt() << "\n";     // true
std::cout << big.fitsInt64() << "\n";     // false
std::cout << big.fitsUInt64() << "\n";    // false

true
true
false
true
true
false
false

Arithmetic Operators

Int supports the same operator syntax as C++ built-in integer types. When either operand is NaN or $\pm\infty$, the result is determined by the propagation rules described above.

Binary Operators

friend Int operator+(const Int& lhs, const Int& rhs)   // + 3 rvalue overloads
friend Int operator-(const Int& lhs, const Int& rhs)   // + 3 rvalue overloads
friend Int operator*(const Int& lhs, const Int& rhs)
friend Int operator/(const Int& lhs, const Int& rhs)   // + 1 rvalue overload
friend Int operator%(const Int& lhs, const Int& rhs)   // + 1 rvalue overload
friend Int operator^(const Int& lhs, const Int& rhs)

Compound Assignment Operators

Int& operator+=(const Int& other)
Int& operator-=(const Int& other)
Int& operator*=(const Int& other)
Int& operator/=(const Int& other)
Int& operator%=(const Int& other)
Int& operator^=(const Int& other)  // Exponentiation assignment

Unary / Increment

Int operator-() const     // Unary minus
Int operator+() const     // Unary plus (copy)
friend Int& operator++(Int& value)       // Prefix ++
friend Int operator++(Int& value, int)   // Postfix ++
friend Int& operator--(Int& value)       // Prefix --
friend Int operator--(Int& value, int)   // Postfix --

Int a("123456789012345678901234567890");
Int b("987654321098765432109876543210");
std::cout << (a + b) << "\n";
std::cout << (a * b) << "\n";
std::cout << (b / a) << "\n";
std::cout << (b % a) << "\n";
std::cout << (Int(2) ^ Int(100)) << std::endl;  // 2^100

1111111110111111111011111111100
121932631137021795226185032733866767003075587200439230
8
9876543210
1267650600228229401496703205376

Multiplication Algorithm

Basecase / Karatsuba / Toom-Cook-3 / Toom-Cook-4 / NTT (Schönhage–Strassen) are automatically selected based on the number of words in the operands. Squaring ($a \times a$) exploits symmetry to run about 30% faster.

Division Algorithm

Schoolbook / Burnikel-Ziegler / Newton reciprocal iteration are automatically selected based on the divisor size. Divisors that are powers of 2 are completed with only a right shift.

Special Division — IntOps

C++'s / and % perform truncation toward zero. Since different rounding rules may be needed depending on the application, the following variants are provided.

static Int IntOps::divmod(const Int& dividend, const Int& divisor, Int& remainder)
static Int IntOps::floorDiv(const Int& dividend, const Int& divisor)
static Int IntOps::ceilDiv(const Int& dividend, const Int& divisor)
static Int IntOps::divExact(const Int& dividend, const Int& divisor)

Int a(17), b(5);
Int rem;
Int q = IntOps::divmod(a, b, rem);
std::cout << "17 / 5 = " << q << " remainder " << rem << "\n";

// Floor division (Python-style): differs for negative division
std::cout << "floorDiv(-7, 3) = " << IntOps::floorDiv(Int(-7), Int(3)) << "\n";
// C++ -7/3 = -2, but floorDiv gives -3

// Ceiling division
std::cout << "ceilDiv(7, 3) = " << IntOps::ceilDiv(Int(7), Int(3)) << std::endl;

17 / 5 = 3 remainder 2
floorDiv(-7, 3) = -3
ceilDiv(7, 3) = 3

Comparison Operators (C++20 Three-Way Comparison)

Implements the C++20 spaceship operator (operator<=>), from which <, <=, >, >= are automatically derived.

The return type is std::partial_ordering rather than std::strong_ordering. This is because NaN exists, and comparison with NaN returns false for any comparison operator (same behavior as IEEE 754 floating-point numbers).

friend std::partial_ordering operator<=>(const Int& lhs, const Int& rhs)
friend bool operator==(const Int& lhs, const Int& rhs)

Comparison with NaN returns std::partial_ordering::unordered. As a result, NaN == NaN is false and NaN < x is also false.

Int a(100), b(200);
std::cout << (a <=> b == std::partial_ordering::less) << "\n";  // true
std::cout << (a == b) << "\n";  // false
std::cout << (a < b) << "\n";   // true
std::cout << (a >= b) << "\n";  // false

Bitwise Operators

Perform bitwise operations on arbitrary-precision integers. Positive values are processed using standard binary representation. Negative values are interpreted as infinite-length two's complement bit strings (same convention as Python and Java BigInteger). For example, $-1$ is ...1111 (all bits 1), and $\sim(-1) = 0$.

friend Int operator&(const Int& lhs, const Int& rhs)       // + 3 rvalue overloads
friend Int operator|(const Int& lhs, const Int& rhs)       // + 3 rvalue overloads
friend Int operator~(const Int& value)                     // + 1 rvalue overload
friend Int operator<<(const Int& lhs, int shift)           // + 1 rvalue overload
friend Int operator>>(const Int& lhs, int shift)           // + 1 rvalue overload
Int bitwiseXor(const Int& lhs, const Int& rhs)             // + 3 rvalue overloads

Compound assignment versions: &=, |=, <<=, >>= are also provided.

Negative values are processed using two's complement semantics. This is the same behavior as Python and Java BigInteger.

$$\tilde{n} = -(n + 1)$$

Int a(0b1100);
Int b(0b1010);
std::cout << (a & b).toBinaryString() << "\n";  // 1000
std::cout << (a | b).toBinaryString() << "\n";  // 1110
std::cout << bitwiseXor(a, b).toBinaryString() << "\n";  // 110
std::cout << (a << 4).toBinaryString() << "\n";  // 11000000

// NOT on a negative value (two's complement)
Int c(-1);
std::cout << (~c) << std::endl;  // 0  (since ~(-1) = 0 in two's complement)

1000
1110
110
11000000
0

Bit Manipulation

Get/set individual bits and query bit lengths. Bit positions start at $0$ for the least significant bit (LSB).

bool getBit(size_t position) const
void setBit(size_t position)
void clearBit(size_t position)
void complementBit(size_t position)
size_t bitLength() const
size_t countLeadingZeros() const
size_t countTrailingZeros() const
size_t scanBit0(size_t startPos = 0) const
size_t scanBit1(size_t startPos = 0) const
static size_t hammingDistance(const Int& a, const Int& b)

Free function:

std::size_t bitCount(const Int& value)

Int a(255);  // 0b11111111
std::cout << a.bitLength() << "\n";           // 8
std::cout << a.countTrailingZeros() << "\n";  // 0

Int b(256);  // 0b100000000
std::cout << b.countTrailingZeros() << "\n";  // 8
std::cout << Int::hammingDistance(a, b) << std::endl;

8
0
8
9

Behavior for NaN / $\pm\infty$

The behavior of bit manipulation methods for special values is as follows.

Numeric Conversion

Convert an Int to a C++ built-in type. Converting a value that exceeds the target type's range results in undefined behavior, so always verify the range using fitsInt() / fitsInt64() / fitsUInt64() before conversion.

int toInt() const
int64_t toInt64() const
uint64_t toUInt64() const
size_t toSizeT() const
double toDouble() const

Free function versions:

int64_t toInt64(const Int& value)
uint64_t toUInt64(const Int& value)
double toDouble(const Int& value)

Int a(42);
int i = a.toInt();
int64_t j = a.toInt64();
double d = a.toDouble();
std::cout << i << " " << j << " " << d << std::endl;

42 42 42

String Conversion

There are multiple ways to convert an Int to a string. Radixes from 2 to 36 can be specified. C++20 std::format is also supported, allowing format control via format specifiers.

toString

std::string toString(int base = 10) const

Return value: std::string — String representation in the specified radix. Negative values are prefixed with -.

Int a(255);
std::cout << a.toString() << "\n";     // Decimal
std::cout << a.toString(16) << "\n";   // Hexadecimal
std::cout << a.toString(2) << "\n";    // Binary
std::cout << a.toString(8) << std::endl; // Octal

255
ff
11111111
377

Specialized String Methods

std::string toHexString(bool uppercase = false) const
std::string toBinaryString() const
std::string toOctalString() const

fromString

static Int fromString(std::string_view str, int base = 10)

Return value: The parsed Int.

Int a = Int::fromString("DEADBEEF", 16);
std::cout << a << std::endl;

3735928559

Stream I/O

friend std::ostream& operator<<(std::ostream& os, const Int& value)
friend std::istream& operator>>(std::istream& is, Int& value)

std::format Support

Int a(255);
std::cout << std::format("{}", a) << "\n";     // 255
std::cout << std::format("{:x}", a) << "\n";   // ff
std::cout << std::format("{:#X}", a) << "\n";  // 0XFF
std::cout << std::format("{:b}", a) << "\n";   // 11111111
std::cout << std::format("{:+d}", a) << std::endl; // +255

255
ff
0XFF
11111111
+255

Digit Count / Logarithm

Query the magnitude of a number by digit count or logarithm. sizeInBase is faster than exact digit count but may have a $+1$ error. Use digitCount when the exact digit count is needed.

size_t digitCount(int base = 10) const
size_t sizeInBase(int base = 10) const
size_t ilog2() const
size_t ilog10() const

Int a("123456789012345678901234567890");
std::cout << a.digitCount() << "\n";    // 30
std::cout << a.sizeInBase() << "\n";    // 30 or 31
std::cout << a.ilog2() << "\n";         // 96
std::cout << a.ilog10() << std::endl;   // 29

30
30
96
29

GCD / LCM

Compute the Greatest Common Divisor and Least Common Multiple. gcd and lcm are provided as free functions (in the calx namespace). The extended Euclidean algorithm is provided as a static method of the IntGCD class.

gcd

Computes the greatest common divisor. Returns the largest divisor common to the two integers.

Int gcd(const Int& a, const Int& b)

Return value: Int — $\gcd(a, b) \geq 0$.

Algorithm: Binary GCD (Stein), $O(n^2)$. Details

Special values: $\gcd(0, b) = |b|$, $\gcd(\text{NaN}, x) = \text{NaN}$, $\gcd(\infty, x) = \text{NaN}$

Int a(48), b(36);
std::cout << gcd(a, b) << std::endl;  // 12

12

lcm

Computes the least common multiple.

Int lcm(const Int& a, const Int& b)

Return value: Int — $\text{lcm}(a, b) \geq 0$.

Internally computed as $\text{lcm}(a, b) = |a| \times (|b| / \gcd(a, b))$ (to avoid intermediate overflow).

Int a(12), b(18);
std::cout << lcm(a, b) << std::endl;  // 36

36

extendedGcd

Extended Euclidean algorithm. In addition to the GCD, it computes the Bézout coefficients $x$ and $y$. This is used in cryptography for computing multiplicative inverses and for solving indeterminate equations.

$$ax + by = \gcd(a, b)$$

static Int IntGCD::extendedGcd(const Int& a, const Int& b, Int& x, Int& y)

Return value: Int — $\gcd(a, b)$.

Int a(35), b(15), x, y;
Int g = IntGCD::extendedGcd(a, b, x, y);
std::cout << "gcd = " << g << "\n";
std::cout << "x = " << x << ", y = " << y << "\n";
std::cout << "check: " << (a * x + b * y) << std::endl;

gcd = 5
x = 1, y = -2
check: 5

Exponentiation

Compute integer exponentiation and modular exponentiation. Both use binary exponentiation (repeated squaring), completing the computation in $O(\log e)$ multiplications relative to the exponent $e$.

pow

Computes the power. Since results grow extremely rapidly, consider using powMod (modular exponentiation) for large exponents.

$$\text{pow}(a, n) = a^n$$

Int pow(const Int& base, unsigned int exponent)
Int pow(const Int& base, const Int& exponent)

Return value: Int — $\text{base}^{\text{exponent}}$.

Algorithm: Binary exponentiation, $O(\log e \times M(n))$. Details

Int a(2);
std::cout << pow(a, 100u) << std::endl;

1267650600228229401496703205376

powMod

Modular exponentiation.

$$\text{powMod}(a, e, m) = a^e \bmod m$$

Int powMod(const Int& base, const Int& exponent, const Int& modulus)

Return value: Int — $a^e \bmod m$, in the range $[0, |m|)$.

Algorithm: Right-to-left binary exponentiation, reducing modulo $m$ at each step. Details

Negative exponents: $\text{powMod}(a, -n, m) = \text{inverseMod}(a^n, m)$

Int base(2), exp(100), mod(1000000007);
std::cout << powMod(base, exp, mod) << std::endl;

976371285

IntModular::powerMod

Montgomery multiplication-based modular exponentiation. Returns the same result as powMod, but is provided as a static member of the IntModular class.

$$\text{powerMod}(a, e, m) = a^e \bmod m$$

static Int IntModular::powerMod(const Int& base, const Int& exp, const Int& m)

Return value: Int — $a^e \bmod m$, in the range $[0, |m|)$.

Algorithm: Repeated squaring via Montgomery multiplication. The conversion to/from Montgomery space means that for a single modular exponentiation the speed is roughly equivalent to powMod, but it is advantageous when performing multiple exponentiations with the same modulus.

IntModular::powerModSec

Constant-time modular exponentiation (side-channel attack resistant). Intended for cryptographic use.

$$\text{powerModSec}(a, e, m) = a^e \bmod m$$

static Int IntModular::powerModSec(const Int& base, const Int& exp, const Int& m)

Return value: Int — $a^e \bmod m$, in the range $[0, |m|)$.

Algorithm: Montgomery modular exponentiation with a constant-time execution path independent of the exponent's bit values. Use this for cryptographic implementations that require resistance to timing attacks and cache-timing attacks (e.g., RSA private key operations). Slower than the standard powerMod, but should be preferred whenever security is required.

IntOps::pow2

Fast generation of powers of $2$.

static Int IntOps::pow2(uint64_t exponent)

Return value: Int — $2^n$. Constructed by bit-setting only, significantly faster than multiplication.

Modular Arithmetic

Modular operations and multiplicative inverse computation for integers. Provided as static methods of the IntModular class. For more advanced modular arithmetic (template-based ModularInt<P> class), see modular.html.

IntModular::mod

Normalized remainder. Unlike C++'s % operator, this always returns a non-negative result $0 \leq r < |m|$.

static Int IntModular::mod(const Int& x, const Int& m)

Return value: Int — $x \bmod m$, in the range $[0, |m|)$.

std::cout << IntModular::mod(Int(-7), Int(5)) << "\n";  // 3 (C++ % gives -2)
std::cout << IntModular::mod(Int(7), Int(5)) << std::endl; // 2

3
2

IntModular::inverseMod

Computes the multiplicative inverse. Finds $x$ such that $a \times x \equiv 1 \pmod{m}$. Frequently used in cryptography (RSA key generation, etc.) and for solving systems of congruences.

$$a \times x \equiv 1 \pmod{m}$$

static Int IntModular::inverseMod(const Int& a, const Int& m, bool is_prime = false)

Return value: Int — $a^{-1} \bmod m$. Returns $0$ if no inverse exists.

Precondition: $\gcd(a, m) = 1$ (coprime).

Algorithm: Extended Euclidean algorithm (accelerated via Fermat's little theorem when is_prime=true). Details

std::cout << IntModular::inverseMod(Int(3), Int(7)) << "\n";   // 5  (3*5=15 equiv 1 mod 7)
std::cout << IntModular::inverseMod(Int(2), Int(5)) << std::endl; // 3  (2*3=6 equiv 1 mod 5)

5
3

Primality Testing

Determines whether a large integer is prime. Since deterministic primality testing for arbitrary-precision integers is extremely costly, a probabilistic algorithm (Miller-Rabin) is used. When a number is determined to be "prime," there is a small probability of a false positive, but this probability can be made arbitrarily small.

isProbablePrime

Probabilistic primality test. This free function is sufficient for most use cases.

bool isProbablePrime(const Int& value, int iterations = 25)

Return value: bool — true if prime (probabilistic).

Algorithm: Miller-Rabin probabilistic primality test. False positive probability $\leq 4^{-k}$ (with default $k = 25$: $\leq 2^{-50}$). Details

Int mersenne = pow(Int(2), 127u) - Int(1);
std::cout << mersenne << "\n";
std::cout << std::boolalpha << isProbablePrime(mersenne) << std::endl;

170141183460469231731687303715884105727
true

IntPrime Class

A collection of static methods for prime-related utilities. Allows direct invocation of specific test algorithms and searching for the next or previous prime.

static bool IntPrime::isMillerRabinPrime(const Int& n, int k = 20)
static bool IntPrime::isFermatPrime(const Int& n, int k = 5)
static bool IntPrime::isProbablePrime(const Int& n, int k = 20)
static Int IntPrime::nextPrime(const Int& n, int k = 20)
static Int IntPrime::prevPrime(const Int& n, int k = 20)

std::cout << IntPrime::nextPrime(Int(100)) << std::endl;  // 101
std::cout << IntPrime::prevPrime(Int(100)) << std::endl;   // 97

101
97

Combinatorics

Computes factorials, double factorials, and binomial coefficients. Provided as static methods of the IntCombinatorics class. For large $n$, results can reach thousands to tens of thousands of digits, but arbitrary-precision integers handle this without issues.

factorial

Computes the factorial $n!$. Automatically selects the optimal algorithm based on the size of $n$.

static Int IntCombinatorics::factorial(const Int& n)

Return value: Int — $n! = 1 \times 2 \times \cdots \times n$.

Algorithm: Automatically selects table lookup / simple loop / sieve method + tournament multiplication based on the size of $n$. Details

std::cout << IntCombinatorics::factorial(Int(20)) << "\n";
std::cout << IntCombinatorics::factorial(Int(100)) << std::endl;

2432902008176640000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

doubleFactorial

Computes the double factorial $n!!$.

static Int IntCombinatorics::doubleFactorial(const Int& n)

Return value: Int

$$n!! = \begin{cases} n \times (n-2) \times \cdots \times 4 \times 2 & (n \text{ is even}) \\ n \times (n-2) \times \cdots \times 3 \times 1 & (n \text{ is odd}) \end{cases}$$

std::cout << IntCombinatorics::doubleFactorial(Int(6)) << "\n";   // 6*4*2 = 48
std::cout << IntCombinatorics::doubleFactorial(Int(7)) << std::endl; // 7*5*3*1 = 105

48
105

binomial

Computes the binomial coefficient.

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

static Int IntCombinatorics::binomial(const Int& n, const Int& k)

Return value: Int — $\binom{n}{k}$.

Exploits the symmetry $\binom{n}{k} = \binom{n}{n-k}$ to reduce computation when $k > n/2$.

std::cout << IntCombinatorics::binomial(Int(10), Int(3)) << "\n";
std::cout << IntCombinatorics::binomial(Int(100), Int(50)) << std::endl;

120
100891344545564193334812497256

Square Root / $n$th Root

Computes the integer square root or $n$th root. Results always return the integer part (truncated). Use sqrtRem / nthRootRem when the remainder is also needed. All are provided as static methods of the IntSqrt class.

IntSqrt::sqrt

Computes the integer square root $\lfloor \sqrt{n} \rfloor$. The optimal algorithm is selected based on input size.

$$\lfloor \sqrt{n} \rfloor$$

static Int IntSqrt::sqrt(const Int& value)

Return value: Int — $\lfloor \sqrt{\text{value}} \rfloor$.

Algorithm: Automatically selects double-precision / Babylonian method / Karatsuba square root (Zimmermann) based on input size, $O(M(n))$. Details

std::cout << IntSqrt::sqrt(Int(1000000)) << "\n";  // 1000
std::cout << IntSqrt::sqrt(Int(2)) << std::endl;    // 1

1000
1

IntSqrt::sqrtRem

Returns the square root and remainder simultaneously.

$$\text{value} = s^2 + r \quad (0 \leq r \leq 2s)$$

static Int IntSqrt::sqrtRem(const Int& value, Int& remainder)

Return value: Int — Square root $s = \lfloor \sqrt{\text{value}} \rfloor$.

Int rem;
Int s = IntSqrt::sqrtRem(Int(50), rem);
std::cout << "sqrt = " << s << ", rem = " << rem << std::endl;
// 50 = 7^2 + 1

sqrt = 7, rem = 1

IntSqrt::isSquare

Perfect square test.

static bool IntSqrt::isSquare(const Int& value, Int* pSqrt = nullptr)

Return value: bool — true if the value is a perfect square.

Optimization: Modular filtering for fast rejection of non-squares. Details

Int s;
std::cout << std::boolalpha;
std::cout << IntSqrt::isSquare(Int(144), &s) << " sqrt=" << s << "\n";
std::cout << IntSqrt::isSquare(Int(145)) << std::endl;

true sqrt=12
false

IntSqrt::nthRoot

Computes the integer part of the $n$th root.

$$\lfloor \sqrt[n]{\text{value}} \rfloor$$

static Int IntSqrt::nthRoot(const Int& value, unsigned int n)

Return value: Int — $\lfloor \text{value}^{1/n} \rfloor$.

Algorithm: Newton's method + precision doubling, $O(M(n) \times \log n)$. Details

std::cout << IntSqrt::nthRoot(Int(1000000), 3) << std::endl;  // 100 (cube root of 1000000)

100

IntSqrt::nthRootRem

Returns the $n$th root and remainder simultaneously.

static Int IntSqrt::nthRootRem(const Int& value, unsigned int n, Int& remainder)

Return value: Int — $s = \lfloor \text{value}^{1/n} \rfloor$.

Int rem;
Int r = IntSqrt::nthRootRem(Int(1000), 3, rem);
std::cout << "root = " << r << ", rem = " << rem << std::endl;
// 1000 = 10^3 + 0

root = 10, rem = 0

Number-Theoretic Functions

The IntNumberTheory class provides a collection of number-theoretic functions. Many functions require prime factorization, so they take an IntFactorTable (small prime table) as a parameter.

#include <math/core/mp/Int/IntNumberTheory.hpp>

IntFactorTable table(1000);
std::cout << IntNumberTheory::eulerPhi(Int(12), table);  // 4
std::cout << IntNumberTheory::jacobiSymbol(Int(2), Int(7));  // 1

Integer Factorization

The IntFactorization class fully factorizes composite numbers into prime factors. It internally dispatches through trial division, Pollard's rho, MPQS, and GNFS in stages.

#include <math/core/mp/Int/IntFactorization.hpp>

auto factors = IntFactorization::factorize(Int("1234567890"));
std::cout << IntFactorization::toString(factors);
// 2 * 3^2 * 5 * 3607 * 3803

Factorization — Individual Algorithms

findFactor() automatically selects from the following algorithms based on input size. Advanced users can also invoke them individually.

All findFactor_* functions take an Int argument and return a non-trivial factor as an Int. Returns $0$ if no factor is found.

Random Number Generation

The IntRandom class provides random number generators for arbitrary-precision integers. Internally uses std::mt19937_64.

#include <math/core/mp/Int/IntRandom.hpp>

Both a class-based IntRandom rng(seed) and free function versions (using a thread_local global engine) are available.

IntRandom rng;
Int r = rng.randomBits(256);    // 256-bit random number
Int s = rng.randomBelow(Int("1000000000000"));  // [0, 10^12)

Integer Sequences

The IntSequence class computes Fibonacci and Lucas sequences using the fast doubling method in $O(\log n)$.

#include <math/core/mp/Int/IntSequence.hpp>

Int fib100 = IntSequence::fibonacci(100);
std::cout << fib100;  // 354224848179261915075

Other Utilities

Absolute value, factor removal, divisibility test, congruence check, and access to internal representation.

abs

Returns the absolute value. Provided as a free function.

Int abs(const Int& value)
Int abs(Int&& value)        // Rvalue overload

The rvalue version only flips the sign, returning the buffer as-is.

Return value: Int — $|value|$.

std::cout << abs(Int(-42)) << std::endl;  // 42

42

removeFactor

Divides the value by a given factor as many times as possible, returning a pair of the "quotient after all divisions" and "the number of times divided."

For example, removing the factor $2$ from $72$:

$$72 \div 2 = 36, \quad 36 \div 2 = 18, \quad 18 \div 2 = 9 \quad (\text{9 is not divisible by 2})$$

It was divided by $2$ 3 times, leaving a quotient of 9. That is, $72 = 9 \times 2^3$. This function returns {9, 3}.

In number theory, "how many times $n$ is divisible by a prime $p$" is called the $p$-adic valuation $v_p(n)$. In the example above, $v_2(72) = 3$.

std::pair<Int, uint64_t> removeFactor(const Int& value, const Int& factor)

Return value: std::pair<Int, uint64_t>

• First element (Int): Quotient after removing all occurrences of the factor — $9$ in the example above
• Second element (uint64_t): Number of times the factor was removed — $3$ in the example above

These satisfy the following relationship:

$$\text{value} = \text{quotient} \times \text{factor}^{\text{count}}$$

auto [quotient, count] = removeFactor(Int(72), Int(2));
std::cout << "72 = " << quotient << " * 2^" << count << std::endl;
// -> 72 = 9 * 2^3

auto [q2, c2] = removeFactor(Int(1000), Int(10));
std::cout << "1000 = " << q2 << " * 10^" << c2 << std::endl;
// -> 1000 = 1 * 10^3

72 = 9 * 2^3
1000 = 1 * 10^3

isDivisible

Tests whether the value is divisible by a given divisor.

bool isDivisible(const Int& divisor) const

Return value: bool — true if *this is divisible by divisor.

std::cout << std::boolalpha;
std::cout << Int(12).isDivisible(Int(3)) << std::endl;  // true
std::cout << Int(13).isDivisible(Int(3)) << std::endl;  // false

true
false

isCongruent

Tests whether two values are congruent modulo a given modulus. Internally checks whether the remainder of their difference is zero.

$$\text{this} \equiv \text{other} \pmod{\text{modulus}}$$

bool isCongruent(const Int& other, const Int& modulus) const

Return value: bool — true if congruent.

std::cout << std::boolalpha;
std::cout << Int(17).isCongruent(Int(2), Int(5)) << std::endl;  // true (17 = 2 mod 5)

true

swap

void swap(Int& other) noexcept              // Member function version
friend void swap(Int& a, Int& b) noexcept   // Free function version

Swaps two Int values in $O(1)$.

Int a(10), b(20);
swap(a, b);
std::cout << a << " " << b << std::endl;  // 20 10

20 10

Internal Access

Direct access to the internal representation of Int (64-bit word array). Used for debugging and data exchange with external libraries. Words are in little-endian order: word(0) is the least significant 64 bits.

constexpr uint64_t word(size_t index) const
constexpr size_t size() const
std::vector<uint64_t> words() const

Algorithms Used

For details on the algorithms used in each operation, see the respective documentation pages.

• Multiplication — 5-tier automatic selection: Basecase / Karatsuba / Toom-Cook / NTT
• Division — Schoolbook / Burnikel-Ziegler / Newton reciprocal iteration
• GCD / Extended GCD — Binary GCD (Stein), Extended Euclidean algorithm
• Exponentiation / Modular Arithmetic — Binary exponentiation, modular exponentiation, modular inverse
• Primality Testing — Small prime table + Miller-Rabin
• Square Root / $n$th Root — Babylonian / Karatsuba sqrt (Zimmermann) / Newton's method
• Factorial / Combinatorics — Table / Sieve + Tournament multiplication