Commit | Line | Data |
---|---|---|
b35b6967 MM |
1 | #ifndef BIGINTEGER_H |
2 | #define BIGINTEGER_H | |
e67d6049 | 3 | |
05780f4b | 4 | #include "BigUnsigned.hh" |
e67d6049 | 5 | |
3e132790 MM |
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. | |
6e1e0f2f | 9 | * |
3e132790 MM |
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 { | |
5ff40cf5 | 14 | |
2301f99c | 15 | public: |
3e132790 MM |
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 }; | |
5ff40cf5 | 25 | |
2301f99c | 26 | protected: |
3e132790 MM |
27 | Sign sign; |
28 | BigUnsigned mag; | |
5ff40cf5 | 29 | |
2301f99c | 30 | public: |
3e132790 MM |
31 | // Constructs zero. |
32 | BigInteger() : sign(zero), mag() {} | |
33 | ||
34 | // Copy constructor | |
35 | BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {}; | |
05780f4b | 36 | |
3e132790 MM |
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; | |
05780f4b | 46 | } |
3e132790 MM |
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; | |
05780f4b | 54 | } |
3e132790 MM |
55 | |
56 | // Constructors from primitive integer types | |
e67d6049 MM |
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); | |
5ff40cf5 | 63 | |
3e132790 MM |
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; | |
2301f99c | 77 | public: |
3e132790 MM |
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 | |
5ff40cf5 | 90 | |
e67d6049 | 91 | // COMPARISONS |
3e132790 | 92 | |
e67d6049 MM |
93 | // Compares this to x like Perl's <=> |
94 | CmpRes compareTo(const BigInteger &x) const; | |
3e132790 MM |
95 | |
96 | // Ordinary comparison operators | |
05780f4b | 97 | bool operator ==(const BigInteger &x) const { |
3e132790 | 98 | return sign == x.sign && mag == x.mag; |
05780f4b MM |
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; } | |
5ff40cf5 | 105 | |
3e132790 MM |
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. */ | |
05780f4b | 113 | void divideWithRemainder(const BigInteger &b, BigInteger &q); |
3e132790 MM |
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(); | |
5ff40cf5 | 132 | |
e67d6049 | 133 | // INCREMENT/DECREMENT OPERATORS |
3e132790 MM |
134 | void operator ++( ); |
135 | void operator ++(int); | |
136 | void operator --( ); | |
137 | void operator --(int); | |
e67d6049 MM |
138 | }; |
139 | ||
e67d6049 MM |
140 | // NORMAL OPERATORS |
141 | /* These create an object to hold the result and invoke | |
6e1e0f2f MM |
142 | * the appropriate put-here operation on it, passing |
143 | * this and x. The new object is then returned. */ | |
e67d6049 MM |
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 { | |
0afe80d5 | 160 | if (x.isZero()) throw "BigInteger::operator /: division by zero"; |
3e132790 MM |
161 | BigInteger q, r; |
162 | r = *this; | |
163 | r.divideWithRemainder(x, q); | |
164 | return q; | |
e67d6049 MM |
165 | } |
166 | inline BigInteger BigInteger::operator %(const BigInteger &x) const { | |
0afe80d5 | 167 | if (x.isZero()) throw "BigInteger::operator %: division by zero"; |
3e132790 MM |
168 | BigInteger q, r; |
169 | r = *this; | |
170 | r.divideWithRemainder(x, q); | |
171 | return r; | |
e67d6049 MM |
172 | } |
173 | inline BigInteger BigInteger::operator -() const { | |
174 | BigInteger ans; | |
175 | ans.negate(*this); | |
176 | return ans; | |
177 | } | |
178 | ||
8c16728a MM |
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 | */ | |
e67d6049 | 186 | inline void BigInteger::operator +=(const BigInteger &x) { |
8c16728a | 187 | add(*this, x); |
e67d6049 MM |
188 | } |
189 | inline void BigInteger::operator -=(const BigInteger &x) { | |
8c16728a | 190 | subtract(*this, x); |
e67d6049 MM |
191 | } |
192 | inline void BigInteger::operator *=(const BigInteger &x) { | |
8c16728a | 193 | multiply(*this, x); |
e67d6049 MM |
194 | } |
195 | inline void BigInteger::operator /=(const BigInteger &x) { | |
0afe80d5 MM |
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; | |
e67d6049 MM |
203 | } |
204 | inline void BigInteger::operator %=(const BigInteger &x) { | |
0afe80d5 | 205 | if (x.isZero()) throw "BigInteger::operator %=: division by zero"; |
05780f4b | 206 | BigInteger q; |
0afe80d5 | 207 | // Mods *this by x. Don't care about quotient left in q. |
05780f4b | 208 | divideWithRemainder(x, q); |
e67d6049 MM |
209 | } |
210 | // This one is trivial | |
211 | inline void BigInteger::flipSign() { | |
212 | sign = Sign(-sign); | |
213 | } | |
214 | ||
215 | #endif |