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

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.

pow() function in C

pow() function is one of the in-built functions present in math.h header file Power function is used to calculate the powers of the given number. The syntax of the power...

3 minutes read.

Prototype in C

A prototype is nothing but a model, a model of initial creation of an intended product. Similarly, in the C programming language, all functions have a prototype. In general, all...

4 minutes read.

Array Example in C

An array is a collection of similar types of data elements arranged in such a way that any number of values can be assigned to it. It can store values that...

4 minutes read.

Loop Statement in C

Loop statement is used to execute one or more statement repeatedly multiple times. There are three types of loops in C language. Why use loop? We can use loop because it executes a...

2 minutes read.

While Loop in C programming examples

Introduction There is always a header file containing all the essential data regarding inputs and outputs of various functions in the C programs. The following statement describes how to use/add header file...

22 minutes read.

Results of Comparison Operations in C and C++

In this tutorial, we will explore comparison operators and how the system should compare an incoming value supplied as a context parameter to a given value or range of values. A...

2 minutes read.

Associativity of Operators in C

What is an Associativity operator? Two operators with equal priority are connected by employing their association when they are present in an expression. There are two different types of associativity: left to rightright...

4 minutes read.

Bar3d() function in C Graphics

The bar3d function is used to create a 2-dimensional filled-in rectangular bar. We can also create three-dimensional shapes in C using helpful function. The first step in creating this 3D...

3 minutes read.

Expressions in C

Expressions in C: In the C programming language, an expression defines a formula in which the operands are linked to each other by using operators to compute the value. The operand...

4 minutes read.

Fibonacci series in C

We have learned about the Fibonacci series in mathematics. For a quick recap, A Fibonacci series is the sequence of numbers following a certain pattern i.e., the next number should...

3 minutes read.

Dynamic memory allocation

Dynamic memory allocation is used to allocate the memory at runtime. It has following function within <stdlib.h> header file. Function Syntax malloc() malloc (number *sizeof(int)); calloc() calloc (number, sizeof(int)); realloc() realloc (pointer_name, number * sizeof(int)); free() free (pointer_name); malloc() function The process...

2 minutes read.

File Handling in C

File Handling is used to open, read, write, search and close file.  C files I/O functions handles data on secondary storage device. File handling function: There are varioushandling functions in C. Function Operation fopen() It is...

4 minutes read.

Nested loop in C

Definition of Nested Loop A nested loop is generally used when we want to run a loop statement inside another loop statement. This kind of loop is also known as a...

3 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.

Factorial Program in C Using While Loop

Before looking into the mechanism of factorial program, first, you have to understand about the working of a while loop. While Loop The syntax that has been used for the “while” loop...

4 minutes read.

Big O Notation in C

Big O Notation in C: In the C programming language, we have so many algorithms and solutions to the problems that exist, which have different aspects and purposes to an...

3 minutes read.

Simple Programs in C Language

In this article, we will discuss the basic programs in C language. Addition of two values in C. Swapping two values. Finding the odd or even values. Finding vowels and consonants in C. Finding the...

11 minutes read.

Union in C

Union is a user-defined data type that is used to hold the different types of elements like structure. In union, all members share the same memory location. Syntax: union [union name] { ...

1 minute read.

#define in C

#define in C In the C programming language, the preprocessor directive acts an important role within which the #define directive is present that is used to define the constant or the...

3 minutes read.