How to handle big integers in C ++
Published: 2021-04-18 16:05:11

### 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<sup>9</sup>*
- *long int* : approx *10<sup>12</sup>*
- *long long int* : approx *10<sup>18</sup>*

that means we can only store a maximum of *10<sup>18</sup>* 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<sup>7</sup> items, so if we store each digit of our number into each of the memory locations then we will able to store 10<sup>7</sup> 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

![](https://media.giphy.com/media/S5yqNNTQlEZfqQ7InC/giphy.gif)


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

![](https://media.giphy.com/media/11sBLVxNs7v6WA/giphy.gif)

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.*

![](https://media.giphy.com/media/CjmvTCZf2U3p09Cn0h/giphy.gif)


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