Big Integer Arithmetic

A refinement of http://fuliang.iteye.com/blog/368928 .

 

#include <string>
#include <iostream>
using namespace std;

/*
 * This implementation uses string to represent big integer. Arithmetic is 
 * performed on every digit. This is not a efficient way. Hacker's Delight 
 * provides a more efficient way. If I am not wrong, Java BigInteger performs 
 * arithmetic in that way.
 */

// ascii code for '0'
const int ZERO = 48;

inline int compare(string str1, string str2) {
  int result = str1.size() - str2.size();
  if (result != 0) 
    return result;
  else
    return str1.compare(str2);
}

inline int int_val(const char& ch) {
  return ch - ZERO;
}

inline void swap_str(string& str1, string& str2) {
  string temp = str1;
  str1 = str2;
  str2 = temp;
}

inline char ch_val(int integer) {
  return char(integer + ZERO);
}

inline bool negative(string str) {
  return str[0] == '-';
}

inline bool same_sign(string str1, string str2) {
  return str1[0] == '-' && str2[0] == '-' 
    || str1[0] != '-' && str2[0] != '-';
}

inline void format(int sign, string& integer) {
  integer.erase(0, integer.find_first_not_of('0'));  
  if(integer.empty()) integer = "0";  
  if((sign == -1) && (integer[0] != '0'))  
    integer = "-" + integer;  
}

string add_int(string, string);
string subtraction_int(string, string);
string add_natural(string, string);
string subtraction_natural(string, string);

/**
 * add_int - add two integers.
 */
string add_int(string lterm, string rterm) {
  int sign = 1;
  string sum;

  if (same_sign(lterm, rterm)) {
    if (negative(lterm)) {
      sign = -1;
      lterm.erase(0, 1);
      rterm.erase(0, 1);
    }
    sum = add_natural(lterm, rterm);
  } else {
    if (negative(lterm))
      swap_str(lterm, rterm);
    rterm.erase(0, 1);

    int res = compare(lterm, rterm);
    if (res == 0)
      return "0";
    else if (res < 0) {
      sign = -1;
      swap_str(lterm, rterm);
    }
    sum = subtraction_natural(lterm, rterm);
  }

  format(sign, sum); 
  return sum;  
}

/**
 * subtraction_int - subtract rterm from lterm.
 */
string subtraction_int(string lterm, string rterm) {
  if (negative(rterm))
    rterm.erase(0, 1);
  else 
    rterm = "-" + rterm;
  return add_int(lterm, rterm);
}

/**
 * subtraction_natural - subtract rterm natural number from lterm natural number.
 * 
 * rterm should be less than lterm.
 */
string subtraction_natural(string lterm, string rterm) {
  string difference;
  string::size_type offset = lterm.size() - rterm.size();

  for (int i = rterm.size() - 1; i >= 0; i--) {
    if (lterm[i + offset] < rterm[i]) {
      difference = ch_val(lterm[i + offset] - rterm[i] + 10) + difference;
      int j = i + offset - 1;
      while (lterm[j] == ZERO) {
        lterm[j--] = 9 + ZERO;
      }
      lterm[j] = char(int(lterm[j]) - 1);
    } else {
      difference = ch_val(lterm[i + offset] - rterm[i]) + difference;
    }
  }
  for (int i = offset - 1; i >= 0; i--)
    difference = lterm[i] + difference;

  return difference; 
}

/**
 * add_natural - add the two natural number.
 */
string add_natural(string lterm, string rterm) {
  int i;
  string sum;
  string::size_type ll, lr;
  ll = lterm.size();
  lr = rterm.size();
  if (ll < lr) {
    for (i = 1; i <= lr - ll; i++)
      lterm = "0" + lterm;
  } else {
    for (i = 1; i <= ll - lr; i++)
      rterm = "0" + rterm;
  }
  int digit = 0, carry = 0, temp;
  for (i = lterm.size() - 1; i >= 0; i--) {
    temp = int_val(lterm[i]) + int_val(rterm[i]) + carry;
    digit = temp % 10;
    carry = temp / 10;
    sum = ch_val(digit) + sum;
  }
  if (carry != 0)
    sum = ch_val(carry) + sum;
  return sum;
}

