Big integers

A big integer is a number stored as an array of its digits, and the program adds and multiplies such numbers column by column, the way it is done on paper. It is needed when a problem asks for every digit of a number beyond long long, which stops at about 9.2 \cdot 10^{18} (see integer types). If only the remainder of the answer is needed, use modular arithmetic instead.

Explanation

25! has 26 digits, too many for a long long. Standard C++ has no type that holds it and can be read or printed with cin and cout, although Python and Java have one.

The natural way to get the digits is to read the number as a string. Take 99875 and 487. Column addition starts from the ones digits, but in the strings they sit at different places: the 5 of 99875 is at index 4, the 7 of 487 at index 2. Adding the strings character by character pairs 9 with 4, which is wrong. The sum, 100362, also has one digit more than 99875, and that new 1 belongs in front of index 0, where the string has no room for it.

The fix is to write the digits backwards: cell i holds the digit worth 10^i, so the ones digit is in cell 0 and the tens digit in cell 1. Now the columns line up by index in every number. The top cell, the one with the highest place value, is the last cell of the array, so a new top digit goes at the end, where a vector adds it with push_back.

Fig. 1. As written, cell 0 pairs the wrong digits. Backwards, cell i holds the digit worth 10^i in both numbers.

Let's add 99875 and 487 in this layout.

Digits backwards: the ones digits are in cell 0. The box at the top holds the carry.

Column: 5 + 7 + 0 = 12.

Carry: keep 2, carry 1.

Column: 7 + 8 + 1 = 16. Carry: keep 6, carry 1.

Column: 8 + 4 + 1 = 13. Carry: keep 3, carry 1.

Column: 9 + 0 + 1 = 10. Carry: keep 0, carry 1. 487 has no cell 3, so it adds 0.

Column: 9 + 0 + 1 = 10. Carry: keep 0, carry 1.

Finish: the carry 1 becomes a new cell.

Print from the top cell to cell 0: 100362.

1/9

Fig. 2. Step with the buttons or the arrow keys. Blue is the current column, and the box on the right holds the carry.

Each step of the loop has two parts. The column adds the two digits and the incoming carry. The carry is what doesn't fit in one cell: from 12 we keep 2 in the cell and pass 1 on to the next column, as in school (12 % 10 = 2 and 12 / 10 = 1, see integer division). After the loop comes the finish: the last carry becomes a new top cell. The loop runs to the length of the longer number, so a sum of an $n$-digit and an $m$-digit number has at most \max(n, m) + 1 digits.

To compare two numbers, look at the length first: a number with more digits is larger, as long as neither has leading zeros. With equal lengths, compare from the top cell down to the first difference: for 99875 and 99785 the top cells are equal, then 8 > 7, so 99875 is larger. Comparing the strings doesn't work: "99875" comes after "100362" as a string, because '9' is greater than '1'.

Multiplying by an ordinary int works column by column too: each column is the digit times k plus the carry, and the cell keeps the last digit of that. The carry is everything else, so it can have several digits, and at the finish it may need more than one new cell.

Fig. 3. Multiplying 987 by 99. The carries 69, 86 and 97 have two digits, so the last one fills two new cells.

Each operation touches each cell once, so it takes $O(n)$ time for numbers with $n$ digits.

In C++

A big integer is a vector<int> with the digits backwards, called big for short. mulSmall takes big& a, a reference, so it changes the caller's number in place.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef vector<int> big;   // digits backwards: a[i] is worth 10^i

// strip leading zeros, keep one cell for 0
void trim(big& a) {
    while (a.size() > 1 && a.back() == 0) a.pop_back();
}

// digits backwards: the last character of s goes to cell 0
big readBig(const string& s) {
    big a;
    for (int i = (int)s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    trim(a);
    return a;
}

// from the top cell down to cell 0
void printBig(const big& a) {
    for (int i = (int)a.size() - 1; i >= 0; i--) cout << a[i];
    cout << '\n';
}

// -1 if a < b, 0 if a == b, 1 if a > b
int compareBig(const big& a, const big& b) {
    // length first
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    // then from the top
    for (int i = (int)a.size() - 1; i >= 0; i--)
        if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
    return 0;
}

big addBig(const big& a, const big& b) {
    big c;
    int carry = 0;
    for (int i = 0; i < (int)max(a.size(), b.size()); i++) {
        // column
        int cur = carry;
        if (i < (int)a.size()) cur += a[i];
        if (i < (int)b.size()) cur += b[i];
        // carry
        c.push_back(cur % 10);
        carry = cur / 10;
    }
    // finish
    if (carry > 0) c.push_back(carry);
    return c;
}

// a = a * k, for 0 <= k <= 10^9
void mulSmall(big& a, long long k) {
    long long carry = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        // column
        long long cur = a[i] * k + carry;
        // carry
        a[i] = cur % 10;
        carry = cur / 10;
    }
    // finish
    while (carry > 0) {
        a.push_back(carry % 10);
        carry /= 10;
    }
    trim(a);
}

