C++ big integer library
MIT License
C++ big integers, with explanations.
To get started, download the archive containing header and source files, include it in your code, and compile however you would.
Do you need thousands of digits? Millions? More? This library got you covered! Are you after documentation but cannot be bothered looking up for research papers? Browse the resources here.
There are already many big integer libraries out there:
This project is an attempt at providing a better compromise:
+
, -
, *
, /
, %
==
, !=
, <=
, >=
, <
, >
<<
, >>
More to come in the future.
Type definition
Defined inside the bigint
namespace, use arbitrarily large integers with the bigint_t
class.
Big integers can be created from regular integer types or from any std::string
representing an integer, then manipulated normally:
using namespace bigint;
bigint_t a(123456789), b(987654321),
c = a + b, d = c * c;
std::cout << d;
Arithmetic operations working for regular integers are overloaded to work with big integers. The algorithms behind these operations are aimed to have fast algorithmic complexity. Because calculating numbers without any way to output them would make the library rather useless, stream operators render big integers as strings.
Comparison Big integers of any size can be compared to one another.
using namespace bigint;
bigint_t a("123456789123456789123456789123456789"),
b("987654321987654321987654321987654321987654321");
bool e = (a == b), //false
ne = (a != b), //true
gt = (a > b), //false
ge = (a >= b), //false
lt = (a < b), //true
le = (a <= b); //true
//Since C++20
auto ss = (a <=> b); //std::strong_ordering::less
Addition / Subtraction Add/subtract big integers normally:
bigint_t x = a + b, y = c - d;
Bit-wise operations In progress.
Multiplication Multiply big integers normally. Multiplication is a complex operation that deserves its own separate documentation.
bigint_t x = a * b;
Division / Mod In progress.
Input/Output of a bigint_t
In progress.
The bigint
namespace is shipped with more complex algorithms, with a non-obvious approach to ensure it outperforms naive implementations.
Power The power function calculates $n^p = \overbrace{n \times n \times n \times \dotsc \times n}^{p\text{ times}}$. This is done with $\text{O}(\text{log}(p))$ multiplications.
auto np bigint::power(123456789ULL, 62125); // 123456789 ^ 62125
Factorials
The factorial function calculates $n! = 1 \times 2 \times 3 \times \dotsc \times n$ (typed: size_t
).
The function uses about half the multiplications that would normally be required for this calculation and does so by pairing operands in a way that better uses the multiplication algorithms, compared to the naive approach.
auto f = bigint::factorial(100000); // 100k!
Fibonacci sequence + generalization
The Fibonacci sequence is a very famous sequence of integers, supported only up to its 93rd element when using 64-bit unsigned integers. bigint::fibonacci
can go way, way beyond that point using an elaborate algorithm to diminish the calculation time as much as possible.
The algorithm is designed to produce consecutive Fibonacci numbers between 2 indices and handles 2 types of generalization of the Fibonacci sequence:
auto f = bigint::fibonacci(500000);
This library and its associated documentation are separately provided under MIT license.