Class BigInteger

Defined in File BigInteger.h

Nested Relationships

Nested Types

Class Documentation

class BigInteger

an integer of any length, sign and magnitude in base 2^64

Public Types

using Limb = std::uint64_t

Public Functions

BigInteger(long long v = 0)

explicit BigInteger(const std::string &s, int base = 10)

the number written in s in the base, with an optional sign

Pre:: 2 <= base <= 36 and s a number in the base
Post:: *this == fromStringSchool( s , base ) (an audit)

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

Pre:: 2 <= base <= 36
Post:: the result equals toStringSchool( base ) (an audit)

std::string toStringSchool(int base = 10) const

the conversions dividing or multiplying by P only, O( n^2 )

Pre:: as for toString() and BigInteger( s , base )

int sign(void) const: -1, 0 or 1

BigInteger abs(void) const

std::size_t limbs(void) const: the number of digits (limbs) in base 2^64

BigInteger operator-(void) const

BigInteger &operator+=(const BigInteger &b)

BigInteger &operator-=(const BigInteger &b)

BigInteger &operator*=(const BigInteger &b)

Public Static Functions

static BigInteger fromStringSchool(const std::string &s, int base = 10)

static std::pair<BigInteger, BigInteger> divMod(const BigInteger &a, const BigInteger &b)

the quotient truncated toward zero and the remainder

Pre:: b != 0
Post:: a = q b + r, |r| < |b|, r = 0 or of the sign of a, and the pair equals divModSchool( a , b ) (audits)

static std::pair<BigInteger, BigInteger> divModSchool(const BigInteger &a, const BigInteger &b)

the quotient and the remainder by Algorithm D alone, O( m n )

Pre:: b != 0

static BigInteger multiplySchool(const BigInteger &a, const BigInteger &b)

the product by Algorithm M, by Karatsuba and by the NTT

Post:: multiplyKaratsuba( a , b ) and multiplyFFT( a , b ) equal multiplySchool( a , b ) (an audit)

static BigInteger multiplyKaratsuba(const BigInteger &a, const BigInteger &b)

static BigInteger multiplyFFT(const BigInteger &a, const BigInteger &b)

static BigInteger divExact(BigInteger a, const BigInteger &b)

a / b for b a divisor of a: by one digit by the inverse of b modulo 2^64 (Hensel’s division, 4.3.1 exercise 16), with no division of two digits by one, in place of a, else as a / b

Pre:: b != 0 and b divides a
Post:: the result times b is a (an audit)

static void addMul(BigInteger &r, const BigInteger &a, const BigInteger &b): r += a b, in place when a or b has one digit, r at least as long as the other and of the sign of the product

static BigInteger pow(const BigInteger &x, unsigned long n): x^n by the binary method

static std::pair<BigInteger, BigInteger> sqrtRem(const BigInteger &a)

the integer square root s = floor( sqrt( a ) ) and r = a - s^2, by Zimmermann’s Karatsuba square root

Pre:: a >= 0
Post:: s^2 + r = a, 0 <= r <= 2 s, s equal to sqrtNewton( a ) (audits)

static BigInteger sqrt(const BigInteger &a)

static BigInteger sqrtNewton(const BigInteger &a)

the integer square root by Newton’s method from above

Pre:: a >= 0

static BigInteger gcd(const BigInteger &a, const BigInteger &b)

the greatest common divisor of |a| and |b|, by Lehmer

Post:: it equals gcdEuclid( a , b ) (an audit)

static BigInteger gcdEuclid(BigInteger a, BigInteger b): the greatest common divisor of |a| and |b|, by Euclid

Public Static Attributes

static constexpr std::size_t kKaratsuba = 40: limbs for Karatsuba

static constexpr std::size_t kToom3 = 120: limbs for Toom-3

static constexpr std::size_t kToom4 = 200: limbs for Toom-4

static constexpr std::size_t kToom32 = 64: limbs, Toom-3/2, 4/2

static constexpr std::size_t kFFT = 768: limbs for the NTT

static constexpr std::size_t kSqrKaratsuba = 56: the same, squares

static constexpr std::size_t kSqrToom3 = 160

static constexpr std::size_t kSqrToom4 = 300

static constexpr std::size_t kSqrFFT = 768

static constexpr std::size_t kDivide = 96: quotient limbs, recursion

static constexpr std::size_t kConvert = 24: limbs, divide and conquer

static constexpr std::size_t kConvertF = 64: limbs, by fractions

static constexpr std::size_t kFracLeaf = 32: chunks, by products

static constexpr std::size_t kFracLevel = 4: 2^k chunks, fractions

static constexpr std::size_t kFracCyclic = 448: limbs, cyclic products

static constexpr std::size_t npos = std::size_t(-1)

static constexpr std::size_t kModFold = 16: limbs, folded remainder

static constexpr std::size_t kHensel = 20: limbs, gcd by folding

static constexpr std::size_t kNewton = 768: limbs, by the reciprocal

static constexpr std::size_t kNewtonKept = 512: limbs, the same if kept

static constexpr std::size_t kRecip = 32: limbs, reciprocal by D

static constexpr std::size_t kDivCut = 900: limbs, quotient alone

static constexpr std::size_t kDivShort = 16: limbs, on the stack

static constexpr std::size_t kDivBlock = 40: limbs, 4 digits a step

static constexpr std::size_t kDivBlock6 = 64: limbs, 6 digits a step

static constexpr std::size_t kDivExact2 = 32: limbs, exact both ways

static constexpr std::size_t kHgcd = 128: limbs, recursive hgcd

static constexpr std::size_t kGcdDC = 300: limbs, gcd by hgcd

static constexpr std::size_t kGmpMul = 5: limbs, mpn_mul

static constexpr std::size_t kGmpMulTop = 1536

static constexpr std::size_t kGmpMulLongTop = 704

static constexpr std::size_t kGmpSqrTop = 1920: limbs, mpn_sqr

static constexpr std::size_t kGmpDivTop = 3584: mpn_tdiv_qr

static constexpr std::size_t kGmpShort = 512: quotient limbs

static constexpr std::size_t kGmpQuot = 8: mpz_tdiv_q

static constexpr std::size_t kGmpQuotTop = 49152

static constexpr std::size_t kGmpExactTop = 262144: mpz_divexact

static constexpr std::size_t kGmpToStringTop = 49152: mpz_get_str

static constexpr std::size_t kGmpGcd = 2048: limbs, mpz_gcd

Friends

friend BigInteger operator+(const BigInteger &a, const BigInteger &b)

friend BigInteger operator-(const BigInteger &a, const BigInteger &b)

friend BigInteger operator*(const BigInteger &a, const BigInteger &b)

friend BigInteger operator/(const BigInteger &a, const BigInteger &b)

Pre:: b != 0

friend BigInteger operator%(const BigInteger &a, const BigInteger &b)

friend bool operator==(const BigInteger &a, const BigInteger &b) = default

friend std::strong_ordering operator<=>(const BigInteger &a, const BigInteger &b)