# 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

```mermaid
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
    }
```

## 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

```mermaid
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
```

## Build and run

```sh
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:

```sh
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.