In C or C++, we have different types of data types like integers, long, float, characters etc. Each data type occupies some amount of memory. There is a range of numbers that can be occupied by that data type.
For example, an integer occupies 4 bytes of memory so that we can have numbers from -2147483648 to +2147463647.
So, if we want to have an integer where the number of digits in decimal format is 22 or more, then we cannot store it using primitive data types. To resolve this problem, we have BigInt data type which can do the following operations:
- Adding two big integers
- Subtracting the two big integers.
- Multiplying and dividing the two big integer
- Getting the square root of big integers.
- Printing the big integer or converting the integer to a big integer.
There are a lot of applications where we can use the big integer data type, like getting the Catalan or Fibonacci of a large number or getting the factorial of a big integer. We will store the large number in the string format so that we can do every operation we want.
1. Getting the Fibonacci number
We can get a huge Fibonacci number using a big integer data type.
C++ Example:
#include <bits/stdc++.h>
using namespace std;
class BigInt{
string num;
public:
BigInt(unsigned long long n = 0);
BigInt(BigInt &);
friend void divideByTwo(BigInt &a);
friend int Length(const BigInt &);
BigInt &operator=(const BigInt &);
friend BigInt &operator+=(BigInt &, const BigInt &);
friend ostream &operator<<(ostream &,const BigInt &);
friend BigInt getNthFibNum(int n);
};
BigInt::BigInt(unsigned long long nr){
do{
num.push_back(nr % 10);
nr /= 10;
} while (nr);
}
BigInt::BigInt(BigInt & a){
num = a.num;
}
int Length(const BigInt & a){
return a.num.size();
}
BigInt &BigInt::operator=(const BigInt &a){
num = a.num;
return *this;
}
BigInt &operator+=(BigInt &a,const BigInt& b){
int t = 0, s, i;
int n = Length(a), m = Length(b);
if(m > n)
a.num.append(m - n, 0);
n = Length(a);
for (i = 0; i < n;i++){
if(i < m)
s = (a.num[i] + b.num[i]) + t;
else
s = a.num[i] + t;
t = s / 10;
a.num[i] = (s % 10);
}
if(t)
a.num.push_back(t);
return a;
}
BigInt operator+(const BigInt &a, const BigInt &b){
BigInt temp;
temp = a;
temp += b;
return temp;
}
void divideByTwo(BigInt & a){
int add = 0;
for (int i = a.num.size() - 1; i >= 0;i--){
int digit = (a.num[i] >> 1) + add;
add = ((a.num[i] & 1) * 5);
a.num[i] = digit;
}
while(a.num.size() > 1 && !a.num.back())
a.num.pop_back();
}
BigInt getNthFibNum(int n){
BigInt a(1), b(1), c;
if(!n)
return c;
n--;
while(n--){
c = a + b;
b = a;
a = c;
}
return b;
}
ostream &operator<<(ostream &out,const BigInt &a){
for (int i = a.num.size() - 1; i >= 0;i--)
cout << (short)a.num[i];
return cout;
}
int main(){
for (int i = 0; i <= 100; i++) {
BigInt Fib;
Fib = getNthFibNum(i);
cout << "Fibonacci number at " << i << " = " << Fib<<'\n';
}
}
Output:
Explanation:
We can get the 100 th Fibonacci number which is huge, but with the help of a big Integer, we can do this.
2. Getting Factorial of a large number
C ++ Example:
#include <bits/stdc++.h>
using namespace std;
class BigInt{
string num;
public:
BigInt(unsigned long long n = 0);
friend void divideByTwo(BigInt &a);
friend bool Null(const BigInt &);
BigInt &operator=(const BigInt &);
friend BigInt &operator*=(BigInt &, const BigInt &);
friend ostream &operator<<(ostream &,const BigInt &);
friend BigInt getFactorial(int n);
};
BigInt::BigInt(unsigned long long nr){
do{
num.push_back(nr % 10);
nr /= 10;
} while (nr);
}
bool Null(const BigInt& a){
if(a.num.size() == 1 && a.num[0] == 0)
return true;
return false;
}
BigInt &BigInt::operator=(const BigInt &a){
num = a.num;
return *this;
}
BigInt &operator*=(BigInt &a, const BigInt &b)
{
if(Null(a) || Null(b)){
a = BigInt();
return a;
}
int n = a.num.size(), m = b.num.size();
vector<int> v(n + m, 0);
for (int i = 0; i < n;i++)
for (int j = 0; j < m;j++){
v[i + j] += (a.num[i] ) * (b.num[j]);
}
n += m;
a.num.resize(v.size());
for (int s, i = 0, t = 0; i < n; i++)
{
s = t + v[i];
v[i] = s % 10;
t = s / 10;
a.num[i] = v[i] ;
}
for (int i = n - 1; i >= 1 && !v[i];i--)
a.num.pop_back();
return a;
}
void divideByTwo(BigInt & a){
int add = 0;
for (int i = a.num.size() - 1; i >= 0;i--){
int digit = (a.num[i] >> 1) + add;
add = ((a.num[i] & 1) * 5);
a.num[i] = digit;
}
while(a.num.size() > 1 && !a.num.back())
a.num.pop_back();
}
BigInt getFactorial(int n){
BigInt f(1);
for (int i = 2; i <= n;i++)
f *= i;
return f;
}
ostream &operator<<(ostream &out,const BigInt &a){
for (int i = a.num.size() - 1; i >= 0;i--)
cout << (short)a.num[i];
return cout;
}
int main()
{
for (int i = 0; i <= 100; i++) {
BigInt fact;
fact = getFactorial(i);
cout << "Factorial of "
<< i << " = ";
cout << fact << '\n';
}
}
Output: