A Big Number Calculating Approach http://geek.daohoangson.com/2010/01/cpp-big-number-calculating-approach.html

main.cpp

#define THOUSAND_SEPARATOR ","

#include<iostream> // cin, cout
#include<cmath> // math functions
#include<string> // string functions

using namespace std;

struct digit {
 int value;
 digit* link;
};
typedef digit* digitPtr; //shortcut for digit pointer type

class bigNumber {
 friend istream& operator>> (istream&, bigNumber&);
 friend ostream& operator<< (ostream&, const bigNumber&);
 friend bigNumber operator+ (const bigNumber&, const bigNumber&);
 friend bigNumber operator- (const bigNumber&, const bigNumber&);
 friend bigNumber operator* (const bigNumber&, const bigNumber&);
 friend int cmp (const bigNumber&, const bigNumber&, bool);
 public:
  bigNumber();
  ~bigNumber();
  void cleanup();
  void trim();
  digitPtr getHead() const;
  bool addDigit(int);
  bool addDigit(int,bool);
  int numberOfDigits() const;
  bool getSign() const;
  bool setSign(bool);
  bigNumber& operator= (int);
  bigNumber& operator= (const bigNumber&);
  bigNumber& operator+= (const bigNumber&);
  bigNumber& operator-= (const bigNumber&);
  bigNumber& operator*= (const bigNumber&);
 private:
  digitPtr digit_head;
  bool positive; //true = positive, false = negative
};

//Constructor
bigNumber::bigNumber() {
 this->digit_head = NULL;
 this->positive = true;
}

//Destructor
bigNumber::~bigNumber() {
 this->cleanup();
}

//Cleanup all allocated memory for this bigNumber's digits
void bigNumber::cleanup() {
 digitPtr digit_current, digit_previous;
 
 digit_current = this->digit_head;
 while (digit_current != NULL) {
  digit_previous = digit_current->link;
  delete digit_current;
  digit_current = digit_previous;
 }
 
 this->digit_head = NULL;
 this->positive = true;
}

//Remove zeros at the beginning of the bigNumber if any
void bigNumber::trim() {
 digitPtr digit_current, digit_previous;
 
 digit_previous = NULL;
 digit_current = this->getHead();
 
 while (digit_current->link != NULL) {
  digit_previous = digit_current;
  digit_current = digit_current->link;
 }
 
 if (digit_current->value == 0 && digit_previous != NULL) {
  digit_previous->link = NULL; //remove the tail digit
  delete digit_current;
  
  if (digit_previous->value == 0) this->trim();
 }
}

//Return the head of the linked-list digits
digitPtr bigNumber::getHead() const {
 return this->digit_head;
}

//Add digit to the linked-list
//Support 2 directions
bool bigNumber::addDigit(int digit_value, bool direction) {
 digitPtr digit_new, digit_current;
 
 //Create a digit
 digit_new = new digit;
 digit_new->value = digit_value;
 
 if (direction == true) {
  digit_new->link = this->digit_head; //point new-digit's link back to current head
  
  //Swap current head with the newly created digit
  this->digit_head = digit_new;
 } else {
  digit_new->link = NULL; //point new-digit's link to nothing (as it will be the last digit)
  
  if (this->digit_head == NULL) {
   this->digit_head = digit_new; //no digit yet
  } else {
   digit_current = this->getHead();
   
   //Find the last digit
   while (digit_current->link != NULL) {
    digit_current = digit_current->link;
   }
   
   digit_current->link = digit_new; //the new-digit now become the tail digit
  }
 }
 
 return true;
}

//A wrapper which adds the digit to the head 
bool bigNumber::addDigit(int digit_value) {
 return this->addDigit(digit_value,true);
}

//Count the number of digits
int bigNumber::numberOfDigits() const {
 digitPtr digit_current;
 int count = 0;
 
 digit_current = this->getHead();
 
 while (digit_current->link != NULL) {
  count++;
  digit_current = digit_current->link;
 }
 
 return count;
}

