Big Integer Implementation

[funprogrammer]

I was trying to implement Big Integer Implementation. I wanted to start with the basic operation of addition. I am having some problems with operator overloading part, can someone help me out?

/**
BigInteger implementation
*/

#include "conio.h"
#include "iostream"
#include "vector"
using namespace std;

const int CAPACITY = 200;

class BigInt{
   int digits[CAPACITY];
public:
   BigInt();
   BigInt(char num[]);
   BigInt(int init_num);
   BigInt operator+=(BigInt a);
};

BigInt::BigInt(){
   for(int i=0; i< CAPACITY; i++){
      digits[i]=0;
   }
}

BigInt::BigInt(int init_num){
   int i =0;
   while(init_num > 0){
      digits[i] = init_num % 10;
      init_num = init_num/10;
   }
   for(;i< CAPACITY;i++){
      digits[i]=0;
   }
}

BigInt::BigInt(char num[]){
   int i = 0;

   for(int i=0; i< CAPACITY; i++){
      digits[i]=0;
   }

   i =0;

   while(num[i]!= '\0'){
      ++i;
   }

   --i;

   while(i>=0){
      digits[i]= num[i] - '0';
	  i--;
   }
}

BigInt BigInt::operator +=(BigInt a){
   BigInt temp;
   int num = 0;
   int carry = 0;
   for(int i = 0; i < CAPACITY; i++)
   {
       num = digits[i] + a.digits[i] + carry;

	   if(num >= 10)
       {
           num = num - 10;
           carry = 1;
	   }

       temp.digits[i] = num;
   }
    
   return temp;
}

int main(){
   BigInt B1(98765432);
   BigInt B2(98765421);
   BigInt B3;
   B3 = B1+B2;
   cout << "B1+B2 is" << B3 << endl;
   return 0;
}

[cire]

You've overloaded operator+=, but you're trying to use operator+.

Fortunately, operator+ can be implemented in terms of operator+=.

Unfortunately, operator+= is not implemented correctly. It should modify the object it is invoked on, and it should return a reference to that same object.

You also haven't overloaded the insertion operator, so line 84 won't work.

[Edit: If I were you, I'd start with the insertion operator so you can 'cout' a BigInt, then just create one such as you have on line 80 and 81 and make sure that's working correctly before I worked on anything else.]

[Duthomhas]

It's tough when you're new to the language...

Besides what cire said, you also need a copy constructor.

class BigInt{
   unsigned int digits[CAPACITY];      //<--fixed (use unsigned!)
public:
   BigInt();
   BigInt(char num[]);
   BigInt(int init_num);
   BigInt(const BigInt& a);             //<--added copy constructor
   BigInt& operator+=(const BigInt& a); //<--fixed
   BigInt operator+(const BigInt& a);   //<--added

   friend std::ostream& operator<<(std::ostream& outs, const BigInt& a); //<--added stream insertion operator
};

You missed something when converting the number:

BigInt::BigInt(int init_num){
   int i =0;
   while(init_num > 0){
      digits[i++] = init_num % 10;  //<--fixed
      init_num = init_num/10;
   }
   for(;i< CAPACITY;i++){
      digits[i]=0;
   }
}

In your addition algorithm, get rid of the temp variable. The += operator should be modifying *this. Also, make sure to return *this.

Finally, pay attention to what happens to carry when there isn't a carry.

When you write your stream insertion operator (the friend function), make sure to print something even if your number is zero.


Personally, since your bignum digits are only holding values in 0..9, I would not use ints but unsigned char digits[CAPACITY];


Good luck!

[funprogrammer]

Thanks a lot for your replies cire and duoas. I took your suggestions and looked at other code piece and came up with a working program :)
I have to optimize it though, here is the modified working program.

/**
BigInteger implementation
*/
#include "conio.h"
#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;

class BigInt{
   vector<int> digits;
public:
   BigInt(string num="0");
   BigInt operator+(BigInt a);
   friend std::ostream& operator<<(std::ostream& out,BigInt a);
};

struct Ascii2Int { int operator()(int c) {return c-'0';} };

BigInt::BigInt(string num){
   transform(num.rbegin(), num.rend(), back_inserter(digits),Ascii2Int());
}
BigInt BigInt::operator +(BigInt a){
   //BigInt temp;
   int num = 0;
   int carry = 0;
   for(unsigned int i = 0; i < a.digits.size(); i++)
   {
       num = digits[i] + a.digits[i] + carry;

	   if(num >= 10)
       {
           num = num - 10;
           carry = 1;
	   }
	   else{
		   carry = 0;
	   }
       this->digits[i] = num;
   }
   if (carry){
	   this->digits.push_back(1);
   }
   return *this;
}

