—

**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). **BigInteger**s 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 : )

–

ana knt wa5dha mn sharaf mn fatra 😀 bgad msA (Y)

feeh bardo mas2ala : “485 – Pascal’s Triangle of Death” laziza 😀

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

mmmm tab kways enak 2olt 😀

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.

Tamam (Y)

I’ll take a look for Java ones : )

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 !

3ash ya 3amr.

msA.

men taqaddom ela taqaddom, we men code ela code 😀

tmam ya Mr.Amr : )

Well Done .

nice one .. great job .. go on

Thanx man, Rabbena yekremak : D

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

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

Reblogged this on begin from badcoding and commented:

Big Integer for C++

Syukron Abu Muslim,

I reblogged it

You’re welcome, anytime : )

MSA

3alek

nafsy a2olk 3adak el 3yb bs Downloading Error, b2aly 3 hours badwr 3al division function or algorithm.

Here you go: BigInt

https://app.box.com/s/c4501pdkk5myi3fx65nu