BigInt

BigInt

An arbitrary-precision unsigned integer. A normal int overflows past a couple billion, so for anything larger I store the number one decimal digit per array slot and do the arithmetic by hand, the way you would on paper.

How it stores a number

Every bigint holds a fixed int digits[500] and an int size for how many of those slots are in use. Digits go in least-significant-first, so the number 123 is stored as digits[0]=3, digits[1]=2, digits[2]=1. That ordering is what makes addition and multiplication line up by place value without any index juggling.

The cap of 500 digits is a compile-time constant. It is plenty for the course data files and keeps the class free of any heap allocation, which also means the default copy and assignment the compiler gives you are correct.

Class

classDiagram
    class bigint {
        -int size
        -int digits[500]
        +bigint()
        +bigint(int value)
        +bigint(const char[] charray)
        +operator==(const bigint&) bool
        +operator+(const bigint&) bigint
        +operator*(const bigint&) bigint
        +operator[](int) int
        +timesDigit(int) bigint
        +times10(int) bigint
        +debugPrint(ostream&) void
    }

Loading

Key methods

• Constructors. Default gives zero. The int constructor peels digits off with % 10 and / 10. The const char[] constructor reads a numeric string and reverses it into the digit array, converting each character with - '0'.
• operator+. Column addition with a carry. Walk both numbers from the ones place up, add the two digits plus the carry, keep sum % 10, carry sum / 10. If a carry is left over at the end it becomes a new leading digit. See the flowchart below.
• operator*. Long multiplication built from two helpers. For each digit of the right operand, timesDigit multiplies the whole left number by that single digit (with its own carry), times10 shifts the partial product left by the digit's position, and the shifted partials get added up.
• operator[]. Returns the digit at a place value, or 0 if the index is out of range, so callers can read past the used length safely.
• Stream << and >>. Output skips leading zeros and wraps at 80 characters per line. Input reads digits until a ; terminator and reverses them into place, which matches the data1-*.txt format.

Addition with carry

flowchart TD
    A[Start: result = 0, carry = 0] --> B[i = 0]
    B --> C{i < max of the two sizes?}
    C -- no --> G{carry != 0?}
    C -- yes --> D["sum = digits[i] + rhs.digits[i] + carry"]
    D --> E["result.digits[i] = sum mod 10"]
    E --> F["carry = sum / 10"]
    F --> B2[i = i + 1]
    B2 --> C
    G -- yes --> H["place carry as new top digit, grow size"]
    G -- no --> I[Return result]
    H --> I

Loading

Build and run

cd bigint
make tests        # build and run the assertion suite
make add          # addition demo, reads data1-1.txt
make multiply     # multiplication demo, reads data1-2.txt

The course Makefile uses clang++ -std=c++17. The class also builds clean under g++ -std=c++11, which is what CI uses:

g++ -std=c++11 bigint.cpp test_add.cpp -o test_add && ./test_add

Notes and limits

BigInt is unsigned and supports addition and multiplication only. There is no subtraction, division, or negative sign. The == operator compares the full digit arrays, so it works because unused slots are always zero.