std::ostream& operator <<(std::ostream& out,BigInt a)
{
   for(unsigned int i=0; i < a.digits.size(); i++){
      out << a.digits[i] << endl;
   }
   return out;
}

int main(){
   BigInt B1("981654321");
   BigInt B2("987654321");
   BigInt B3;
   B3 = B1+B2;
   cout << "B1+B2 is" << B3 << endl;
   return 0;
}

[cire]

If I change your stream insertion operator and main to:

#include <sstream>
#include <iomanip>

// ...

std::ostream& operator <<(std::ostream& out, BigInt a)
{
    std::ostringstream os;

    for (unsigned i = a.digits.size(); i > 0; --i)
        os << a.digits[i-1];

    return out << os.str() ;
}

int main(){
    BigInt B1("981654321");
    BigInt B2("987654321");
    BigInt B3;

    std::cout << "Before addition:\n";
    std::cout << "B1: " << std::setw(11) << B1 << '\n';
    std::cout << "B2: " << std::setw(11) << B2 << '\n';
    std::cout << "B3: " << std::setw(11) << B3 << '\n';

    B3 = B1 + B2;

    std::cout << "After addition:\n";
    std::cout << "B1: " << std::setw(11) << B1 << '\n';
    std::cout << "B2: " << std::setw(11) << B2 << '\n';
    std::cout << "B3: " << std::setw(11) << B3 << std::endl;

    return 0;
}

I get:

Before addition:
B1:   981654321
B2:   987654321
B3:           0
After addition:
B1:  1969308642
B2:   987654321
B3:  1969308642

Does that look right to you? Should B1 be different after the addition?

[Duthomhas]

Remember,

operator +=
  modifies and returns *this

operator +
  creates a new BigInt and returns it, without modifying *this

If you make a copy constructor like I asked you to, you can define + in terms of +=

BigInt& operator +=(const BigInt& a)
{
    //add a to *this here.
    return *this;
}

BigInt operator +(const BigInt& a) const
{
    return BigInt(*this) += a;
}

You also need to be careful now about the size of your operands. Before they were always 200 digits, so you couldn't have any troubles. Now, what if you add a really big number to a smaller one:

    BigInt B1("12");
    BigInt B2("987654321");
    BigInt B3;

    B3 = B1 + B2;  // B1 isn't big enough to handle adding all B2's digits 

By the way, you should make a policy now on how you will handle and store zero. Right now zero is {0}, where (digits.size() == 1). Otherwise your number should take care to not have any extraneous leading zeros in the digits. (Once you get into doing multiplications the number of leading zeros can grow quickly.)

Good luck!

[funprogrammer]

Hi Cerie & Duoas,
I took your suggestions and modified my program quite a bit. I was having some difficult understanding copy constructors and assignment operators. I think I kind of understood the need for it, but still not convinced on when & how to use them. I think this will improve with more coding experience. I am attaching my latest modified piece of code, I still have some trivial questions which will follow the code. Please help me out, it will improve my understanding.

#include "conio.h"
#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;

class BigInt{
   vector<int> digits;
public:
   BigInt(const BigInt& a);
   BigInt(string num="000000000");
   BigInt operator+(const BigInt& a);
   BigInt& operator+=(const BigInt& a);
   BigInt operator=(BigInt a);
   friend std::ostream& operator<<(std::ostream& out,BigInt a);
};

struct Ascii2Int { int operator()(int c) {return c-'0';} };

BigInt::BigInt(const BigInt& other):digits(other.digits){}

BigInt BigInt::operator=(BigInt a){
   for(unsigned int i=0; i<digits.size();i++){
     digits[i] = a.digits[i];	
   } 
   return *this;
}

BigInt::BigInt(string num){
   transform(num.rbegin(), num.rend(), back_inserter(digits),Ascii2Int());
}
BigInt& BigInt::operator +=(const BigInt& a)
{
   unsigned int maxSize;
   unsigned int num = 0;
   unsigned int carry = 0;
   BigInt Temp; 
 
   //size for output variable

   if(digits.size()>a.digits.size()){
	   maxSize = digits.size();
	   Temp.digits.resize(digits.size());
   }
   else{
	   maxSize = a.digits.size();
	   digits.resize(a.digits.size());
   }

   copy(a.digits.begin(), a.digits.end(), Temp.digits.begin());

   for(unsigned int i = 0; i < maxSize; i++)
   {
       num = digits[i] + Temp.digits[i] + carry;

	   if(num >= 10)
       {
           num = num - 10;
           carry = 1;
	   }
	   else{
		   carry = 0;
	   }

	   digits[i] = num;
   }
   if (carry){
	   digits.push_back(1);
   }
   
   return *this;
}

