Big Integer Library in C++

A C++ self-project that implements an arbitrary-precision integer class named BigInteger.

The goal of this project is to work with integer values larger than built-in C++ types like long long, while keeping the code simple enough to understand and explain in an interview.

GitHub About

Suggested repository description:

Arbitrary-precision integer library in C++ using vector-based digit storage and operator overloading.

Suggested topics:

cpp, cpp20, big-integer, arbitrary-precision, operator-overloading, data-structures, algorithms, console-application

Why I Built This

C++ integer types have fixed size limits. For example, long long is not enough for values like:

• 1000!
• 2^1000
• large Fibonacci numbers
• large combinatorics results

This project helped me understand how large-number arithmetic works internally instead of relying on an external big integer library.

What The Project Does

The project provides a reusable BigInteger class that supports:

• positive and negative integers
• arithmetic operations
• comparison operators
• large-number functions such as factorial, Fibonacci, power, square root, and Catalan number

The demo program also provides a simple console menu where custom inputs can be entered.

How Numbers Are Stored

Numbers are stored using a vector<int>.

Each element stores one decimal digit from 0 to 9. The digits are stored in reverse order because arithmetic usually starts from the least significant digit.

For example:

12345 is stored as [5, 4, 3, 2, 1]

The sign is stored separately, so negative numbers are also supported.

I used base-10 storage intentionally because it is easier to read, debug, and explain. It is not the fastest representation, but it fits the learning goal of this project.

Supported Operations

• Addition: +
• Subtraction: -
• Multiplication: *
• Division: /
• Modulo: %
• Comparisons: <, >, ==, !=, <=, >=
• Power
• Integer square root
• Factorial
• Fibonacci
• Catalan number

Algorithms Used

• Addition and subtraction are done digit by digit with carry or borrow.
• Multiplication uses the standard long multiplication method.
• Division uses long division.
• Power uses binary exponentiation.
• Integer square root uses binary search.
• Factorial multiplies the current result by each integer from 2 to n.
• Fibonacci is calculated iteratively.
• Catalan numbers are calculated using a recurrence formula.

No external big integer libraries are used.

Folder Structure

Big-Integer-Library/
  .github/
    workflows/
      cpp-tests.yml
  include/
    BigInteger.h
  src/
    BigInteger.cpp
    main.cpp
  tests/
    test_runner.cpp
    test_cases.txt
  README.md

How To Compile And Run

Compile with C++20:

g++ -std=c++20 src/main.cpp src/BigInteger.cpp -Iinclude -o big_integer_demo.exe

Run:

./big_integer_demo.exe

On Windows PowerShell:

.\big_integer_demo.exe

How To Run Tests

The project includes a small test runner without any external testing framework.

Compile the tests:

g++ -std=c++20 tests/test_runner.cpp src/BigInteger.cpp -Iinclude -o big_integer_tests.exe

Run:

./big_integer_tests.exe

On Windows PowerShell:

.\big_integer_tests.exe

The tests cover basic construction, signs, arithmetic, comparison operators, division, modulo, power, square root, factorial, Fibonacci, Catalan number, division by zero, and the LLONG_MIN constructor edge case.

The same test command is used in the GitHub Actions workflow at .github/workflows/cpp-tests.yml.

Sample Output

The program starts with a menu:

Big Integer Library in C++

Choose an option:
1. Add two numbers
2. Subtract two numbers
3. Multiply two numbers
4. Divide two numbers
5. Modulo of two numbers
6. Compare two numbers
7. Power
8. Integer square root
9. Factorial
10. Fibonacci
11. Catalan number
12. Run sample demo
0. Exit

Example input:

Enter choice: 1
Enter first number: 123456789123456789123456789
Enter second number: 987654321987654321987654321
Result:
1111111111111111111111111110
Time taken: 3 microseconds

The demo option includes larger examples such as 2^1000, 1000!, Fibonacci(500), and Catalan(50).

Runtime may vary depending on machine and input size.

Time Complexity

Let n be the number of decimal digits.

• Addition and subtraction: O(n)
• Comparison: O(n)
• Multiplication: O(n^2)
• Division and modulo: O(n^2) in this implementation
• Power: O(log exponent) multiplications
• Integer square root: binary search over the answer range
• Factorial: repeated multiplication from 2 to n
• Fibonacci: O(n) additions for the index value

Limitations

• Base-10 storage is easy to understand but slower than using larger bases such as 1e9.
• General multiplication uses long multiplication, not Karatsuba or FFT.
• Division is written for clarity and is not the fastest possible version.
• Decimal numbers are not supported.
• Exponents are normal unsigned integers, not BigInteger.
• This is a console project, not a GUI or web application.

Future Improvements

• Add more automated test cases for very large values.
• Add faster multiplication for very large numbers.
• Add GCD and modular exponentiation.
• Improve input validation.
• Add more examples in the tests/ folder.