/**
 * multiply_int - multiply two integers.
 */
string multiply_int(string lfactor, string rfactor) {
  // handle sign
  int sign = 1;
  if (lfactor[0] == '-') {
    sign *= -1;
    lfactor = lfactor.erase(0, 1);
  }
  if (rfactor[0] == '-') {
    sign *= -1;
    rfactor = rfactor.erase(0, 1);
  }

  string product;
  int i, j;
  string::size_type l1, l2;
  l1 = lfactor.size();
  l2 = rfactor.size();

  for (i = l2 - 1; i >= 0; i--) {
    string temp;
    int digit = 0, carry = 0, product1, rdigit = int_val(rfactor[i]);
    if (rdigit != 0) {
      for (j = 1; j <= (int)(l2 - 1 - i); j++)
        temp = temp + "0";
      for (j = l1 - 1; j >= 0; j--) {
        product1 = rdigit * int_val(lfactor[j]) + carry; 
        digit = product1 % 10;
        carry = product1 / 10;
        temp = ch_val(digit) + temp;
      }
      if (carry != 0)
        temp = ch_val(carry) + temp;
      product = add_int(product, temp);
    }
  }

  format(sign, product);
  return product;
}

/**
 * divide_int - divide divident wiwht divisor.
 * @flag: 1 to return quotient, 0 to return residue.
 */
string divide_int(string divident, string divisor, int flag) {
  string quotient, residue;
  int sign1 = 1, sign2 = 1;

  // divided by zero
  if (divisor == "0") {
    quotient = "ERROR";
    residue = "ERROR";
    if (flag == 1)
      return quotient;
    else 
      return residue;
  }

  // divide zero
  if (divident == "0") {
    quotient = "0";
    residue = "0";
  }

  if (divident[0] == '-') {
    divident.erase(0, 1);
    sign1 = -1;
    sign2 = -1;
  }
  if (divisor[0] == '-') {
    divisor.erase(0, 1);
    sign1 *= -1;
  }

  int res = compare(divident, divisor);
  if (res < 0) {
    quotient = "0";
    residue = divident;
  } else if (res == 0) {
    quotient = "1";
    residue = "0";
  } else {
    string::size_type l1 = divident.size();
    string::size_type l2 = divisor.size();
    string temp;
    string product;
    temp.append(divident, 0, l2 - 1);
    for (int i = l2 - 1; i < l1; i++) {
      temp = temp + divident[i];
      // try quotient
      for (char ch = '9'; ch >= '0'; ch--) {
        string str;
        str = str + ch;
        product = multiply_int(divisor, str);
        if (compare(product, temp) <= 0) {
          quotient = quotient + ch;
          temp = subtraction_int(temp, product);
          break;
        }
      }
    }
    residue = temp;
  }

  format(sign1, quotient);
  format(sign2, residue);
  return flag ? quotient : residue;
}

string divide_int(string divident, string divisor) {
  return divide_int(divident, divisor, 1);
}

int main(int argc, const char *argv[]) {
  char ch;
  string lterm, rterm, res;
  int shift;
  
  while (cin >> ch) {
    cin >> lterm >> rterm;
    switch (ch) {
      case '+': 
        res = add_int(lterm, rterm);
        break;
      case '-':
        res = subtraction_int(lterm, rterm);
        break;
      case '*':
        res = multiply_int(lterm, rterm);
        break;
      case '/':
        res = divide_int(lterm, rterm);
        break;
      default:
        break;
    }
    cout << res << endl;
  }

  return 0;
}

评论

1 楼 fuliang 2010-09-17  

more cleanner than before