Logo
×

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.

  1. Adding two large numbers
  2. Subtracting two large numbers
  3. Multiplying two large numbers
  4. Divide two significant digits.
  5. Two large integers modulo
  6. Increase a large number by one.
  7. a large integer's square root
  8. To determine which is greater and which is smaller, compare two large integers.
  9. Determine the huge integer's digit count.
  10. Show the large integer.
  11. Make a huge integer from an integer.

Applications of BigInt

Here are some straightforward uses for the new BigInt data type:

  1. Calculating a large number's Fibonacci number.
  2. Calculating a huge integer's Catalan number.
  3. Calculating a large integer's factorial.

Approach

The features listed below are being implemented to produce a big new integer data type:

  1. Using C++ strings, we can store very large numbers as well because we can save our numbers as characters (in reverse order for efficiency).
  2. 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.
  3. 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.
  4. 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:

Bigint (BIG INTEGERS) in C with Example Bigint (BIG INTEGERS) in C with Example Bigint (BIG INTEGERS) in C with Example Bigint (BIG INTEGERS) in C with Example Bigint (BIG INTEGERS) in C with Example Bigint (BIG INTEGERS) in C with Example

Related Topics

C program to Store Information of Students Using Structure

What is the Structure in C? User-defined data types include structures. Structures aid your ability to combine things of various categories into a single group. Like arrays, it operates similarly. A...

3 minutes read.

fork() in C

Introduction To create a new function in the system, there is a need for a system call, i.e. fork system call. It is also known as the child process. These child...

2 minutes read.

How to get ASCII value in C

For text data on computers and the internet, ASCII (American Standard Code for Information Interchange). It is the most widely used character encoding standard. One hundred twenty-eight alphabetic, numeric, special...

3 minutes read.

Type qualifiers in C

Type qualifiers in C: In the C programming language, type qualifiers are the keywords that prepend to the variables to change their accessibility, i.e., we can tell that the type...

4 minutes read.

Find reverse of an array in C using functions

Introduction: Here, we describe how to find the reverse array in C using functions. Suppose you have an array with n elements. I need to display the elements present in...

3 minutes read.

Structure in C

Why Structure came into the picture? In the actual world, we deal with entities that are collections of objects rather than tiny bits of data like integers, characters, floats, etc. So,...

4 minutes read.

Cbrt() function in C

Introduction: The Cbrt is a function used in C programming language. The cbrt() function is a math function. Using the cbrt function, we can do the cube root of a function. This...

4 minutes read.

C Language Environment Setup

To compile C program, we must have GCC compiler installed on our machine. In this C tutorial, all the examples are compiled and tested using GCC compiler. Although we can...

3 minutes read.

Type Casting in C

Type casting is a way to convert a variable from one data type to another data type.Syntax: (type) expression;     Example: #include <stdio.h> int main() { int a,b; float sum; printf("Example of Type Casting\n"); printf("Enter any integer nos:"); scanf("%d",&a,&b); sum=a+b; printf("Sum: %f",sum); return 0; } Output Example...

1 minute read.

C Program to Find the Largest Number using Ternary Operator

In this tutorial, we will write some program to determine which of the provided integers is larger using the ternary operator, also known as the conditional operator in C. Ternary Operator: The ternary...

3 minutes read.

Prime Number Program in C using for Loop

In this article, we will know about the procedure of checking whether a natural number inputted by the user is a prime number or non-prime number. Definition of the prime number A...

3 minutes read.

C/C++ Program to Find the Size of int, float, double and char

In this tutorial, we will learn how to use the sizeof operator to determine the size of each variable. Program to Determine Variable Size Write a C or C++ program to determine the...

2 minutes read.

tolower() Function in C

The tolower() capability is characterized in the ctype.h header document. In the event that the person passed is a capitalized letter set, the tolower() capability switches capitalized letters in order...

3 minutes read.

#include in C

In the C programming language, #include is another way of inferring a standard, or a user defines file into the application or program. The preprocessor of the programming standard generally...

4 minutes read.

Free() Function in C

Free() function is a built-in function which is define in the stdlib.h header file. If we want to use this function in our program, we must include the stdlib.h header...

4 minutes read.

10 Best IDEs for C or C++ Developers in 2024

Nobody can deny the fact that C and C++ were the first programming languages used by significant developers worldwide. Even now, newcomers who want to start programming are most frequently...

6 minutes read.

Armstrong program in C using function

In this article we will learn how to find Armstrong of a number using function in C. An Armstrong number is a three-digit number that is the sum of its separate...

1 minute read.

C printf and Scanf

Input-Output functions in C Programming In C Language, the printf() and scanf() are inbuilt library functions that used for input and output. It is defined in the header file“<stdio.h>”. printf() Function: In C...

2 minutes read.

Find Day from Day in C Without using function

Introduction: In the given article, I find daily in C without using functions. It takes 365 days for the earth to revolve around the sun. It will be close to...

3 minutes read.

What is a buffer in C?

A buffer is an area of memory set aside for the temporary storage of data. A data buffer (or just buffer) is a region of a physical memory storage used to...

5 minutes read.