//Return the sign of the bigNumber
bool bigNumber::getSign() const {
 return this->positive;
}

//Assign the sign of the bigNumber
bool bigNumber::setSign(bool positive) {
 this->positive = positive;
 
 return true;
}

//Assigning with an integer's value
bigNumber& bigNumber::operator= (int i) {
 this->cleanup();
 
 this->positive = (i > 0);
 i = abs(i);
 
 while (i > 0) {
  this->addDigit(i % 10,false);
  i /= 10;
 }
 
 return *this;
}

//Assigning with an other bigNumber's value
bigNumber& bigNumber::operator= (const bigNumber& theOtherNumber) {
 digitPtr digit_current;
 
 if (this != &theOtherNumber) {
  this->cleanup();
  
  this->positive = theOtherNumber.positive;
  
  digit_current = theOtherNumber.getHead();
  while (digit_current != NULL) {
   this->addDigit(digit_current->value,false);
   
   digit_current = digit_current->link;
  }
 } 
 
 return *this;
}

//Self-increasing
bigNumber& bigNumber::operator+= (const bigNumber& theOtherNumber) {
 int thisValue, otherValue, currentResult;
 digitPtr thisPtr, otherPtr, tmpPtr;
 
 if (this->getSign() == theOtherNumber.getSign()) {
  //if 2 numbers have the same sign
  //do basic adding
  int remember = 0;
  
  thisPtr = this->getHead();
  otherPtr = theOtherNumber.getHead();
  
  #ifdef DEBUG
  cout << "Calculating: " << *this << " + " << theOtherNumber << endl;
  #endif
  
  while (thisPtr != NULL || otherPtr != NULL) {
   //Get 2 values
   if (thisPtr != NULL) {
    thisValue = thisPtr->value;
   } else {
    thisValue = 0;
   }
   
   if (otherPtr != NULL) {
    otherValue = otherPtr->value;
   } else {
    otherValue = 0;
   }
   
   //Adding
   currentResult = thisValue + otherValue + remember;
   
   #ifdef DEBUG
   cout << thisValue << " + " << otherValue << " (+ " << remember << ")";
   #endif
   
   if (currentResult > 9) {
    remember = currentResult / 10;
    currentResult %= 10;
   } else {
    remember = 0;
   }
   
   #ifdef DEBUG
   cout << " -> " << currentResult << " (remember: " << remember << ")" << endl;
   #endif
   
   //Update our value
   if (thisPtr != NULL) {
    thisPtr->value = currentResult;
    thisPtr = thisPtr->link; //Process to next digit
   } else {
    this->addDigit(currentResult,false);
   }
   
   //Process to next digit
   if (otherPtr != NULL) {
    otherPtr = otherPtr->link;
   } else {
    //do nothing
   }
  }
  
  //Additional check for remembered value
  while (remember > 0) {
   this->addDigit(remember % 10,false);
   remember /= 10;
  }
  //finised with adding 2 same-sign numbers
 } else {
  //different sign numbers
  int borrow = 0;
  bool swapped = false;
  bigNumber subtractNumber;
  
  if (cmp(*this,theOtherNumber,false) == -1) {
   //*this < theOtherNumber
   //swap
   subtractNumber = *this;
   *this = theOtherNumber;
   
   this->setSign(!this->getSign());
   subtractNumber.setSign(!subtractNumber.getSign());
   
   swapped = true;
  } else {
   subtractNumber = theOtherNumber;
  }
  
  thisPtr = this->getHead();
  otherPtr = subtractNumber.getHead();
  
  #ifdef DEBUG
  cout << "Calculating: " << *this << " + " << subtractNumber << endl;
  #endif
  
  while (thisPtr != NULL || otherPtr != NULL) {
   //Get 2 values
   if (thisPtr != NULL) {
    thisValue = thisPtr->value;
   } else {
    thisValue = 0;
   }
   
   if (otherPtr != NULL) {
    otherValue = otherPtr->value;
   } else {
    otherValue = 0;
   }
   otherValue = 10 - otherValue;
   
   //Subtracting
   if (borrow > 0) {
    #ifdef DEBUG
    cout << thisValue;
    #endif
    
    thisValue -= borrow;
    
    #ifdef DEBUG
    cout << " = " << thisValue << " (due to borrowed) ";
    #endif
   }
   
   currentResult = thisValue + otherValue;
   
   #ifdef DEBUG
   cout << thisValue << " + " << otherValue << " = " << currentResult;
   #endif
   
   if (currentResult > 9) {
    currentResult %= 10;
    borrow = 0;
   } else {
    borrow = 1;
   }
   
   #ifdef DEBUG
   cout << " -> " << currentResult << " (borrow: " << borrow << ")" << endl;
   #endif
   
   //Update our value
   if (thisPtr != NULL) {
    thisPtr->value = currentResult;
    thisPtr = thisPtr->link; //Process to next digit
   } else {
    this->addDigit(currentResult,false);
   }
   
   //Process to next digit
   if (otherPtr != NULL) {
    otherPtr = otherPtr->link;
   } else {
    //do nothing
   }
  }
  
  //Assign back the sign if neccessary
  if (swapped) {
   this->setSign(!this->getSign());
  }
  
  //trim number
  this->trim();
 }
 
 return *this;
}

