Header and implementation file for multidigit arithmetic. ---- Numbers.h ---- #ifndef __MYNUMBERS__ #define __MYNUMBERS__ #ifndef __FSTREAM_H #include #endif #define kMAXDIGITS 100 class Number { public: Number(); Number(long); Number(const Number& other); Number(char numstr[]); Number(istream&); void ReadFrom(ifstream& in); void WriteTo(ofstream& out) const; void PrintOn(ostream& printer) const; Number Add(const Number& other) const; Number Subtract(const Number& other) const; Number Multiply(const Number& other) const; Number Divide(const Number& other) const; int Zero_p() const; void MakeZero(); void Randomize(); int Equal(const Number& other) const; void ChangeSign(); int Compare(const Number& other) const; private: int SameSign(const Number& other) const; void DoAdd(const Number& other); Number DoSubtract(const Number& other, int subop) const; void SubtractSub(const Number& other); void Product(int k); void Quotient(int k); void Times10(int power); int LargerThan(const Number& other) const; void LongDiv(const Number& other); int Trial(const Number& other,int,int); int Smaller(const Number& other,int,int); void Difference(const Number& other,int,int); void CopyTo(Number& dest) const; unsigned char fDigits[kMAXDIGITS+1]; unsigned char fPosNeg; short fLength; }; inline int Number::Zero_p() const { return (fLength == 0); } inline int Number::SameSign(const Number& other) const { return (this->fPosNeg == other.fPosNeg); } inline void Number::ChangeSign() { if(fPosNeg) fPosNeg = 0; else fPosNeg = 1; } #endif ---- #include #include #include #include #include #include "Numbers.h" void Overflow() { cout << "Overflow\n"; exit(1); } Number::Number() { fPosNeg = 0; for(int i=0; i<=kMAXDIGITS;i++) fDigits[i] = 0; fLength = 0; } Number::Number(long lval) { fPosNeg = 0; if(lval<0) { fPosNeg = 1; lval = -lval; } for(int i=0; i<=kMAXDIGITS;i++) fDigits[i] = 0; fLength = 0; while(lval) { fDigits[fLength++] = lval % 10; lval = lval / 10; } } Number::Number(const Number& other) { fPosNeg = other.fPosNeg; fLength = other.fLength; for(int i=0; i<=kMAXDIGITS;i++) fDigits[i] = other.fDigits[i]; } Number::Number(char numstr[]) { for(int i=0;i<=kMAXDIGITS;i++) fDigits[i] = 0; fPosNeg = 0; /* Positive */ i = 0; fLength = strlen(numstr); if(numstr[i] =='+') { i++; fLength--; } else if(numstr[i] =='-') { fPosNeg = 1; i++; fLength--; } int pos = fLength - 1; while(numstr[i] != '\0') { if(!isdigit(numstr[i])) { cout << "Bad data in number input\n"; exit(1); } fDigits[pos] = numstr[i] - '0'; i++; pos--; } while((fLength>0) && (fDigits[fLength-1] == 0)) fLength--; } void Number::WriteTo(ofstream& out) const { out.write(&fDigits, sizeof(fDigits)); out.write(&fPosNeg, sizeof(fPosNeg)); out.write(&fLength, sizeof(fLength)); } void Number::PrintOn(ostream& printer) const { if(fLength==0) { printer << "0"; return; } if(fPosNeg) printer << "-"; int i = kMAXDIGITS; i = fLength - 1; while(i>=0) { printer << char('0' + fDigits[i]); i--; } } Number Number::Add(const Number& other) const { Number result; CopyTo(result); if(other.Zero_p()) return result; if(this->SameSign(other)) { result.DoAdd(other); return result; } else return DoSubtract(other, 0); } Number Number::Subtract(const Number& other) const { Number result; CopyTo(result); if(other.Zero_p()) return result; if(this->SameSign(other)) return DoSubtract(other, 1); else { result.DoAdd(other); return result; } } Number Number::DoSubtract(const Number& other, int subop) const { Number result; // Set up call to subtract smaller from larger magnitude if(this->LargerThan(other)) { CopyTo(result); result.SubtractSub(other); } else { Number temp; CopyTo(temp); result = other; result.SubtractSub(temp); if(subop) result.ChangeSign(); } return result; } void Number::MakeZero() { for(int i=0;i<=kMAXDIGITS;i++) fDigits[i] = 0; fLength = 0; } void Number::Randomize() { MakeZero(); int len = (kMAXDIGITS / 2) - 1; len = rand() % len; len++; for(int i=0;i other.fLength) return (fPosNeg == 0) ? 1 : -1; if(fLength < other.fLength) return (fPosNeg == 0) ? -1 : 1; for(int i=fLength-1;i>=0;i--) if(fDigits[i] > other.fDigits[i]) return (fPosNeg == 0) ? 1 : -1; else if(fDigits[i] < other.fDigits[i]) return (fPosNeg == 0) ? -1 : 1; return 0; } void Number::CopyTo(Number& dest) const { // This function is not needed. // Can simply have dest = *this; at point of call. // Function CopyTo introduced to delay discussion of *this // until pointers covered more fully. dest.fLength = this->fLength; dest.fPosNeg = this->fPosNeg; for(int i=0; i<=kMAXDIGITS; i++) dest.fDigits[i] = this->fDigits[i]; } void Number::DoAdd(const Number& other) { int lim; int Carry = 0; lim = (fLength >= other.fLength) ? fLength : other.fLength; for(int i=0;i=10) { Carry = 1; temp -= 10; } else Carry = 0; fDigits[i] = temp; } fLength = lim; if(Carry) { if(fLength == kMAXDIGITS) Overflow(); fDigits[fLength] = 1; fLength++; } } int Number::LargerThan(const Number& other) const { if(fLength > other.fLength) return 1; if(fLength < other.fLength) return 0; for(int i=fLength-1; i>=0; i--) if(fDigits[i] > other.fDigits[i]) return 1; else if(fDigits[i] < other.fDigits[i]) return 0; return 1; } void Number::SubtractSub(const Number& other) { int Borrow = 0; int newlen = 0; for(int i=0;ikMAXDIGITS) Overflow(); for(int i=fLength-1;i>=0;i--) fDigits[i+power] = fDigits[i]; for(i = power-1;i>=0;i--) fDigits[i] = 0; fLength += power; } void Number::Product(int k) { int lim; int Carry = 0; if(k==0) { MakeZero(); return; } lim = fLength; for(int i=0;i=0;i--) { int temp; temp = 10*Carry + fDigits[i]; fDigits[i] = temp / k; if((newlen==0) && (fDigits[i] !=0)) newlen = i+1; Carry = temp % k; } fLength = newlen; } void Number::LongDiv(const Number& other) { int f; Number d(other); Number r; CopyTo(r); int m = other.fLength; int n = fLength; f = 10 / (other.fDigits[m-1] + 1); r.Product(f); d.Product(f); int newlen = 0; for(int k = n - m; k>=0; k--) { int qt; qt = r.Trial(d,k,m); if(qt==0) { fDigits[k] = 0; continue; } Number dq(d); dq.Product(qt); if(r.Smaller(dq,k,m)) { qt--; dq = dq.Subtract(d); } if((newlen==0) && (qt !=0)) newlen = k+1; fDigits[k] = qt; r.Difference(dq,k,m); } fLength = newlen; } int Number::Trial(const Number& other, int k, int m) { int km = k + m; int r3; int d2; km = k + m; r3 = (fDigits[km]*10 + fDigits[km-1])*10 + fDigits[km-2]; d2 = other.fDigits[m-1]*10 + other.fDigits[m-2]; int temp = r3 / d2; return (temp<9) ? temp : 9; } int Number::Smaller(const Number& other,int k ,int m) { int i; i = m; for(;i>0;i--) if(fDigits[i+k] != other.fDigits[i]) break; return fDigits[i+k] < other.fDigits[i]; } void Number::Difference(const Number& other,int k,int m) { int borrow = 0; for(int i = 0; i <= m; i++) { int diff = fDigits[i+k] - other.fDigits[i] - borrow + 10; fDigits[i+k] = diff % 10; borrow = 1 - (diff / 10); } if(borrow) Overflow(); }