codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <string> #include <cctype> #include <cassert> enum { BIT = 3, // for test // BIT = 30, CMASK = 1 << BIT, BMASK = CMASK - 1 }; class BigInteger { private: int n; int *b; private: friend BigInteger sub(BigInteger const &a, BigInteger const &b, int &carry); friend BigInteger mul1(BigInteger const &a, BigInteger const &b); friend BigInteger mul2(BigInteger const &a, BigInteger const &b); friend BigInteger div1(BigInteger const &a, BigInteger const &b, BigInteger &r); friend void div2(BigInteger const &a, BigInteger const &b, BigInteger &q, BigInteger &r); static bool iszero(BigInteger &n); static void LeftShift(BigInteger &a); static void RightShift(BigInteger &a, int &lsb); static void LeftShift2(int &msb, BigInteger &a); static void LeftShift3(BigInteger &a, int msb); public: BigInteger(); BigInteger(const BigInteger &ob); BigInteger(const int n); ~BigInteger(); BigInteger &operator=(BigInteger n); friend bool operator==(BigInteger const &a, BigInteger const &b); friend bool operator!=(BigInteger const &a, BigInteger const &b); friend BigInteger operator+(BigInteger const &a, BigInteger const &b); friend BigInteger operator-(BigInteger const &a, BigInteger const &b); friend BigInteger operator*(BigInteger const &a, BigInteger const &b); friend BigInteger operator/(BigInteger const &a, BigInteger const &b); friend BigInteger operator%(BigInteger const &a, BigInteger const &b); friend bool operator<(BigInteger const &a, BigInteger const &b); friend bool operator<=(BigInteger const &a, BigInteger const &b); friend std::ostream &operator<<(std::ostream &stream, BigInteger c); void dump() const { std::cout << "n = " << this->n << ": "; for (int i = 0; i < this->n; i++) std::cout << i << ":" << this->b[i] << ","; std::cout << std::endl; } }; BigInteger::BigInteger() { this->n = 1; this->b = new int[1]; this->b[0] = 0; } BigInteger::BigInteger(const BigInteger &ob) { this->n = ob.n; if (ob.n == 0) { this->b = 0; } else { this->b = new int[ob.n]; for (int i = 0; i < ob.n; i++) this->b[i] = ob.b[i]; } } BigInteger::BigInteger(const int c) { if (c <= 0) { this->n = 1; this->b = new int[1]; this->b[0] = 0; } else { int *newbody; int bodysize = 0; int i, j, r, cc, pos; this->b = 0; this->n = 0; cc = c; while (cc > 0) { r = 0; pos = 1; for (i = 0; i < BIT; i++) { if ((cc & 1) != 0) { r = (r | pos); } else { } pos = pos * 2; cc = cc / 2; } newbody = new int[this->n + 1]; for (j = 0; j < this->n; j++) newbody[j] = this->b[j]; newbody[j] = r; /* j == this->n */ delete this->b; this->b = newbody; this->n++; } } assert(this->n != 0); } BigInteger &BigInteger::operator=(BigInteger ob) { this->n = ob.n; if (ob.n == 0) { delete [] this->b; this->b = 0; } else { delete [] this->b; this->b = new int[ob.n]; for (int i = 0; i < ob.n; i++) { this->b[i] = ob.b[i]; } } return *this; } BigInteger::~BigInteger() { delete [] this->b; this->b = 0; this->n = 0; } bool operator==(BigInteger const &a, BigInteger const &b) { int i, more, less; bool isEqual = true; if (a.n < b.n) { less = a.n; } else { less = b.n; } for (i = 0; i < less; i++) { if ((a.b[i]) != (b.b[i])) { isEqual = false; } } if (a.n < b.n) { for (; i < b.n; i++) if (b.b[i] != 0) { isEqual = false; } } else { for (;i < a.n; i++) if (a.b[i] != 0) { isEqual = false; } } return isEqual; } bool operator!=(BigInteger const &a, BigInteger const &b) { return !(a == b); } BigInteger operator+(BigInteger const &a, BigInteger const &b) { BigInteger r; BigInteger const * more_ab; int less_n; if (a.n > b.n) { r.n = a.n; more_ab = &a; less_n = b.n; } else { r.n = b.n; more_ab = &b; less_n = a.n; } r.b = new int [r.n]; int i, carry = 0; for (i = 0; i < less_n; i++) { int s = a.b[i] + b.b[i] + carry; if (s >= CMASK) { carry = 1; r.b[i] = (s & BMASK); } else { carry = 0; r.b[i] = s; /* need */ } } for (;i < r.n; i++) { int s = more_ab->b[i] + carry; if (s >= CMASK) { carry = 1; r.b[i] = (s & BMASK); /* need */ } else { carry = 0; r.b[i] = (s & BMASK); /* need */ /* not to insert break keyword.*/ } } if (carry) { int *new_body = new int [r.n + 1]; for (i = 0; i < r.n; i++) new_body[i] = r.b[i]; new_body[i] = carry; delete [] r.b; r.b = new_body; r.b[r.n] = 1; /* need */ r.n++; } return r; } BigInteger operator-(BigInteger const &a, BigInteger const &b) { int dmy; return sub(a, b, dmy); } bool operator<(BigInteger const &a, BigInteger const &b) { int borrow; sub(a, b, borrow); if (borrow != 0) { return true; } else { return false; } } bool operator<=(BigInteger const &a, BigInteger const &b) { if (a < b) return true; if (a == b) return true; return false; } BigInteger sub(BigInteger const &a, BigInteger const &b, int &borrowR) { int vCount, moreCount, i; int diff; bool flagMore, flagLess; BigInteger r; flagMore = false; flagLess = false; moreCount = a.n; vCount = a.n; r = a; if (a.n > b.n) { flagMore = true; vCount = b.n; moreCount = a.n; r = a; } if (a.n < b.n) { flagLess = true; vCount = a.n; moreCount = b.n; r = b; } borrowR = 0; for (i = 0; i < vCount; i++) { diff = a.b[i] - b.b[i] - borrowR; if (diff < 0) { borrowR = 1; r.b[i] = diff + CMASK; } else { borrowR = 0; r.b[i] = diff; } } if (flagMore) { for (;i < moreCount; i++) { diff = a.b[i] - borrowR; if (diff < 0) { borrowR = 1; r.b[i] = diff + CMASK; } else { borrowR = 0; r.b[i] = diff; } } } if (flagLess) { for (;i < moreCount; i++) { if (b.b[i] > 0) { borrowR = 1; } } } // std::cout << a << "-" << b << "==" << r << ":" << borrowR << " "; // std::cout << "a.n=" << a.n <<",b.n=" << b.n << std::endl; return r; } BigInteger operator*(BigInteger const &a, BigInteger const &b) { return mul2(a, b); } BigInteger mul2(BigInteger const &a, BigInteger const &b) { BigInteger Rshift = b; BigInteger Lshift = a; BigInteger r = 0; int lsb; while (!BigInteger::iszero(Rshift)) { BigInteger::RightShift(Rshift, lsb); if (lsb) { r = r + Lshift; } BigInteger::LeftShift(Lshift); } return r; } void BigInteger::LeftShift(BigInteger &a) { int i, msb; msb = 0; for (i = 0; i < a.n; i++) { a.b[i] *= 2; if (msb > 0) a.b[i] = (a.b[i] | 0x01); if (a.b[i] > BMASK) { msb = 1; a.b[i] -= CMASK; } else { msb = 0; } } if (msb > 0) { int *newbody; newbody = new int [a.n + 1]; newbody[a.n] = 1; for (int i = 0; i < a.n; i++) { newbody[i] = a.b[i]; } a.n++; delete a.b; a.b = newbody; } } void BigInteger::RightShift(BigInteger &a, int &lsb_out) { int i, lsb; lsb = 0; for (i = a.n - 1; i >= 0; --i) { if (lsb > 0) a.b[i] = (a.b[i] | CMASK); if ((a.b[i] & 0x01) > 0) lsb = 1; else lsb = 0; a.b[i] /= 2; } lsb_out = lsb; if (a.b[a.n - 1] == 0) { int *newbody; newbody = new int [a.n - 1]; for (int i = 0; i < a.n - 1; i++) newbody[i] = a.b[i]; a.n--; delete a.b; a.b = newbody; } } BigInteger mul1(BigInteger const &a, BigInteger const &b) { BigInteger r = 0; for (BigInteger i = BigInteger(0); i < b; i = i + 1) r = r + a; return r; } void BigInteger::LeftShift2(int &msb, BigInteger &a) { int i, msb_v; msb_v = 0; for (i = 0; i < a.n; i++) { a.b[i] *= 2; if (msb_v > 0) a.b[i] = (a.b[i] | 0x01); if (a.b[i] > BMASK) { msb_v = 1; a.b[i] -= CMASK; } else { msb_v = 0; } } msb = msb_v; } void BigInteger::LeftShift3(BigInteger &a, int msb) { int i, msb_v; msb_v = msb; for (i = 0; i < a.n; i++) { a.b[i] *= 2; if (msb_v > 0) a.b[i] = (a.b[i] | 0x01); if (a.b[i] > BMASK) { msb_v = 1; a.b[i] -= CMASK; } else { msb_v = 0; } } if (msb_v > 0) { int *newbody; newbody = new int [a.n + 1]; newbody[a.n] = 1; for (int i = 0; i < a.n; i++) { newbody[i] = a.b[i]; } a.n++; delete a.b; a.b = newbody; } } void div2(BigInteger const &a, BigInteger const &b, BigInteger &q, BigInteger &r) { if (b == BigInteger(0)) { std::cout << "null devided." << std::endl; return; } /* LeftRest <- LeftShiftBuff */ BigInteger LeftRest(0); BigInteger LeftShiftBuff = a; BigInteger Quotient(0); int msb, lsb; msb = 0; int n = a.n * BIT; while (n > 0) { // std::cout << "LeftShiftBuff=" << LeftShiftBuff << std::endl; // std::cout << "LeftRest=" << LeftRest << std::endl; BigInteger::LeftShift2(msb, LeftShiftBuff); BigInteger::LeftShift3(LeftRest, msb); lsb = 0; if (b <= LeftRest) { LeftRest = LeftRest - b; lsb = 1; } BigInteger::LeftShift3(Quotient, lsb); // std::cout << "Quotient=" << Quotient << std::endl; n--; } q = Quotient; r = LeftRest; } BigInteger operator/(BigInteger const &a, BigInteger const &b) { BigInteger q, r; div2(a, b, q, r); return q; } BigInteger operator%(BigInteger const &a, BigInteger const &b){ BigInteger q, r; div2(a, b, q, r); return r; } BigInteger div1(BigInteger const &a, BigInteger const &b, BigInteger &r) { BigInteger q(0); BigInteger rest = a; while ((b < rest) || (b == rest)) { q = q + BigInteger(1); rest = rest - b; } r = rest; return q; } bool BigInteger::iszero(BigInteger &n) { bool isZero = true; for (int i = 0; i < n.n; i++) if (n.b[i] != 0) { isZero = false; break; } return isZero; } std::ostream &operator<<(std::ostream &stream, BigInteger c) { std::basic_string<char> mod10; BigInteger q, n; int mod; bool fzero; fzero = true; n = c; for(;;) { /* div10(n, q, mod); */ { q = n; mod = 0; for (int i = 0; i < n.n * BIT; i++) { /* shift_div(mod, q); */ { int cy, i; cy = 0; for (i = 0; i < n.n; i++) { q.b[i] = q.b[i] << 1; if (cy) q.b[i] = q.b[i] | 0x01; cy = (q.b[i] >> BIT); q.b[i] = q.b[i] & BMASK; } mod = mod << 1; if (cy) mod = mod | 0x01; } if (mod >= 10) { q.b[0] = q.b[0] | 0x01; mod = mod - 10; } } } if (BigInteger::iszero(q) && mod == 0) break; mod10 = (char)('0' + mod) + mod10; fzero = false; n = q; } if (fzero) stream << '0'; else stream << mod10; return stream; } int main() { BigInteger s; for (int n = 1; n <= 100; n++) { BigInteger t(n); s = s + t; } std::cout << s << std::endl; const int a = 1234; const int b = 123; // r = 12345C1234 BigInteger r(1); int l, m, n; for (l = 1, m = a, n = b; n > 0; m--, n--, l++) { BigInteger s1(m); BigInteger s2(l); r = r * s1; r = r / s2; } std::cout << r << std::endl; return 0; } /* end */
Private
[
?
]
Run code
Submit