//Self-decreasing
bigNumber& bigNumber::operator-= (const bigNumber& theOtherNumber) {
 bigNumber theOtherNumber_tmp;
 
 theOtherNumber_tmp = theOtherNumber;
 theOtherNumber_tmp.setSign(!theOtherNumber.getSign());
 
 *this += theOtherNumber_tmp;
 
 return *this;
}

//Self-multiplying
bigNumber& bigNumber::operator*= (const bigNumber& theOtherNumber) {
 int count, i;
 digitPtr thisPtr, otherPtr;
 bigNumber tmp1, tmp2;
 
 thisPtr = this->getHead();
 count = 0;
 
 #ifdef DEBUG
 cout << "Calculating: " << *this << " * " << theOtherNumber << endl;
 #endif
 
 while (thisPtr != NULL) { //start looping through our digits
  tmp2.cleanup();
  for (i = 0; i < count; i++) tmp2.addDigit(0,false);
  
  otherPtr = theOtherNumber.getHead();
  
  while (otherPtr != NULL) { //start looping through theOtherNumber digits
   tmp2.addDigit(thisPtr->value * otherPtr->value,false); //add the multiplied value to tmp2
   
   otherPtr = otherPtr->link; //process to next digit
  }
  
  #ifdef DEBUG
  cout << thisPtr->value << " * " << theOtherNumber << " = " << tmp2 << endl;
  #endif
  
  tmp1 += tmp2; //add tmp2 back to tmp1
  count++;
  
  thisPtr = thisPtr->link;
 }
 
 //Assign the sign of the result
 //If 2 numbers have the same sign: result will be positive
 //Otherwise, it will be negative. Obvious!
 tmp1.setSign(this->getSign() == theOtherNumber.getSign()?true:false);
 
 *this = tmp1; //copy tmp1 value
 
 return *this;
}

//Get value from input
istream& operator>> (istream& input, bigNumber& theNumber) {
 char tmp;
 bool foundNumber = false;
 
 theNumber.cleanup();
 
 while (!input.eof()) {
  input.get(tmp);
  
  if (tmp >= '0' && tmp <= '9') {
   foundNumber = true;
   theNumber.addDigit(tmp - '0');
  } else {
   if (foundNumber == false) {
    //not found number yet, continue
    if (tmp == '-') {
     theNumber.setSign(false);
    }
   } else {
    //finished with the number, return
    if (tmp != ' ') input.putback(tmp);
    
    return input;
   }
  }
 }
}

