# Some Programming Questions Related to Operations with Big Integers

## Contents

The C++ standard library doesn’t support big integer operations such as addition and multiplication. In this post, I will show how to solve such problems in C++.

# Big integer addition

The built in integer types in C++ are mainly `short`

, `int`

, `long`

and `long long`

. These types can only represent relatively small integers. If we store big integers in these types, integer overflow will occur. As a solution, we can store big integers as strings and do integer addition the same way as we do in paper.

The following code accept two integers represented as strings and return their sum as a string,

```
string bigIntAddition(const string& num1, const string& num2){
string result;
int i = static_cast<int>(num1.size() - 1);
int j = static_cast<int>(num2.size() - 1);
int carry = 0;
while (i >= 0 or j >= 0 or carry != 0){
int sum = (i < 0 ? 0 : num1[i--] - '0') + (j < 0 ? 0 : num2[j--] - '0') + carry;
result += ((sum % 10) + '0');
carry = sum / 10;
}
std::reverse(result.begin(), result.end());
return result;
}
```

# Big integer multiplication

Integer multiplication is bit more complex, if two integers have $m$ and $n$ digits, then the final result have a maximum of $m + n$ digits. One post on leetcode gives an excellent explanation of how to do mulitiplication manually, digit by digit. The basic idea is this >Start from the least significant digit of both integers, and calculate their product. If the indices of the digits are $i$, $j$, then the product will be added to indices $i+j$ and $i+j+1$.

This is a repeated process where each digit in the result is gradually built by addition. Until we finished the process, the digits are changing their values continuously.

Following is the code to do interger(expresses as string) multiplications,

```
string bigIntMultiplication(const string& num1, const string& num2){
if (num1 == "0" or num2 == "0"){
return "0";
}
int N = static_cast<int>(num1.size());
int M = static_cast<int>(num2.size());
vector<int> result(N+M, 0);
for (int i = N-1; i >= 0; --i){
for (int j = M-1; j >= 0; --j){
int tmp = (num1[i] - '0') * (num2[j] - '0');
int sum = tmp + result[i+j+1];
result[i+j+1] = sum % 10;
result[i+j] += sum / 10;
}
}
// in case the result only have N+M-1 digits or one of num is zero
ostringstream out;
int i = 0;
while (result[i] == 0) {++i;}
for (; i != N+M; ++i){
out << result[i];
}
return out.str();
}
```

# Factorial of n

Factorial increases really fast, for example, the factorial of `100!`

has 158 digits. In order to represent such big integer, we can use an array to store its digit separately. Below is an algorithm to find the factorial of `n`

,

- create an array
`res[N]`

big enough to store all the digits in`n!`

, initialize`res[0]`

to 1 - let
`m`

be the number of digits that current result takes up, the initialize`m`

to be 1 - for
`num`

from 2 to n

- initialize
`carry`

to 0 - for each digit in current result (i.e., from res[0] to res[m-1]), let cur = num*res[j] + carry, put last digit of cur in res[j], put other digit in cur in carry.
- if carry is not zero, put every digit in carry into res by incresing m

- initialize

In order to simplify computation, we store all the digits of the result in reverse order, which means that the least significant digit is stored in the smallest index of the array, kind of like “small endian”. In each iteration, we also keep track of how many digits the current result takes up. The following code is an implementation of this idea,

```
string factorial(int n){
const int N = 10000;
int* digits = new int[N];
digits[0] = 1;
int m = 1;
for (int num = 2; num <= n; ++num){
// multipy num and every digit in current result
int carry = 0;
for (int j = 0; j != m; ++j){
int cur += num*digits[j];
digits[j] = cur % 10;
carry = cur / 10;
}
// if carry is not zeros, span current result using digits in carry
while (carry){
digits[m++] = carry % 10;
carry /= 10;
}
}
ostringstream out;
for (int i = m-1; i >= 0; --i){
out << digits[i];
}
delete[] digits;
return out.str();
}
```