—

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 add(string number1, string number2);
 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>

Download the source files from HERE.

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:

• Fibonacci Freeze
• 500!

–

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 : )

–