Technical

# C++ Big Integer

Overview:

As I looked more than once for a BigInteger class in C++ like this one in included in Java and didn’t find a well made one, I decided to implement my own class.

As it clear from its name, the goal of BigInteger class is to perform all arithmetic operations with “Big” integers; big integers that can’t be stored in primitive data types (int, long, double, …).  BigIntegers are stored as strings, operations performed on these strings. It is good to know that 32 bit unsigned integer can store numbers from 0 to 4294967295 (10-digits number), While “signed int” stores values from -2147483648 to +2147483647 (10-digit number). BigIntegers enable us to store and perform operations on very big values like 10^10000 (10000-digits numbers).

Some functions increase very fast like Fibonacci and Factorial, You can see how your scientific CASIO calculator prints “Sorry” for 70!   : D.

Here’s simple illustration of the main idea:

Implementation:

Supported arithmetic operations are (+, -, *, / and %) and 15 other additional operator to make the class very usable (=, ==, !=, >, >=, <, <=, ++, –, +=, -=, *=, /=, %= and unary minus).

Here’s the “BigInteger.h”:

```</pre>
//-------------------------------------------------------------
// Class: BigInteger
// Author: Amr Mohammed
// Last update: 26-12-2012
//-------------------------------------------------------------

#ifndef BIGINTEGER_H
#define BIGINTEGER_H
#include "StdAfx.h"
#include <string>
#define MAX 10000 // for strings

using namespace std;
//-------------------------------------------------------------

const int BASE = 10;

class BigInteger
{
private:
public:
string number;
bool sign;

BigInteger(); // empty constructor initializes zero
BigInteger(string & s); // "string" constructor
BigInteger(string & s, bool & sin); // "string" constructor
BigInteger(int n); // "int" constructor
void setNumber(string & s);
string& getNumber(); // retrieves the number
void setSign(bool s);
bool& getSign();
BigInteger absolute(); // returns the absolute value
string toString();
void operator = (BigInteger b);
bool operator == (BigInteger & b);
bool operator != (BigInteger & b);
bool operator > (BigInteger & b);
bool operator < (BigInteger & b);
bool operator >= (BigInteger & b);
bool operator <= (BigInteger & b);
BigInteger& operator ++(); // prefix
BigInteger operator ++(int); // postfix
BigInteger& operator --(); // prefix
BigInteger operator --(int); // postfix
BigInteger operator + (BigInteger & b);
BigInteger operator - (BigInteger & b);
BigInteger operator * (BigInteger & b);
BigInteger operator / (BigInteger & b);
BigInteger operator % (BigInteger & b);
BigInteger& operator += (BigInteger & b);
BigInteger& operator -= (BigInteger & b);
BigInteger& operator *= (BigInteger & b);
BigInteger& operator /= (BigInteger & b);
BigInteger& operator %= (BigInteger & b);
BigInteger& operator [] (int n);
BigInteger operator -(); // unary minus sign
operator string(); // for conversion from BigInteger to string
private:
bool equals(BigInteger & n1, BigInteger & n2);
bool less(BigInteger & n1, BigInteger & n2);
bool greater(BigInteger & n1, BigInteger & n2);
string subtract(string number1, string number2);
string multiply(string n1, string n2);
pair<string, long long> divide(string n, long long den);
string toString(long long n);
long long toInt(string s);
BigInteger range (int a, int b);
double double_div (const BigInteger &o);
pair <BigInteger, BigInteger> divmod (BigInteger &o);
BigInteger operator << (int p);
void trim ();
int toInt();
};

#endif
<pre>
```

To test the class and train yourself to use it, I collected some UVa problems that requires BigInt, Here’s a list of some problems:

Complexity:

• Adding and Subtracting: O( max( len(operand1) , len(operand2) ) )
• Multiplication: O( len(operand1) * len(operand2) )
• Division and Modulus: O( len(numerator) * max(len(numerator), len(den) ) )

I have to say that we pay both time and memory when BigIntegers must be used. Challenges of various implementations work on saving both memory and time.

Any technical feedback, issues or more suggestions for improvements are totally welcomed : )

## 19 thoughts on “C++ Big Integer”

1. Hesham Abd El-Hay says:

ana knt wa5dha mn sharaf mn fatra 😀 bgad msA (Y)
feeh bardo mas2ala : “485 – Pascal’s Triangle of Death” laziza 😀

1. tamam tamam, bas elly ana kont meddeha le Sharaf kanet unsigned, we de zawwedt 3aleha operators we keda : )

1. Hesham Abd El-Hay says:

mmmm tab kways enak 2olt 😀

2. amr mahdi says:

Cool JAK 😉

Concerning multiplication & division as you mentioned its is costly and I’ve read once that there are more efficient techniques for doing that operations with lower order. You can check them for improvements and I also think that those are the ones used in JAVA.

3. Oh, I have forgot to make [] operator,

Here it is:

BigInteger& operator [] (int n)
{
return *(this + (n*sizeof(BigInteger)));
}

Btw, cpp and header files updated !

4. Mohammed Sharaf says:

3ash ya 3amr.
msA.

5. Yahya says:

tmam ya Mr.Amr : )
Well Done .

6. hi,
When I click on the link to view to BigInteger.cpp file, it takes me to a webpage which is asking to pay to view the file. How do I view the file for free or I must pay to view?

Thanks

1. SA,