分治法大整数乘法——大整数类实现版

#include "BigNumber.h" #include <iostream.h> #include <algorithm> BigNumber::BigNumber(int max) { nMaxLen = max; pNum = new char[max]; nLength = 0; } BigNumber::BigNumber(const BigNumber& bn) { nMaxLen = bn.nMaxLen; pNum = new char[nMaxLen]; nLength = bn.nLength; int i = 0; while(i < nLength) { pNum[i] = bn.pNum[i]; ++i; } } BigNumber BigNumber::operator= (const BigNumber& bn) { if(nMaxLen != bn.nMaxLen) { delete []pNum; nMaxLen = bn.nMaxLen; pNum = new char[nMaxLen]; } nLength = bn.nLength; int i = 0; while(i < nLength) { pNum[i] = bn.pNum[i]; ++i; } return *this; } BigNumber BigNumber::operator<<(int n) { BigNumber bn(nMaxLen); int i = 0; while(i < n) { bn.pNum[i] = '0'; ++i; } int j = 0; while(j < nLength) { bn.pNum[i] = pNum[j]; ++j; ++i; } bn.nLength = nLength + n; return bn; } BigNumber BigNumber::operator>>(int n) { BigNumber bn(nMaxLen); if(n > nLength) { bn.nLength = 1; bn.pNum[0] = '0'; } else { bn.nLength = nLength - n; int i,j; i = n,j = 0; while(i < nLength) { bn.pNum[j] = pNum[i]; ++i; ++j; } } return bn; } char BigNumber::operator[](int n) const { if(n >= nLength) return '0'; else return pNum[n]; } BigNumber BigNumber::operator+(const BigNumber& bn) { BigNumber res(nMaxLen); int len = bn.nLength > nLength ? bn.nLength : nLength; int i,tmp,carry; carry = 0; for(i = 0;i < len;++i) { tmp = int((*this)[i] - '0' + bn[i] - '0') + carry; if(tmp >= 10) { tmp %= 10; carry = 1; } else carry = 0; res.pNum[res.nLength++] = char(tmp + '0'); } if(carry == 1) res.pNum[res.nLength++] = '1'; return res; } BigNumber BigNumber::operator-(const BigNumber& bn) { BigNumber res(bn.nMaxLen); int len = (nLength > bn.nLength ? nLength : bn.nLength); int i,tmp,carry; carry = 0; for(i = 0;i < len;++i) { tmp = int((*this)[i] - bn[i] - carry); if(tmp < 0) { tmp += 10; carry = 1; } else carry = 0; res.pNum[res.nLength++] = char(tmp + '0'); } if(res.IsZero()) res.nLength = 1; else res.RemoveZero(); return res; } BigNumber BigNumber::operator*(BigNumber bn) { BigNumber res(2*nMaxLen); int len = (nLength > bn.nLength ? nLength : bn.nLength); int rlen = 1; while(rlen < len) rlen <<= 1; len = rlen; if(len == 1) { if(IsZero()|| bn.IsZero()) { res.pNum[0] = '0'; res.nLength = 1; } else { int tmp = (pNum[0] - '0')*(bn[0] - '0'); int low = tmp % 10; int high = tmp / 10; if(high != 0) { res.pNum[0] = char(low + '0'); res.pNum[1] = char(high + '0'); res.nLength = 2; } else { res.pNum[0] = char(low + '0'); res.nLength = 1; } } } else { BigNumber a1 = (*this)>>(len>>1); BigNumber b1 = (*this) - (a1<<(len>>1)); BigNumber a2 = bn>>(len>>1); BigNumber b2 = bn - (a2<<(len>>1)); BigNumber a1a2 = a1 * a2; BigNumber b1b2 = b1 * b2; BigNumber abcd = (a1 + b1)*(a2 + b2) - a1a2 - b1b2; // res = a1a2<<len + ((a1 + b1)*(a2 + b2) - a1a2 - b1b2)<<(len>>1) + b1b2; res = (a1a2<<len) + (((a1 + b1)*(a2 + b2) - a1a2 - b1b2)<<(len>>1)) + b1b2; } return res; } bool BigNumber::IsZero() { int i = 0; while(i < nLength) { if(pNum[i] != '0') return false; ++i; } return true; } void BigNumber::RemoveZero() { while(pNum[nLength - 1] == '0') --nLength; } ostream& operator<< (ostream& out,BigNumber& bn) { if(bn.IsZero()) { bn.pNum[0] = '0'; bn.nLength = 1; } else bn.RemoveZero(); bn.pNum[bn.nLength] = '\0'; std::reverse(bn.pNum,bn.pNum + bn.nLength); out << bn.pNum; std::reverse(bn.pNum,bn.pNum + bn.nLength); return out; } istream& operator>> (istream& in,BigNumber& bn) { in >> bn.pNum; bn.nLength = strlen(bn.pNum); std::reverse(bn.pNum,bn.pNum + bn.nLength); return in; }