Bigint (BIG INTEGERS) in C with Example
The maximum number of digits that a long, long int can have in C/C++ is 20. The issue is how to store the 22-digit number, which is difficult to do with any simple type. Therefore, let's create a new data type called BigInt to address this type of problem. A few fundamental operations are applied to the new data type in this article.
- Adding two large numbers
- Subtracting two large numbers
- Multiplying two large numbers
- Divide two significant digits.
- Two large integers modulo
- Increase a large number by one.
- a large integer's square root
- To determine which is greater and which is smaller, compare two large integers.
- Determine the huge integer's digit count.
- Show the large integer.
- Make a huge integer from an integer.
Applications of BigInt
Here are some straightforward uses for the new BigInt data type:
- Calculating a large number's Fibonacci number.
- Calculating a huge integer's Catalan number.
- Calculating a large integer's factorial.
Approach
The features listed below are being implemented to produce a big new integer data type:
- Using C++ strings, we can store very large numbers as well because we can save our numbers as characters (in reverse order for efficiency).
- Use the fundamentals of addition to add or remove two large integers, which states to add the corresponding two digits and, if any carry is produced, to add it to the sum of the subsequent digits. Repeat this process until all digits have been added or subtracted.
- Like this, when multiplying two numbers, follow the basic mathematical procedure, which dictates to multiply each digit of one number by the other entire number before adding all the results.
- On BigInt, the following operations are being carried out:
- Defining a few large integers
- Examining the huge integer's digit count.
- Decrementation, Post-Incrementation, or Both
- Two large integers are added.
- Taking away two large integers.
- Two large integers being multiplied.
- Split two significant digits of two large integers modulo
- A large integer's square root (floor integer value)
- Increase a large number by one.
- Transforming a little integer into a large integer.
- Fibonacci calculations up to 10,000. even 100,000 but more slowly
- Factorial calculations up to 1000.
- Catalan computation up to 1000.
- Comparing the bigger and smaller big integer.
The above method is implemented in C++ as follows:
// C++ programme to put the aforesaid strategy into practise.
#include <bits/stdc++.h>
usingnamespacestd;
classBigInt{
string digits;
public:
BigInt(unsigned longlong n = 0);
BigInt(string &);
BigInt(constchar *);
BigInt(BigInt &);
//Helping Roles:
friendvoid divide_by_2(BigInt &a);
friendboolNull(const BigInt &);
friendintLength(const BigInt &);
intoperator[](constint)const;
/* * * * Operator Overloading * * * */
//Direct responsibility
BigInt &operator=(const BigInt &);
//Post/Pre-Incremental Calculation
BigInt &operator++();
BigInt operator++(int temp);
BigInt &operator--();
BigInt operator--(int temp);
//Subtraction and Addition
friend BigInt &operator+=(BigInt &, const BigInt &);
friend BigInt operator+(const BigInt &, const BigInt &);
friend BigInt operator-(const BigInt &, const BigInt &);
friend BigInt &operator-=(BigInt &, const BigInt &);
//operators for comparison
friendbool operator==(const BigInt &, const BigInt &);
friendbooloperator!=(const BigInt &, const BigInt &);
friendbool operator>(const BigInt &, const BigInt &);
friendbool operator>=(const BigInt &, const BigInt &);
friendbool operator<(const BigInt &, const BigInt &);
friendbool operator<=(const BigInt &, const BigInt &);
//Division and Exponentiation
friend BigInt &operator*=(BigInt &, const BigInt &);
friend BigInt operator*(const BigInt &, const BigInt &);
friend BigInt &operator/=(BigInt &, const BigInt &);
friend BigInt operator/(const BigInt &, const BigInt &);
friend BigInt operator%(const BigInt &, const BigInt &);
friend BigInt &operator%=(BigInt &, const BigInt &);
friend BigInt &operator^=(BigInt &,const BigInt &);
friend BigInt operator^(BigInt &, const BigInt &);
//Function with Square Roots
friend BigInt sqrt(BigInt &a);
friendostream&operator<<(ostream&,const BigInt &);
friendistream&operator>>(istream&, BigInt &);
friend BigInt NthCatalan(int n);
friend BigInt NthFibonacci(int n);
friend BigInt Factorial(int n);
};
BigInt::BigInt(string & s){
digits = "";
int n = s.size();
for (inti = n - 1; i>= 0;i--){
if(!isdigit(s[i]))
throw("ERROR");
digits.push_back(s[i] - '0');
}
}
BigInt::BigInt(unsigned longlong nr){
do{
digits.push_back(nr % 10);
nr /= 10;
} while (nr);
}
BigInt::BigInt(constchar *s){
digits = "";
for (inti = strlen(s) - 1; i>= 0;i--)
{
if(!isdigit(s[i]))
throw("ERROR");
digits.push_back(s[i] - '0');
}
}
BigInt::BigInt(BigInt & a){
digits = a.digits;
}
boolNull(const BigInt& a){
if(a.digits.size() == 1 &&a.digits[0] == 0)
returntrue;
returnfalse;
}
intLength(const BigInt & a){
returna.digits.size();
}
intBigInt::operator[](constint index)const{
if(digits.size() <= index || index < 0)
throw("ERROR");
return digits[index];
}
bool operator==(const BigInt &a, const BigInt &b){
returna.digits == b.digits;
}
booloperator!=(const BigInt &a,const BigInt &b){
return !(a == b);
}
bool operator<(constBigInt&a,constBigInt&b){
int n = Length(a), m = Length(b);
if(n != m)
return n <m;
while(n--)
if(a.digits[n] != b.digits[n])
returna.digits[n] <b.digits[n];
returnfalse;
}
bool operator>(constBigInt&a,constBigInt&b){
return b <a;
}
bool operator>=(constBigInt&a,constBigInt&b){
return !(a < b);
}
bool operator<=(constBigInt&a,constBigInt&b){
return !(a > b);
}
BigInt &BigInt::operator=(const BigInt &a){
digits = a.digits;
return *this;
}
BigInt &BigInt::operator++(){
inti, n = digits.size();
for (i = 0; i< n && digits[i] == 9;i++)
digits[i] = 0;
if(i == n)
digits.push_back(1);
else
digits[i]++;
return *this;
}
BigInt BigInt::operator++(int temp){
BigInt aux;
aux = *this;
++(*this);
returnaux;
}
BigInt &BigInt::operator--(){
if(digits[0] == 0 &&digits.size() == 1)
throw("UNDERFLOW");
inti, n = digits.size();
for (i = 0; digits[i] == 0 &&i<n;i++)
digits[i] = 9;
digits[i]--;
if(n > 1 && digits[n - 1] == 0)
digits.pop_back();
return *this;
}
BigInt BigInt::operator--(int temp){
BigInt aux;
aux = *this;
--(*this);
returnaux;
}
BigInt &operator+=(BigInt &a,const BigInt& b){
int t = 0, s, i;
int n = Length(a), m = Length(b);
if(m > n)
a.digits.append(m - n, 0);
n = Length(a);
for (i = 0; i<n;i++){
if(i< m)
s = (a.digits[i] + b.digits[i]) + t;
else
s = a.digits[i] + t;
t = s / 10;
a.digits[i] = (s % 10);
}
if(t)
a.digits.push_back(t);
returna;
}
BigInt operator+(const BigInt &a, const BigInt &b){
BigInt temp;
temp = a;
temp += b;
returntemp;
}
BigInt &operator-=(BigInt&a,const BigInt &b){
if(a < b)
throw("UNDERFLOW");
int n = Length(a), m = Length(b);
inti, t = 0, s;
for (i = 0; i<n;i++){
if(i< m)
s = a.digits[i] - b.digits[i]+ t;
else
s = a.digits[i]+ t;
if(s < 0)
s += 10,
t = -1;
else
t = 0;
a.digits[i] = s;
}
while(n > 1 &&a.digits[n - 1] == 0)
a.digits.pop_back(),
n--;
returna;
}
BigInt operator-(const BigInt&a,constBigInt&b){
BigInt temp;
temp = a;
temp -= b;
returntemp;
}
BigInt &operator*=(BigInt &a, const BigInt &b)
{
if(Null(a) || Null(b)){
a = BigInt();
returna;
}
int n = a.digits.size(), m = b.digits.size();
vector<int>v(n + m, 0);
for (inti = 0; i<n;i++)
for (int j = 0; j <m;j++){
v[i + j] += (a.digits[i] ) * (b.digits[j]);
}
n += m;
a.digits.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.digits[i] = v[i] ;
}
for (inti = n - 1; i>= 1 && !v[i];i--)
a.digits.pop_back();
returna;
}
BigInt operator*(constBigInt&a,constBigInt&b){
BigInt temp;
temp = a;
temp *= b;
returntemp;
}
BigInt &operator/=(BigInt&a,const BigInt &b){
if(Null(b))
throw("Arithmetic Error: Division By 0");
if(a < b){
a = BigInt();
returna;
}
if(a == b){
a = BigInt(1);
returna;
}
inti, lgcat = 0, cc;
int n = Length(a), m = Length(b);
vector<int>cat(n, 0);
BigInt t;
for (i = n - 1; t * 10 + a.digits[i] <b;i--){
t *= 10;
t += a.digits[i] ;
}
for (; i>= 0; i--){
t = t * 10 + a.digits[i];
for (cc = 9; cc * b >t;cc--);
t -= cc * b;
cat[lgcat++] = cc;
}
a.digits.resize(cat.size());
for (i = 0; i<lgcat;i++)
a.digits[i] = cat[lgcat - i - 1];
a.digits.resize(lgcat);
returna;
}
BigInt operator/(const BigInt &a,const BigInt &b){
BigInt temp;
temp = a;
temp /= b;
returntemp;
}
BigInt &operator%=(BigInt&a,const BigInt &b){
if(Null(b))
throw("Arithmetic Error: Division By 0");
if(a < b){
a = BigInt();
returna;
}
if(a == b){
a = BigInt(1);
returna;
}
inti, lgcat = 0, cc;
int n = Length(a), m = Length(b);
vector<int>cat(n, 0);
BigInt t;
for (i = n - 1; t * 10 + a.digits[i] <b;i--){
t *= 10;
t += a.digits[i];
}
for (; i>= 0; i--){
t = t * 10 + a.digits[i];
for (cc = 9; cc * b >t;cc--);
t -= cc * b;
cat[lgcat++] = cc;
}
a = t;
returna;
}
BigInt operator%(const BigInt &a,BigInt&b){
BigInt temp;
temp = a;
temp %= b;
returntemp;
}
BigInt &operator^=(BigInt &a,const BigInt & b){
BigInt Exponent, Base(a);
Exponent = b;
a = 1;
while(!Null(Exponent)){
if(Exponent[0] & 1)
a *= Base;
Base *= Base;
divide_by_2(Exponent);
}
returna;
}
BigInt operator^(BigInt &a,BigInt& b){
BigInt temp(a);
temp ^= b;
returntemp;
}
void divide_by_2(BigInt &a){
int add = 0;
for (inti = a.digits.size() - 1; i>= 0;i--){
int digit = (a.digits[i] >> 1) + add;
add = ((a.digits[i] & 1) * 5);
a.digits[i] = digit;
}
while(a.digits.size() > 1 && !a.digits.back())
a.digits.pop_back();
}
BigInt sqrt(BigInt & a){
BigInt left(1), right(a), v(1), mid, prod;
divide_by_2(right);
while(left <= right){
mid += left;
mid += right;
divide_by_2(mid);
prod = (mid * mid);
if(prod <= a){
v = mid;
++mid;
left = mid;
}
else{
--mid;
right = mid;
}
mid = BigInt();
}
returnv;
}
BigInt NthCatalan(int n){
BigInt a(1),b;
for (inti = 2; i<= n;i++)
a *= i;
b = a;
for (inti = n + 1; i<= 2 * n;i++)
b *= i;
a *= a;
a *= (n + 1);
b /= a;
returnb;
}
BigInt NthFibonacci(int n){
BigInt a(1), b(1), c;
if(!n)
returnc;
n--;
while(n--){
c = a + b;
b = a;
a = c;
}
returnb;
}
BigInt Factorial(int n){
BigInt f(1);
for (inti = 2; i<= n;i++)
f *= i;
returnf;
}
istream&operator>>(istream&in,BigInt&a){
string s;
in >>s;
int n = s.size();
for (inti = n - 1; i>= 0;i--){
if(!isdigit(s[i]))
throw("INVALID NUMBER");
a.digits[n - i - 1] = s[i];
}
returnin;
}
ostream&operator<<(ostream&out,const BigInt &a){
for (inti = a.digits.size() - 1; i>= 0;i--)
cout<< (short)a.digits[i];
returncout;
}
intmain()
{
BigInt first("12345");
cout<< "The number of digits"
<< " in first big integer = "
<< Length(first) << '\n';
BigInt second(12345);
if (first == second) {
cout<< "first and second are equal!\n";
}
else
cout<< "Not equal!\n";
BigInt third("10000");
BigInt fourth("100000");
if (third < fourth) {
cout<< "third is smaller than fourth!\n";
}
BigInt fifth("10000000");
if (fifth > fourth) {
cout<< "fifth is larger than fourth!\n";
}
cout<< "first = " << first << '\n';
cout<< "second = " << second << '\n';
cout<< "third = " << third << '\n';
cout<< "fourth = " << fourth<< '\n';
cout<< "fifth = " << fifth<< '\n';
first++;
cout<< "After incrementing the"
<< " value of first is : ";
cout<< first << '\n';
BigInt sum;
sum = (fourth + fifth);
cout<< "Sum of fourth and fifth = "
<< sum << '\n';
BigInt product;
product = second * third;
cout<< "Product of second and third = "
<< product << '\n';
cout<< "-------------------------Fibonacci"
<< "------------------------------\n";
for (inti = 0; i<= 100; i++) {
BigInt Fib;
Fib = NthFibonacci(i);
cout<< "Fibonacci " <<i<< " = " << Fib<<'\n';
}
cout<< "-------------------------Catalan"
<< "------------------------------\n";
for (inti = 0; i<= 100; i++) {
BigInt Cat;
Cat = NthCatalan(i);
cout<< "Catalan " <<i<< " = " << Cat<<'\n';
}
cout<< "-------------------------Factorial"
<< "------------------------------\n";
for (inti = 0; i<= 100; i++) {
BigInt fact;
fact = Factorial(i);
cout<< "Factorial of "
<<i<< " = ";
cout<< fact << '\n';
}
}
Output: