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

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

Advertisements

19 thoughts on “C++ Big Integer

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

  2. 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. 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,

      Just press “Blue button – Download now” : )
      Counter for 20-30 seconds will be occur, Wait till “Download file now” button appears.
      I tried it again, and it is working fine : )

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s