Big integers

Why this matters

The previous lesson showed that a 64-bit unsigned integer holds values up to 18446744073709551615. That is about 1.8 times 10 to the power 19, which sounds large, but some everyday calculations pass it quickly.

Take the factorial of a number. The factorial of 5, written 5!, is 5 × 4 × 3 × 2 × 1 = 120. The factorial grows very fast. The program below multiplies the numbers from 1 up to 21 and prints each result from 20 on:

#include <cstdint>
#include <iostream>
 
int main() {
    std::uint64_t f = 1;
    for (std::uint64_t i = 1; i <= 21; ++i) {
        f *= i;
        if (i >= 20) {
            std::cout << i << "! as uint64_t = " << f << "\n";
        }
    }
    return 0;
}

Output from a run with g++ -std=c++20 -Wall:

20! as uint64_t = 2432902008176640000
21! as uint64_t = 14197454024290336768

The first line is correct. The second line is not. The true value of 21! is 51090942171709440000, which is more than the 64-bit limit, so the multiplication wrapped around and printed a wrong number. No error appeared. This is the same silent wrap-around covered in the previous lesson, now happening with a value that a real program might need.

This lesson shows two ways to handle numbers that are too large for the built-in types. The first uses a 128-bit integer. The second stores the digits of a number in a container and does the arithmetic by hand, the way you learned to add and multiply on paper. The lesson also looks at how to parse (turn text into a number) a long string of digits and what goes wrong when you try.

Two approaches

Both approaches are used in practice, and they have different limits.

The 128-bit type is the quick fix when the numbers are a little too big. The digit container is the general tool, because the number of digits has no fixed limit.

The 128-bit type

The type __int128 holds a 128-bit whole number. It is a GCC and Clang extension, so it is not part of standard C++, and some compilers, such as the one from Microsoft, do not provide it. When you use it, the code only compiles on the compilers that have it.

Its limits are available from std::numeric_limits, the same way as the 8-bit and 64-bit limits in the previous lesson. The unsigned form is unsigned __int128. Here is the factorial again, now with a 128-bit unsigned type that can hold up to 34!. The loop prints each factorial as it goes:

#include <iostream>
 
int main() {
    unsigned __int128 fact = 1;
    for (unsigned __int128 i = 1; i <= 34; ++i) {
        fact *= i;
        std::cout << i << "! = " << fact << "\n";
    }
    return 0;
}

This program does not compile, and the reason is the first real problem you will meet with __int128. The standard stream std::cout has no way to print a 128-bit value. The compiler reports this error:

error: ambiguous overload for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘__int128 unsigned’)

The message means that << does not know which of its many overloads (versions of << for different types) to use for this type, because none of them matches. The fix is to write a small function that turns the number into a string of digits. The function below repeatedly takes the last digit with % 10, then divides by 10. It collects the digits in reverse order, so the last step reverses them.

#include <algorithm>
#include <string>
 
std::string to_string_u128(unsigned __int128 value) {
    if (value == 0) {
        return "0";
    }
    std::string digits;
    while (value > 0) {
        digits.push_back(static_cast<char>('0' + static_cast<int>(value % 10)));
        value /= 10;
    }
    std::reverse(digits.begin(), digits.end());
    return digits;
}

The program below computes the factorial of each number from 1 to 34 and prints selected results. It uses the function above and prints the values as text.

#include <algorithm>
#include <iostream>
#include <limits>
#include <string>
 
std::string to_string_u128(unsigned __int128 value) {
    if (value == 0) {
        return "0";
    }
    std::string digits;
    while (value > 0) {
        digits.push_back(static_cast<char>('0' + static_cast<int>(value % 10)));
        value /= 10;
    }
    std::reverse(digits.begin(), digits.end());
    return digits;
}
 
int main() {
    unsigned __int128 fact = 1;
    for (unsigned __int128 i = 1; i <= 34; ++i) {
        fact *= i;
        if (i == 20 || i == 25 || i == 30 || i == 33 || i == 34) {
            std::cout << static_cast<int>(i) << "! = " << to_string_u128(fact) << "\n";
        }
    }
    std::cout << "34! fits in signed __int128: "
              << (fact <= static_cast<unsigned __int128>(std::numeric_limits<__int128>::max()) ? "yes" : "no")
              << "\n";
    return 0;
}

