How to handle big integers in C ++

why we need to understand this topic ?

If we take a look on the number limits of integer data type of C++, you'll find something like:

• int : approx 10⁹
• long int : approx 10¹²
• long long int : approx 10¹⁸

that means we can only store a maximum of 10¹⁸ integer i.e. only a number upto 19 digits. What if we have to deal with numbers greater than 19 digits ?

well using standard data types for such problems will lead to overflow. That's why languages like Python, Java, Ruby, etc. have libraries like Big integers or their variables are able to handle such large numbers.

In this article we'll learn how to store such large numbers in C++ and perform some fundamental operations on them.

Prerequisites

• Basic STL (vectors) || you can also use arrays
• Functions
• Loops

How to store such large integers ?**

As we saw in standard data types of integer we can only store number upto 19 digits so in order to store greater than 19 digits we will use vectors and string for storing and taking input respectively. As we know in vectors / arrays items are stored in contiguous memory locations and we can create a vector upto 10⁷ items, so if we store each digit of our number into each of the memory locations then we will able to store 10⁷ digits. OMG it is much much greater than just 19 digits.

Remember we are storing digits of our number into each memory locations, not entire number into one memory location.

Below is a code sample to explain this

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string num = "123499999999999999999999999999999999";  /* taking input as a string */

    vector <int> number;

    for(int i = 0; i < num.size(); i++)
        number.push_back(num[i] - '0');  /* converting from character to int (ASCII conversion) */

    for(auto i : number)   /* looping on each item in vector */
        cout<<i;
}

/* output: 123456789 */

So now we know how to store such large numbers and that's not the end of the story.
As we saw we need to use a contiguous memory locations to store such large numbers in C++, that's why operating on such numbers gets complicated as compare to handling just simple numbers of int data type.
For doing operations we need to build our own logic like how to add or subtract such numbers.

Let's dive into how to Add such numbers

before going ahead I recommend you to take a pen and a paper and add 12345 + 6789, like we use to do in our childhood, step by step

Algorithm:

• take input and store both numbers into two different vectors / arrays.
• reverse the vector (because we add from right to left).
• initiate a variable to store carry.
• store the sizes of vectors as min_len, max_len.
• first loop till min_len, do addition of respective digits and store them into another vector (answer).
• loop from min_len to max_len and store the sum of rest digits + carry into answer vector.
• after addition of all digits if still carry remain then store it into answer vector.
• again reverse the answer vector (because we previously reversed our two vectors)
• return the answer vector.

here's the code with comments for better understanding of the logic

#include<bits/stdc++.h>
using namespace std;

vector <int> add(vector<int> x, vector<int> y) /* function to add two vectors */
{
    reverse(x.begin(),x.end());  /* reversing since we add from right to left */
    reverse(y.begin(), y.end());

    vector<int> ans; /* vector to store the answer */

    int min_len = min(x.size(), y.size()); /* calculating min_len and max_len from sizes of both vectors */
    int max_len = max(x.size(), y.size());
    int carry = 0;  /* initially carry will be 0 */

    for(int i=0;i<min_len;i++)   /* looping till minimum digits of both the numbers and doing addition */
    {
        int digit_sum = x[i] + y[i] + carry;
        carry = digit_sum / 10;    /* tens digit of digit_sum will be carry */
        ans.push_back(digit_sum % 10);  /* we store the once digit as answer */
    }

    /* handling remaining digits */

    if(x.size() > y.size())
    {
        for(int i=min_len; i < x.size(); i++)
        {
            int digit_sum = x[i] + carry;
            carry = digit_sum / 10;
            ans.push_back(digit_sum % 10);
        }
    }

    if(x.size() < y.size())
    {
        for(int i=min_len; i < y.size(); i++)
        {
            int digit_sum = y[i] + carry;
            carry = digit_sum / 10;
            ans.push_back(digit_sum % 10);
        }
    }

    /* handling remaining carry */

    while(carry)
    {
        ans.push_back(carry % 10);
        carry = carry / 10;
    }

    reverse(ans.begin(), ans.end()); /* reversing the answer vector to get correct answer vector */

    return ans;

}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> a2,b2;

    for(int i=0;i<a.size();i++)  /* storing characters as integers into vector */
        a2.push_back(a[i] - '0');

    for(int i=0; i<b.size(); i++)
        b2.push_back(b[i] - '0');

    vector <int> result = add(a2, b2); /* calling and passing both vectors to add */

    for(auto i: result) /* printing output */
        cout<<i;
}

And we are done.

Yeah exactly I also never thought addition can be so complex, but if take a closer look all we did is just fundamental addition that we did in our childhood, but never considered so many cases.

So let's head forwards and understand another important concept, I bet when you started learning C++ you must made a program to calculate factorial of a number, the flaw of that program is that you only calculate factorials upto number 20, on inputting 21 and onwards you'll face overflow.

Now we are going to remake that same program but this time it'll be able to calculate factorials of much bigger numbers.

Computing factorials of large integers**

Idea is same as before, we take a number and store its factorial into vector, but this time instead of calculating addition we'll go for multiplication.

Algorithm:

• input the number.
• initiate answer vector and put 1 in it. (because multiplying any number with leads to same number )
• loop from i=2 to number and each time multiplies the answer vector with i .
• reverse the answer vector for correct answer.
• print output.

here's the code for above problem

#include<bits/stdc++.h>
using namespace std;


void factorial(vector<int> &v, int x) /* passing with reference so that changes also occur in original vector */
{
    int carry = 0; /* initially carry will be 0 */

    /* doing fundamental way of multiplication */
    for(int i = 0; i < v.size(); i++)
    {
        int digit_product = v[i]*x + carry;
        carry = digit_product / 10;
        v[i] = (digit_product % 10);
    }

    /* handling if carry remains */

    while(carry)
    {
        v.push_back(carry % 10); 
        /* push_back() adds number at the end of vector but in multiplication we put carry in front
        so we need to reverse the vector to get the correct answer */
        carry /= 10;
    }
}

int main()
{
    int n;
    cin >> n;

    vector <int> ans; /* vector to store answer */
    ans.push_back(1);

    for(int i = 2; i <= n; i++) /* looping from 2 to n */
    {
        factorial(ans, i); /* passing vector and i to multiply the number in vector with i */
    }

    reverse(ans.begin(), ans.end()); /* reversing the vector to get the correct answer */

    for(auto i:ans)
        cout<<i;
}

try this code on your own and grasp the concept behind it, I make it as clear as I can with proper comments but you need to visualize the flow using pen and paper, doing the fundamental multiplication of a digits inside vector by a number.

What's next !

If you are ready now and feeling confident with this, I have a homework for you.

Try subtraction of two big integers on your own.

And yeah that was all for this now!

*If you are still reading, make sure to follow me for more as I have some exciting stuff coming up every weekend. See ya next time! *