BigInt BigInt::operator +(const BigInt& a)
{
    return BigInt(*this) += a;

}

std::ostream& operator <<(std::ostream& out,BigInt a)
{
   for(unsigned int i=0; i < a.digits.size(); i++){
      out << a.digits[i] << endl;
   }
   return out;
}

int main(){
   BigInt B1("981654321");
   BigInt B2("98431");
   BigInt B3;
   B3 = B1+B2;
   cout << "B1+B2 is" << B3 << endl;
   BigInt B4;
   B4+=B1;
   B4+=B2;
   B4+=B3;
   cout << "B4 is"<< B4 << endl;
   return 0;
}

Questions:
1) How can I optimize my code in line 11. The constructor is currently passing number of zeros equal to output size
2) I have used default copy constructor(the one used by compiler), is user defined type usually different?

[Duthomhas]

I'm not at my PC ATM so I can't say much more than what a quick glance will do, but you are looking much better.

Line 11 shouldn't need more than one zero -- such inputs should not be permitted to modify the internal representation of your bignum. (Remember what I said about a policy on leading zeros?)

Line 12 should have the keyword "const" just before the semicolon.

I notice that you are messing with a 'temp' bignum again in your += operator function. You really don't need it. All you have to do is make sure that this->digits.size() is not less than a.digits.size(). Then add with carry as long as there are digits in a. Then carry into the remaining digits of *this.

Re copy ctor: yes, it will be different if necessary. In this case, the default does everything correctly.

Maybe cire will catch something I missed.

[cire]

Looking much better. There is no reason to explicitly define operator= (the defaulted version will be correct,) but if you choose to do so, the function should return a reference to BigInt in order to correctly simulate the semantics of built-in arithmetic types.

Since your operator= takes a copy of a BigInt, the following would be an efficient definition (assuming you don't just let the compiler do the work.)

BigInt& operator=(BigInt num)
{
    digits.swap(num.digits) ;
    return *this ;
}

[funprogrammer]

Thanks a lot guys. I was able to modify it further and include the above suggestions. The code looks more stable and neat now. Here is the updated code.

#include "conio.h"
#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;

class BigInt{
   vector<int> digits;
public:
   BigInt(const BigInt& a);
   BigInt(string num="0");
   BigInt operator+(const BigInt& a) const;
   BigInt& operator+=(const BigInt& a);
   BigInt& operator=(BigInt a);
   friend std::ostream& operator<<(std::ostream& out,BigInt a);
};

struct Ascii2Int { int operator()(int c) {return c-'0';} };

BigInt::BigInt(const BigInt& other):digits(other.digits){}

BigInt& BigInt::operator=(BigInt a){
	digits.swap(a.digits);
    return *this;
}

BigInt::BigInt(string num){
   transform(num.rbegin(), num.rend(), back_inserter(digits),Ascii2Int());
}
BigInt& BigInt::operator +=(const BigInt& a)
{
   unsigned int maxSize;
   unsigned int num = 0;
   unsigned int carry = 0;
 
   //size for output variable
   if(digits.size()<a.digits.size()){
	   maxSize = a.digits.size();
	   digits.resize(a.digits.size());
   }
   else{
	   maxSize = digits.size();
   }

   for(unsigned int i = 0; i < maxSize; i++)
   {
	   if(i<a.digits.size())
          num=digits[i]+a.digits[i]+carry;
	   else 
          num=digits[i]+carry;

      if(num >= 10)
      {
          num = num - 10;
          carry = 1;
      }
      else{
         carry = 0;
      }
      
	  digits[i] = num;
   }
   if (carry){
	   digits.push_back(1);
   }
   
   return *this;
}

BigInt BigInt::operator +(const BigInt& a) const
{
    return BigInt(*this) += a;

}

std::ostream& operator <<(std::ostream& out,BigInt a)
{
   for(unsigned int i=0; i < a.digits.size(); i++){
      out << a.digits[i] << endl;
   }
   return out;
}

int main(){
   BigInt B1("981654321");
   BigInt B2("98431");
   BigInt B3;
   B3 = B1+B2;
   cout << "B1+B2 is" << B3 << endl;
   BigInt B4;
   B4+=B1;
   B4+=B2;
   B4+=B3;
   cout << "B4 is"<< B4 << endl;
   return 0;
}

My next step is to try Karatsuba algorithm and other operations. I should be able to do that from here. Thanks a lot for your help