Output from a run with g++ -std=c++20 -Wall:

20! = 2432902008176640000
25! = 15511210043330985984000000
30! = 265252859812191058636308480000000
33! = 8683317618811886495518194401280000000
34! = 295232799039604140847618609643520000000
34! fits in signed __int128: no

The value 34! has 39 digits. It fits in the unsigned 128-bit type, whose largest value is about 3.4 times 10 to the power 38. It does not fit in the signed type, whose largest value is about 1.7 times 10 to the power 38. The last line of output shows this.

The factorial of 35 is about 1.0 times 10 to the power 40, which is more than the unsigned 128-bit limit. A loop that goes that far overflows silently, the same way the 64-bit loop did. A 128-bit type only moves the boundary. It does not remove it.

Notice also that the program uses unsigned for the loop and the product. Signed overflow is undefined in C++, as the previous lesson explained. The unsigned type gives defined wrap-around, which is at least predictable, and the check against the signed limit is done in a separate step.

The digit container

The second approach does not depend on a built-in type. A number is stored as a list of its digits, one digit per element. Here it is stored as a std::string, with each character holding one digit as text.

The order matters. The digits are stored least significant digit first. The least significant digit is the ones place. The number 314 is stored as the characters 4, 1, 3. Position 0 is the ones place, position 1 is the tens place, and so on. This makes carrying easy, because a carry from position 0 goes to position 1, and so on.

The idea of a carry is the same as in addition on paper. If the sum of two digits in one column is 10 or more, you write the last digit and carry 1 into the next column. Adding 9 and 9 gives 18: write 8, carry 1. Adding 9 and 1 gives 10 in a column with carry 0: write 0, carry 1.

Here is addition on digit strings:

std::string add_digits(const std::string& a, const std::string& b) {
    std::string result;
    int carry = 0;
    std::size_t n = std::max(a.size(), b.size());
    for (std::size_t i = 0; i < n || carry > 0; ++i) {
        int da = i < a.size() ? a[i] - '0' : 0;
        int db = i < b.size() ? b[i] - '0' : 0;
        int sum = da + db + carry;
        result.push_back(static_cast<char>('0' + sum % 10));
        carry = sum / 10;
    }
    return result;
}

The loop runs while there is a digit in either number, or while a carry is still waiting. The condition i < a.size() protects against reading past the end of the shorter number. Each step takes the digit at position i from each number, adds the carry, writes the last digit of the sum, and keeps the carry.

Multiplying by a small number, such as a factor from 2 to 100, follows the same column pattern:

std::string multiply_digits_by_small(const std::string& a, int factor) {
    std::string result;
    int carry = 0;
    for (char c : a) {
        int product = (c - '0') * factor + carry;
        result.push_back(static_cast<char>('0' + product % 10));
        carry = product / 10;
    }
    while (carry > 0) {
        result.push_back(static_cast<char>('0' + carry % 10));
        carry /= 10;
    }
    return result;
}

A worked example makes this concrete. The string "75" stores the number 57, with the 7 first. Multiply it by 3. The first digit is 7, and 7 × 3 = 21. Write 1, carry 2. The second digit is 5, and 5 × 3 = 15, plus the carry 2 is 17. Write 7, carry 1. Nothing is left, but the carry is still 1, so write 1. The stored result is "171", and 57 × 3 = 171. The check works.

The program below uses both functions. The number 30! is computed by multiplying 1 by each factor from 2 to 30. The number 100! is computed the same way, and its size is printed:

#include <algorithm>
#include <iostream>
#include <string>
 
// Numbers are stored as strings of digits, least significant digit first.
// "314" is stored as "413".
 
std::string add_digits(const std::string& a, const std::string& b) {
    std::string result;
    int carry = 0;
    std::size_t n = std::max(a.size(), b.size());
    for (std::size_t i = 0; i < n || carry > 0; ++i) {
        int da = i < a.size() ? a[i] - '0' : 0;
        int db = i < b.size() ? b[i] - '0' : 0;
        int sum = da + db + carry;
        result.push_back(static_cast<char>('0' + sum % 10));
        carry = sum / 10;
    }
    return result;
}
 