//Output value
ostream& operator<< (ostream& output, const bigNumber& theNumber) {
 digitPtr digit_current;
 char tmp[2];
 string str;
 int digit_count = 0;
 
 digit_current = theNumber.getHead();
 tmp[1] = 0;
 str = "";
 
 while (digit_current != NULL) {
  tmp[0] = char(digit_current->value + '0');
  
  #ifdef THOUSAND_SEPARATOR
  if (digit_count > 0 && digit_count % 3 == 0) {
   str.insert(0,THOUSAND_SEPARATOR);
  }
  #endif
  
  str.insert(0,tmp);
  
  digit_current = digit_current->link;
  digit_count++;
 }
 
 if (str.length() > 0) {
  if (theNumber.getSign()) {
   //do not display "+" for positive numbers, yet
  } else {
   output << "-";
  }
  output << str;
 } else {
  output << 0;
 }
 
 return output;
}

//Adding 2 bigNumbers, call the += function
bigNumber operator+ (const bigNumber& x, const bigNumber& y) {
 bigNumber result;
 
 result = x;
 result += y;
 
 return result;
}

//Subtrect y from x, call the -= function
bigNumber operator- (const bigNumber& x, const bigNumber& y) {
 bigNumber result;
 
 result = x;
 result -= y;
 
 return result;
}

//Multiply 2 bigNumber, call the *= function
bigNumber operator* (const bigNumber& x, const bigNumber& y) {
 bigNumber result;
 
 result = x;
 result *= y;
 
 return result;
}

//Main comparison function
int cmp (const bigNumber& x, const bigNumber& y, bool checkSign) {
 digitPtr x_ptr, y_ptr;
 bool x_sign, y_sign;
 int x_count, y_count, tmp_count, i;
 int result;
 
 x_ptr = x.getHead();
 y_ptr = y.getHead();
 result = 1;

 if (checkSign) {
  x_sign = x.getSign();
  y_sign = y.getSign();
  
  if (x_sign == y_sign) {
   if (x_sign == true) {
    result = 1;
   } else {
    result = -1;
   }
  } else {
   if (x_sign == true) {
    return 1;
   } else {
    return -1;
   }
  }
 }
 
 x_count = x.numberOfDigits();
 y_count = y.numberOfDigits();
 
 #ifdef DEBUG
 cout << "Comparing: " << x << " & " << y << " with checkSign = " << (checkSign?"true":"false") << endl;
 cout << "Number of Digits: " << x_count << " & " << y_count << endl;
 #endif
 
 if (x_count > y_count) {
  return 1 * result; //x > y
 } else if (x_count < y_count) {
  return -1 * result; //x < y
 } else {
  tmp_count = x_count;
  do {
   i = 0;
   x_ptr = x.getHead();
   y_ptr = y.getHead();
   
   while (i < tmp_count) {
    x_ptr = x_ptr->link;
    y_ptr = y_ptr->link;
    i++;
   }
   
   #ifdef DEBUG
   cout << "Comparing " << x_ptr->value << " & " << y_ptr->value << endl;
   #endif
   
   if (x_ptr->value > y_ptr->value) {
    return 1 * result; //x > y
   } else if (x_ptr->value < y_ptr->value) {
    return -1 * result; //x < y
   }
   
   tmp_count--;
  } while (tmp_count >= 0);
 }
 
 return 0; //x == y
}

//Default comparison function (with checkSign)
int cmp (const bigNumber& x, const bigNumber& y) {
 return cmp(x,y,true);
}

//Greater-than comparison
bool operator> (const bigNumber& x, const bigNumber& y) {
 return (cmp(x,y) == 1?true:false);
}

//Less-than comparison
bool operator< (const bigNumber& x, const bigNumber& y) {
 return (cmp(x,y) == -1?true:false);
}