int main() {
    string s, t;
    long long k;
    cin >> s >> t >> k;
    big a = readBig(s), b = readBig(t);
    printBig(addBig(a, b));
    cout << compareBig(a, b) << '\n';
    mulSmall(a, k);
    printBig(a);
}

The program reads two numbers and k, then prints the sum, the result of the comparison and the first number times k. For example, the input is:

99875 487 99

To get n! for n up to 3000, start from 1 and multiply by 2, 3, …, n. 3000! has 9131 digits, so the 3000 multiplications take at most 3000 \cdot 9131 \approx 2.7 \cdot 10^7 steps.

big f = {1};
for (int i = 2; i <= n; i++) mulSmall(f, i);
printBig(f);

Fibonacci numbers need only additions: keep the last two numbers and add them; F(10000) has 2090 digits.

big x = {0}, y = {1};   // F(0) and F(1)
for (int i = 2; i <= n; i++) {
    big z = addBig(x, y);
    x = y;
    y = z;
}
printBig(y);             // F(n), for n >= 1

To print <, = or > for two numbers from the input:

int r = compareBig(readBig(s), readBig(t));
cout << (r < 0 ? '<' : r == 0 ? '=' : '>') << '\n';

Subtraction of a smaller number from a larger one is the same column loop with a borrow instead of a carry: when a column goes below 0, add 10 and take 1 from the next column, then trim the leading zeros. Division by an int goes the other way, from the top cell down, and passes the remainder of each column on to the next one.

Nine digits per cell

With one digit per cell, F(65536) (13696 digits) takes about 4.5 \cdot 10^8 steps, too close to a one-second limit. A cell can hold nine digits instead: a[i] is then worth 10^{9i}. There are 9 times fewer cells, so F(65536) takes about 5 \cdot 10^7 steps.

The constant BASE replaces 10 in every % and /, readBig takes nine characters at a time from the end of the string, and printBig pads every cell but the top one to nine digits (add #include <iomanip> for setw); the rest stays the same.

Fig. 4. Chunks are cut from the end of the string, so only the top cell can have fewer than nine digits.

const int BASE = 1000000000;   // nine digits per cell

// digits backwards, nine at a time
big readBig(const string& s) {
    big a;
    for (int i = (int)s.size(); i > 0; i -= 9) {
        int from = max(0, i - 9);
        a.push_back(stoi(s.substr(from, i - from)));
    }
    trim(a);
    return a;
}

void printBig(const big& a) {
    cout << a.back();                                   // the top cell as it is
    for (int i = (int)a.size() - 2; i >= 0; i--)
        cout << setw(9) << setfill('0') << a[i];        // every other cell with 9 digits
    cout << '\n';
}

The carry works as before: for 999999999 + 1 the column sum is 10^9, so the cell keeps 0 and the carry 1 becomes a new cell: the cells are 0 and 1, printed as 1 and 000000000. In addBig the column sum is at most 2 \cdot 10^9 - 1, which still fits in an int. In mulSmall, for k up to 10^9 it stays below about 10^{18}, which fits in a long long.

Common mistakes

• Stopping the addition loop at the shorter number and copying the rest of the longer one. 99875 + 487 then gives 99362, because the carry into the 9s is lost. The loop has to run up to the longer length.

• Finishing a multiplication with if (carry) a.push_back(carry);. For 987 × 99 the top cell then holds 97, so the result has 4 cells and compareBig says it is smaller than 10000. A while (carry) loop splits 97 into two cells.

• Leaving leading zeros. Without trim, 987 × 0 prints 000, and a number read as 007 has 3 cells, which breaks the length check. Call trim after reading and after mulSmall.

Similar techniques

Integer types: __int128 reaches 38 digits, but cin and cout can't read or print it.

Modular arithmetic: a remainder can't give the digits back, so it only works when the answer is asked modulo 10^9 + 7.

Floating-point numbers and logarithms: when only the number of digits of a huge number is needed, or which of two is larger. The number of digits of n! is \lfloor \log_{10} 1 + \log_{10} 2 + \dots + \log_{10} n \rfloor + 1, with no big integer at all.

Binary exponentiation: a power modulo m. Computing 2^{1000} in full is a mulSmall(a, 2) loop instead.

Multiplying two big integers: the schoolbook method with two nested column loops takes $O(nm)$; Karatsuba's method, about O(n^{1.58}), and FFT, O(n \log n), handle numbers with 10^5 digits.

Practice