std::string multiply_digits_by_small(const std::string& a, int factor) {
    std::string result;
    int carry = 0;
    for (char c : a) {
        int product = (c - '0') * factor + carry;
        result.push_back(static_cast<char>('0' + product % 10));
        carry = product / 10;
    }
    while (carry > 0) {
        result.push_back(static_cast<char>('0' + carry % 10));
        carry /= 10;
    }
    return result;
}
 
std::string reverse_for_display(std::string digits) {
    std::reverse(digits.begin(), digits.end());
    return digits;
}
 
int main() {
    std::string a = "99999999999999999999";  // 20 nines
    std::string b = "1";
    std::cout << "a + b = " << reverse_for_display(add_digits(a, b)) << "\n";
 
    std::string fact = "1";
    for (int i = 2; i <= 30; ++i) {
        fact = multiply_digits_by_small(fact, i);
    }
    std::cout << "30! = " << reverse_for_display(fact) << "\n";
 
    std::string fact100 = "1";
    for (int i = 2; i <= 100; ++i) {
        fact100 = multiply_digits_by_small(fact100, i);
    }
    std::string shown = reverse_for_display(fact100);
    std::cout << "100! has " << shown.size() << " digits\n";
    std::cout << "100! starts with " << shown.substr(0, 20) << "\n";
    std::cout << "100! ends with " << shown.substr(shown.size() - 5) << "\n";
    return 0;
}

Output from a run:

a + b = 100000000000000000000
30! = 265252859812191058636308480000000
100! has 158 digits
100! starts with 93326215443944152681
100! ends with 00000

The result of a + b has 21 digits, one more than either input, because the carry ran past the end of the longer number. The factorial 30! matches the value from the 128-bit program above. The last line shows the last five digits of 100!, which are 00000. The number 100! ends in 24 zeros, so the last five digits are all zero.

The program prints the stored digits through reverse_for_display, because the stored order is the reverse of the printed order. The function std::reverse from <algorithm> flips the string.

Multiplying two large numbers

Multiplying by a small factor is one case. Multiplying two long numbers needs one more idea. Every digit of the first number is multiplied by every digit of the second. Each product goes into a column, and the column is the sum of the two positions. For example, the digit at position 0 of the first number times the digit at position 2 of the second number goes to column 2.

A column can hold a sum larger than 9, because many products land in the same column. The column values are collected first, and then a single pass turns them into digits, carrying as it goes. The code uses long long for the column sums, so that a long multiplication does not overflow the column values:

#include <iostream>
#include <string>
#include <vector>
 
// Digits are stored least significant first: 314 is {4, 1, 3}.
using Digits = std::vector<int>;
 
Digits from_string(const std::string& text) {
    Digits d;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        d.push_back(*it - '0');
    }
    return d;
}
 
std::string to_string(const Digits& d) {
    std::string s;
    for (auto it = d.rbegin(); it != d.rend(); ++it) {
        s.push_back(static_cast<char>('0' + *it));
    }
    return s;
}
 
Digits multiply(const Digits& a, const Digits& b) {
    std::vector<long long> column(a.size() + b.size(), 0);
    for (std::size_t i = 0; i < a.size(); ++i) {
        for (std::size_t j = 0; j < b.size(); ++j) {
            column[i + j] += static_cast<long long>(a[i]) * b[j];
        }
    }
    Digits result;
    long long carry = 0;
    for (long long value : column) {
        long long total = value + carry;
        result.push_back(static_cast<int>(total % 10));
        carry = total / 10;
    }
    while (carry > 0) {
        result.push_back(static_cast<int>(carry % 10));
        carry /= 10;
    }
    while (result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }
    return result;
}
 
int main() {
    Digits a = from_string("12345678901234567890");
    Digits b = from_string("98765432109876543210");
    std::cout << "a * b = " << to_string(multiply(a, b)) << "\n";
 
    Digits zero = from_string("0");
    std::cout << "0 * b = " << to_string(multiply(zero, b)) << "\n";
 
    Digits p = from_string("18446744073709551616");
    std::cout << "2^64 squared = " << to_string(multiply(p, p)) << "\n";
    return 0;
}

Output from a run:

a * b = 1219326311370217952237463801111263526900
0 * b = 0
2^64 squared = 340282366920938463463374607431768211456

The product of two 20-digit numbers has 40 digits here, and the program produced the exact value. The last line is 2 to the power 128, which is the square of 2 to the power 64. The 0 * b line shows the trimming loop at work: without it, the product of zero and a 20-digit number would be a string of 21 zeros.

The code keeps each digit as an int in a std::vector (a list that grows as needed), not a character. This makes the multiplication direct, because a[i] * b[j] multiplies two numbers instead of a character and a number.

Common mistakes

Parsing a long string with a built-in conversion. Functions such as std::stoull convert text to a built-in integer and fail when the value is too large, by throwing an exception (an error that stops the program unless it is caught). The program below tries to read a 30-digit number:

#include <iostream>
#include <string>
 
int main() {
    std::string big = "123456789012345678901234567890";
    unsigned long long value = std::stoull(big);
    std::cout << value << "\n";
    return 0;
}

The program stops with this output:

terminate called after throwing an instance of 'std::out_of_range'
  what():  stoull

The largest 64-bit unsigned value has 20 digits, so a 30-digit string cannot be converted. The fix is to keep the number as a digit container from the start, and never convert it to a built-in type.

Forgetting the last carry. A loop that adds digits must still run after the shorter number runs out, while a carry is waiting. The condition i < n || carry > 0 in add_digits covers this. If the loop stopped at n, then 99 plus 1 would produce the two digits 00 and lose the leading 1.

Printing the stored order. The digits are stored least significant first, so printing the container directly shows the number backwards. The number 10 to the power 20 is stored as 20 zeros followed by a 1, so printing that order shows 00000000000000000001 instead of 100000000000000000000. Reverse the container before printing, as reverse_for_display does, or print from the last element to the first.

Leaving leading zeros in a result. Multiplying by zero gives a longer string of zeros unless the zeros are removed. The trimming loop in multiply removes them, and it keeps one digit so that zero still prints as 0.

Using __int128 on a compiler that does not have it. The type is not part of standard C++. Code that uses it fails to compile on compilers without the extension. If the program must run on more than one compiler, use the digit container.

Practice

Exercise 1. Which is the largest factorial that fits in a std::uint64_t? Use the program above, and check your answer against the output.

Show the answer

It is 20!, which is 2432902008176640000. The program printed 21! as 14197454024290336768, which is wrong, so 21! does not fit.

Exercise 2. Using multiply_digits_by_small, compute 2 to the power 100 by starting from "1" and multiplying by 2 one hundred times. Print the value, then add up its digits.

Show the answer

Multiply by 2 in a loop of 100 steps, reverse the result for display, then add the digits. The value is 1267650600228229401496703205376, and the digit sum is 115.

Exercise 3. Explain why std::stoull("123456789012345678901234567890") fails. Give the number of digits in the largest unsigned long long.

Show the answer

The string has 30 digits, but the largest unsigned long long is 18446744073709551615, which has 20 digits. The value is too large for the type, so std::stoull throws std::out_of_range.

Exercise 4. Using unsigned __int128 and the to_string_u128 function, compute 2 to the power 120 and print it.

Show the answer

Start with unsigned __int128 v = 1;, multiply by 2 a total of 120 times, then print to_string_u128(v). The output is 1329227995784915872903807060280344576. This value fits because it is below the unsigned 128-bit limit of about 3.4 times 10 to the power 38.

Exercise 5. Add two digit strings by hand in your head: 999 and 1. Then write the column steps the way add_digits does. How many digits does the result have?

Show the answer

The columns are 9 + 1 = 10, which writes 0 and carries 1. The next column is 9 + 0 + 1 = 10, which writes 0 and carries 1. The next is 9 + 0 + 1 = 10, which writes 0 and carries 1. The carry then writes a final 1. The result is 1000, which has 4 digits, one more than the longest input.

Summary

• A 64-bit integer overflows silently for values such as 21!, so it is not enough for some calculations.
• unsigned __int128 extends the range to about 3.4 times 10 to the power 38, but it is a GCC and Clang extension and standard streams cannot print it.
• A digit container stores each digit in order, with the least significant digit first, and does addition and multiplication column by column with carries.
• Multiplying two long numbers means collecting column sums and then resolving the carries in one pass.
• Parsing a too-long string into a built-in type throws an exception, so keep long numbers as digit containers.