| 1 | #ifndef BIGINTEGER_H |
| 2 | #define BIGINTEGER_H |
| 3 | |
| 4 | #include "BigUnsigned.hh" |
| 5 | |
| 6 | /* A BigInteger object represents a signed integer of size limited only by |
| 7 | * available memory. BigUnsigneds support most mathematical operators and can |
| 8 | * be converted to and from most primitive integer types. |
| 9 | * |
| 10 | * A BigInteger is just an aggregate of a BigUnsigned and a sign. (It is no |
| 11 | * longer derived from BigUnsigned because that led to harmful implicit |
| 12 | * conversions.) */ |
| 13 | class BigInteger { |
| 14 | |
| 15 | public: |
| 16 | typedef BigUnsigned::Blk Blk; |
| 17 | typedef BigUnsigned::Index Index; |
| 18 | typedef BigUnsigned::CmpRes CmpRes; |
| 19 | static const CmpRes |
| 20 | less = BigUnsigned::less , |
| 21 | equal = BigUnsigned::equal , |
| 22 | greater = BigUnsigned::greater; |
| 23 | // Enumeration for the sign of a BigInteger. |
| 24 | enum Sign { negative = -1, zero = 0, positive = 1 }; |
| 25 | |
| 26 | protected: |
| 27 | Sign sign; |
| 28 | BigUnsigned mag; |
| 29 | |
| 30 | public: |
| 31 | // Constructs zero. |
| 32 | BigInteger() : sign(zero), mag() {} |
| 33 | |
| 34 | // Copy constructor |
| 35 | BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {}; |
| 36 | |
| 37 | // Assignment operator |
| 38 | void operator=(const BigInteger &x); |
| 39 | |
| 40 | // Constructor that copies from a given array of blocks with a sign. |
| 41 | BigInteger(const Blk *b, Index blen, Sign s); |
| 42 | |
| 43 | // Nonnegative constructor that copies from a given array of blocks. |
| 44 | BigInteger(const Blk *b, Index blen) : mag(b, blen) { |
| 45 | sign = mag.isZero() ? zero : positive; |
| 46 | } |
| 47 | |
| 48 | // Constructor from a BigUnsigned and a sign |
| 49 | BigInteger(const BigUnsigned &x, Sign s); |
| 50 | |
| 51 | // Nonnegative constructor from a BigUnsigned |
| 52 | BigInteger(const BigUnsigned &x) : mag(x) { |
| 53 | sign = mag.isZero() ? zero : positive; |
| 54 | } |
| 55 | |
| 56 | // Constructors from primitive integer types |
| 57 | BigInteger(unsigned long x); |
| 58 | BigInteger( long x); |
| 59 | BigInteger(unsigned int x); |
| 60 | BigInteger( int x); |
| 61 | BigInteger(unsigned short x); |
| 62 | BigInteger( short x); |
| 63 | |
| 64 | /* Converters to primitive integer types |
| 65 | * The implicit conversion operators caused trouble, so these are now |
| 66 | * named. */ |
| 67 | unsigned long toUnsignedLong () const; |
| 68 | long toLong () const; |
| 69 | unsigned int toUnsignedInt () const; |
| 70 | int toInt () const; |
| 71 | unsigned short toUnsignedShort() const; |
| 72 | short toShort () const; |
| 73 | protected: |
| 74 | // Helper |
| 75 | template <class X> X convertToUnsignedPrimitive() const; |
| 76 | template <class X, class UX> X convertToSignedPrimitive() const; |
| 77 | public: |
| 78 | |
| 79 | // ACCESSORS |
| 80 | Sign getSign() const { return sign; } |
| 81 | /* The client can't do any harm by holding a read-only reference to the |
| 82 | * magnitude. */ |
| 83 | const BigUnsigned &getMagnitude() const { return mag; } |
| 84 | |
| 85 | // Some accessors that go through to the magnitude |
| 86 | Index getLength() const { return mag.getLength(); } |
| 87 | Index getCapacity() const { return mag.getCapacity(); } |
| 88 | Blk getBlock(Index i) const { return mag.getBlock(i); } |
| 89 | bool isZero() const { return sign == zero; } // A bit special |
| 90 | |
| 91 | // COMPARISONS |
| 92 | |
| 93 | // Compares this to x like Perl's <=> |
| 94 | CmpRes compareTo(const BigInteger &x) const; |
| 95 | |
| 96 | // Ordinary comparison operators |
| 97 | bool operator ==(const BigInteger &x) const { |
| 98 | return sign == x.sign && mag == x.mag; |
| 99 | } |
| 100 | bool operator !=(const BigInteger &x) const { return !operator ==(x); }; |
| 101 | bool operator < (const BigInteger &x) const { return compareTo(x) == less ; } |
| 102 | bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; } |
| 103 | bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; } |
| 104 | bool operator > (const BigInteger &x) const { return compareTo(x) == greater; } |
| 105 | |
| 106 | // OPERATORS -- See the discussion in BigUnsigned.hh. |
| 107 | void add (const BigInteger &a, const BigInteger &b); |
| 108 | void subtract(const BigInteger &a, const BigInteger &b); |
| 109 | void multiply(const BigInteger &a, const BigInteger &b); |
| 110 | /* See the comment on BigUnsigned::divideWithRemainder. Semantics |
| 111 | * differ from those of primitive integers when negatives and/or zeros |
| 112 | * are involved. */ |
| 113 | void divideWithRemainder(const BigInteger &b, BigInteger &q); |
| 114 | void negate(const BigInteger &a); |
| 115 | |
| 116 | /* Bitwise operators are not provided for BigIntegers. Use |
| 117 | * getMagnitude to get the magnitude and operate on that instead. */ |
| 118 | |
| 119 | BigInteger operator +(const BigInteger &x) const; |
| 120 | BigInteger operator -(const BigInteger &x) const; |
| 121 | BigInteger operator *(const BigInteger &x) const; |
| 122 | BigInteger operator /(const BigInteger &x) const; |
| 123 | BigInteger operator %(const BigInteger &x) const; |
| 124 | BigInteger operator -() const; |
| 125 | |
| 126 | void operator +=(const BigInteger &x); |
| 127 | void operator -=(const BigInteger &x); |
| 128 | void operator *=(const BigInteger &x); |
| 129 | void operator /=(const BigInteger &x); |
| 130 | void operator %=(const BigInteger &x); |
| 131 | void flipSign(); |
| 132 | |
| 133 | // INCREMENT/DECREMENT OPERATORS |
| 134 | void operator ++( ); |
| 135 | void operator ++(int); |
| 136 | void operator --( ); |
| 137 | void operator --(int); |
| 138 | }; |
| 139 | |
| 140 | // NORMAL OPERATORS |
| 141 | /* These create an object to hold the result and invoke |
| 142 | * the appropriate put-here operation on it, passing |
| 143 | * this and x. The new object is then returned. */ |
| 144 | inline BigInteger BigInteger::operator +(const BigInteger &x) const { |
| 145 | BigInteger ans; |
| 146 | ans.add(*this, x); |
| 147 | return ans; |
| 148 | } |
| 149 | inline BigInteger BigInteger::operator -(const BigInteger &x) const { |
| 150 | BigInteger ans; |
| 151 | ans.subtract(*this, x); |
| 152 | return ans; |
| 153 | } |
| 154 | inline BigInteger BigInteger::operator *(const BigInteger &x) const { |
| 155 | BigInteger ans; |
| 156 | ans.multiply(*this, x); |
| 157 | return ans; |
| 158 | } |
| 159 | inline BigInteger BigInteger::operator /(const BigInteger &x) const { |
| 160 | if (x.isZero()) throw "BigInteger::operator /: division by zero"; |
| 161 | BigInteger q, r; |
| 162 | r = *this; |
| 163 | r.divideWithRemainder(x, q); |
| 164 | return q; |
| 165 | } |
| 166 | inline BigInteger BigInteger::operator %(const BigInteger &x) const { |
| 167 | if (x.isZero()) throw "BigInteger::operator %: division by zero"; |
| 168 | BigInteger q, r; |
| 169 | r = *this; |
| 170 | r.divideWithRemainder(x, q); |
| 171 | return r; |
| 172 | } |
| 173 | inline BigInteger BigInteger::operator -() const { |
| 174 | BigInteger ans; |
| 175 | ans.negate(*this); |
| 176 | return ans; |
| 177 | } |
| 178 | |
| 179 | /* |
| 180 | * ASSIGNMENT OPERATORS |
| 181 | * |
| 182 | * Now the responsibility for making a temporary copy if necessary |
| 183 | * belongs to the put-here operations. See Assignment Operators in |
| 184 | * BigUnsigned.hh. |
| 185 | */ |
| 186 | inline void BigInteger::operator +=(const BigInteger &x) { |
| 187 | add(*this, x); |
| 188 | } |
| 189 | inline void BigInteger::operator -=(const BigInteger &x) { |
| 190 | subtract(*this, x); |
| 191 | } |
| 192 | inline void BigInteger::operator *=(const BigInteger &x) { |
| 193 | multiply(*this, x); |
| 194 | } |
| 195 | inline void BigInteger::operator /=(const BigInteger &x) { |
| 196 | if (x.isZero()) throw "BigInteger::operator /=: division by zero"; |
| 197 | /* The following technique is slightly faster than copying *this first |
| 198 | * when x is large. */ |
| 199 | BigInteger q; |
| 200 | divideWithRemainder(x, q); |
| 201 | // *this contains the remainder, but we overwrite it with the quotient. |
| 202 | *this = q; |
| 203 | } |
| 204 | inline void BigInteger::operator %=(const BigInteger &x) { |
| 205 | if (x.isZero()) throw "BigInteger::operator %=: division by zero"; |
| 206 | BigInteger q; |
| 207 | // Mods *this by x. Don't care about quotient left in q. |
| 208 | divideWithRemainder(x, q); |
| 209 | } |
| 210 | // This one is trivial |
| 211 | inline void BigInteger::flipSign() { |
| 212 | sign = Sign(-sign); |
| 213 | } |
| 214 | |
| 215 | #endif |