In C or C++, there exist various data types such as integers, long, float, characters, etc. Each data type consumes a specific amount of memory and has a predefined range of values it can store.
For instance, an integer requires 4 bytes of storage, allowing for values ranging 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 numerous scenarios where the big integer data type finds utility, such as computing the Catalan or Fibonacci sequence for large numbers, or determining the factorial of a significant integer. Storing the substantial number in string format enables the execution of various operations as needed.
1. Getting the Fibonacci number
We have the capability to obtain a substantial Fibonacci value by employing a large 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 are able to calculate the 100th Fibonacci number, which is extremely large, by utilizing a BigInteger data type.
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:
