Summary

The provided content outlines a method for implementing big integer arithmetic in C++ using std::vector.

Abstract

The article "Fast implementation of big integers in C++: Part 1" discusses the practical implementation of large integer data types in C++, a language that does not natively support them. It details how to use std::vector to store and manipulate large integers, allowing for dynamic resizing and efficient operations. The author explains the necessity of defining a new data type, overloading operators, and using the decimal numeral system for digit storage. The article covers the implementation of basic arithmetic operations such as addition, subtraction, multiplication, and division, providing code examples and discussing the time complexity of these operations. The focus is on handling positive integers, with a teaser for future discussion on negative numbers.

Opinions

The author emphasizes the importance of using std::vector for its dynamic size capabilities and ease of digit manipulation.
The article suggests that inserting zero digits at the end of a number rather than the beginning is more efficient, with a time complexity of O(n) versus O(n²).
The author's approach to arithmetic operations, such as addition and subtraction, involves reversing the numbers, equalizing their lengths, and then processing the carry or borrow.
For multiplication, the author opts for the long multiplication algorithm due to its simplicity, acknowledging that it may not be the fastest method.
The division operation is described using the long division algorithm, with a note on the potential inefficiency of using std::vector::erase and the recommendation to reverse the result to optimize zero digit removal.
The article concludes by inviting readers to engage with the content by asking questions, indicating a community-oriented and educational intent.

Fast implementation of big integers in C++: Part 1

Background

In this day and age, the large integer data type is supported in several programming languages, such as JavaScript, Python, Java and C#. However, it is still not supported in an old language like C++. This article will show practical ways to implement big integers in C++.

std::vector

In C++, std::vector is a sequence container that encapsulates dynamic size arrays. It supports insertion and removal at the end of the vector.

Below is the time complexity of some vector operations:

Random access — constant 𝓞(1)

Insertion or removal of elements at the end — amortized constant 𝓞(1)

Insertion or removal of elements — linear in the distance to the end of the vector 𝓞(n)

Therefore, std::vector is ideal for the large integer implementation. It is easy to iterate through each digit in a “large integer” and insert or remove digits from a number.

Implementation with std::vector

Firstly, let’s take a look at data input and output. Since C++ does not support large integers, we need to define a new data type and process input by storing the number into a string before copying it to a vector. We also need to overload operators to do that. Therefore, don’t forget to use the typedef keyword. Because each digit is stored separately in a vector, the decimal numeral system, also known as the base-ten positional numeral system, should be used.

typedef vector<int> BigInteger;

const int BASE = 10;

istream& operator >> (istream &cin, BigInteger &num)
{
    string s;
    cin >> s;

    num.clear();
    
    for (int i = 0; i < s.length(); i++)
        num.push_back(s[i] - '0');
    
    return cin;
}

Similarly, for output:

ostream& operator << (ostream &cout, BigInteger num)
{
    for (int i = 0; i < num.size(); i++)
        cout << num[i];
    
    return cout;
}

Before moving on to four basic arithmetic operations (addition, subtraction, multiplication and division), let’s create some functions to support those operations.

void insert_a_zero(BigInteger &num) 
{
    num.push_back(0);
}

void insert_zeros(BigInteger &num, int new_size)
{
    while (num.size() < new_size)
        insert_a_zero(num);
}

void remove_zeros(BigInteger &num)
{
    while (num.back() == 0)
        num.pop_back();
}

Addition:

It is essential to insert zero digits into the given numbers as the lengths of those numbers should be equalized. However, inserting zero digits into the beginning of a number can take O(n²) time complexity in total. If we insert them at the end, it only takes O(n) time complexity in total. Therefore, we should reverse the numbers before equalizing their lengths and calculating the sum. After that, don’t forget to process the carry, remove the unnecessary zeros. Then, we need to reverse the result (since push_back, instead of insert, is used to take O(n) time complexity in total)

BigInteger operator + (BigInteger a, BigInteger b)
{
    BigInteger res;

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int common_size = max(a.size(), b.size());

    insert_zeros(a, common_size);
    insert_zeros(b, common_size);

    for (int i = 0; i < common_size; i++) 
        res.push_back(a[i] + b[i]);

    insert_a_zero(res);

    for (int i = 0 ;i < common_size; i++)
    {
        res[i + 1] += res[i] / BASE;
        res[i] %= BASE;
    }

    remove_zeros(res);

    reverse(res.begin(), res.end());

    return res;
}

Subtraction:

The subtraction operation is relatively similar to the addition. However, we will insert the difference of digits into the vector. Also, the borrow, instead of the carry, is processed. In case a > b:

BigInteger operator - (BigInteger a, BigInteger b)
{
    BigInteger res;

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int common_size = max(a.size(), b.size());

    insert_zeros(a, common_size);
    insert_zeros(b, common_size);

    for (int i = 0; i < common_size; i++) 
        res.push_back(a[i] - b[i]);

    insert_a_zero(res);

    for (int i = 0; i < common_size; i++)
    {
        if (res[i] < 0)
        {
            res[i] += BASE;
            res[i + 1] --;
        }
    }
    
    remove_zeros(res);

    reverse(res.begin(), res.end());

    return res;
}

Multiplication: For multiplication, we will use the long multiplication algorithm. That is not the fastest, but it can be the simplest.

Between a large integer and an integer

BigInteger operator * (BigInteger a, int b)
{
    BigInteger res;

    int carry = 0;

    for (int i = a.size() - 1; i >= 0; i--)
    {
        int sum = a[i] * b + carry;
        carry = sum / BASE;
        res.push_back(sum % BASE);
    }

    for (; carry > 0; carry /= BASE)
        res.push_back(carry % BASE);

    reverse(res.begin(), res.end());

    return res;
}

Between two large integers:

BigInteger operator * (BigInteger a, BigInteger b)
{
    int max_size = a.size() + b.size();
    
    BigInteger res (max_size, 0);

    for (int i = a.size() - 1; i >= 0; i--)
    {
        for (int j = b.size() - 1; j >= 0; j--)
         res[max_size - 2 - i - j] += a[i] * b[j];
    }
    
    for (int i=0; i<res.size() - 1;i++)
    {
        res[i+1] += res[i]/BASE;
        res[i] %= BASE;
    }
    
    remove_zeros(res);
    
    reverse(res.begin(), res.end());

    return res;
}

Division:

For division, the long division algorithm will be used.

Between a large integer and an integer.

BigInteger operator / (BigInteger a, int b)
{
    BigInteger res;

    for (int i = 0, sum = 0; i < a.size(); i++)
    {
        sum = sum * 10 + a[i];
        res.push_back(sum / b);
        sum -= res.back() * b;
    }

    reverse(res.begin(), res.end());

    remove_zeros(res);

    reverse(res.begin(), res.end());

    return res;
}

For the long division algorithm, when we only use std::vector::erase, it can take O(n²) time complexity in total to remove zero digits at the beginning. For this reason, we need to reverse the result and remove those digits.

Four basic arithmetic operations for big integers are above: addition, subtraction, multiplication and division. Please note that the mentioned examples are just for positive integers. We will move on to negative numbers in another article.

Thank you for reading. If you have any questions, do not hesitate to comment below!