Commit | Line | Data |
---|---|---|
b35b6967 MM |
1 | #ifndef BIGUNSIGNED_H |
2 | #define BIGUNSIGNED_H | |
e67d6049 | 3 | |
05780f4b MM |
4 | #include "NumberlikeArray.hh" |
5 | ||
3e132790 MM |
6 | /* A BigUnsigned object represents a nonnegative 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 | * The number is stored as a NumberlikeArray of unsigned longs as if it were |
11 | * written in base 256^sizeof(unsigned long). The least significant block is | |
12 | * first, and the length is such that the most significant block is nonzero. */ | |
05780f4b | 13 | class BigUnsigned : protected NumberlikeArray<unsigned long> { |
5ff40cf5 | 14 | |
2301f99c | 15 | public: |
3e132790 MM |
16 | // Enumeration for the result of a comparison. |
17 | enum CmpRes { less = -1, equal = 0, greater = 1 }; | |
5ff40cf5 | 18 | |
3e132790 MM |
19 | // BigUnsigneds are built with a Blk type of unsigned long. |
20 | typedef unsigned long Blk; | |
5ff40cf5 | 21 | |
3e132790 MM |
22 | typedef NumberlikeArray<Blk>::Index Index; |
23 | NumberlikeArray<Blk>::N; | |
5ff40cf5 | 24 | |
3e132790 MM |
25 | protected: |
26 | // Creates a BigUnsigned with a capacity; for internal use. | |
27 | BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} | |
5ff40cf5 | 28 | |
3e132790 MM |
29 | // Decreases len to eliminate any leading zero blocks. |
30 | void zapLeadingZeros() { | |
05780f4b MM |
31 | while (len > 0 && blk[len - 1] == 0) |
32 | len--; | |
33 | } | |
5ff40cf5 | 34 | |
2301f99c | 35 | public: |
3e132790 MM |
36 | // Constructs zero. |
37 | BigUnsigned() : NumberlikeArray<Blk>() {} | |
38 | ||
39 | // Copy constructor | |
40 | BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {} | |
5ff40cf5 | 41 | |
3e132790 MM |
42 | // Assignment operator |
43 | void operator=(const BigUnsigned &x) { | |
05780f4b MM |
44 | NumberlikeArray<Blk>::operator =(x); |
45 | } | |
5ff40cf5 | 46 | |
3e132790 MM |
47 | // Constructor that copies from a given array of blocks. |
48 | BigUnsigned(const Blk *b, Index blen) : NumberlikeArray<Blk>(b, blen) { | |
49 | // Eliminate any leading zeros we may have been passed. | |
05780f4b MM |
50 | zapLeadingZeros(); |
51 | } | |
5ff40cf5 | 52 | |
3e132790 MM |
53 | // Destructor. NumberlikeArray does the delete for us. |
54 | ~BigUnsigned() {} | |
55 | ||
56 | // Constructors from primitive integer types | |
e67d6049 MM |
57 | BigUnsigned(unsigned long x); |
58 | BigUnsigned( long x); | |
59 | BigUnsigned(unsigned int x); | |
60 | BigUnsigned( int x); | |
61 | BigUnsigned(unsigned short x); | |
62 | BigUnsigned( short x); | |
3e132790 MM |
63 | protected: |
64 | // Helpers | |
65 | template <class X> void initFromPrimitive(X x); | |
66 | template <class X> void initFromSignedPrimitive(X x); | |
2301f99c | 67 | public: |
3e132790 MM |
68 | |
69 | /* Converters to primitive integer types | |
70 | * The implicit conversion operators caused trouble, so these are now | |
71 | * named. */ | |
72 | unsigned long toUnsignedLong () const; | |
73 | long toLong () const; | |
74 | unsigned int toUnsignedInt () const; | |
75 | int toInt () const; | |
76 | unsigned short toUnsignedShort() const; | |
77 | short toShort () const; | |
78 | protected: | |
79 | // Helpers | |
80 | template <class X> X convertToSignedPrimitive() const; | |
81 | template <class X> X convertToPrimitive() const; | |
2301f99c | 82 | public: |
3e132790 MM |
83 | |
84 | // ACCESSORS | |
85 | ||
86 | // Expose these from NumberlikeArray directly. | |
05780f4b MM |
87 | NumberlikeArray<Blk>::getCapacity; |
88 | NumberlikeArray<Blk>::getLength; | |
3e132790 MM |
89 | |
90 | /* Returns the requested block, or 0 if it is beyond the length (as if | |
91 | * the number had 0s infinitely to the left). */ | |
05780f4b | 92 | Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; } |
3e132790 MM |
93 | |
94 | // The number is zero if and only if the canonical length is zero. | |
95 | bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } | |
5ff40cf5 | 96 | |
e67d6049 | 97 | // COMPARISONS |
3e132790 | 98 | |
e67d6049 MM |
99 | // Compares this to x like Perl's <=> |
100 | CmpRes compareTo(const BigUnsigned &x) const; | |
3e132790 MM |
101 | |
102 | // Ordinary comparison operators | |
918d66f2 MM |
103 | bool operator ==(const BigUnsigned &x) const { |
104 | return NumberlikeArray<Blk>::operator ==(x); | |
105 | } | |
106 | bool operator !=(const BigUnsigned &x) const { | |
107 | return NumberlikeArray<Blk>::operator !=(x); | |
108 | } | |
05780f4b MM |
109 | bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; } |
110 | bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; } | |
111 | bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; } | |
112 | bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; } | |
a8b42b68 MM |
113 | |
114 | /* | |
6e1e0f2f MM |
115 | * BigUnsigned and BigInteger both provide three kinds of operators. |
116 | * Here ``big-integer'' refers to BigInteger or BigUnsigned. | |
117 | * | |
118 | * (1) Overloaded ``return-by-value'' operators: | |
3e132790 MM |
119 | * +, -, *, /, %, unary -, &, |, ^, <<, >>. |
120 | * Big-integer code using these operators looks identical to code using | |
121 | * the primitive integer types. These operators take one or two | |
122 | * big-integer inputs and return a big-integer result, which can then | |
123 | * be assigned to a BigInteger variable or used in an expression. | |
124 | * Example: | |
6e1e0f2f MM |
125 | * BigInteger a(1), b = 1; |
126 | * BigInteger c = a + b; | |
127 | * | |
128 | * (2) Overloaded assignment operators: | |
3e132790 MM |
129 | * +=, -=, *=, /=, %=, flipSign, &=, |=, ^=, <<=, >>=, ++, --. |
130 | * Again, these are used on big integers just like on ints. They take | |
131 | * one writable big integer that both provides an operand and receives a | |
132 | * result. Most also take a second read-only operand. | |
133 | * Example: | |
6e1e0f2f MM |
134 | * BigInteger a(1), b(1); |
135 | * a += b; | |
136 | * | |
3e132790 MM |
137 | * (3) Copy-less operations: `add', `subtract', etc. |
138 | * These named methods take operands as arguments and store the result | |
139 | * in the receiver (*this), avoiding unnecessary copies and allocations. | |
140 | * `divideWithRemainder' is special: it both takes the dividend from and | |
141 | * stores the remainder into the receiver, and it takes a separate | |
142 | * object in which to store the quotient. NOTE: If you are wondering | |
143 | * why these don't return a value, you probably mean to use the | |
144 | * overloaded return-by-value operators instead. | |
145 | * | |
6e1e0f2f MM |
146 | * Examples: |
147 | * BigInteger a(43), b(7), c, d; | |
3e132790 | 148 | * |
6e1e0f2f | 149 | * c = a + b; // Now c == 50. |
3e132790 MM |
150 | * c.add(a, b); // Same effect but without the two copies. |
151 | * | |
152 | * c.divideWithRemainder(b, d); | |
153 | * // 50 / 7; now d == 7 (quotient) and c == 1 (remainder). | |
154 | * | |
155 | * // ``Aliased'' calls now do the right thing using a temporary | |
156 | * // copy, but see note on `divideWithRemainder'. | |
157 | * a.add(a, b); | |
6e1e0f2f | 158 | */ |
5ff40cf5 | 159 | |
3e132790 MM |
160 | // COPY-LESS OPERATIONS |
161 | ||
162 | // These 8: Arguments are read-only operands, result is saved in *this. | |
163 | void add(const BigUnsigned &a, const BigUnsigned &b); | |
164 | void subtract(const BigUnsigned &a, const BigUnsigned &b); | |
165 | void multiply(const BigUnsigned &a, const BigUnsigned &b); | |
166 | void bitAnd(const BigUnsigned &a, const BigUnsigned &b); | |
167 | void bitOr(const BigUnsigned &a, const BigUnsigned &b); | |
168 | void bitXor(const BigUnsigned &a, const BigUnsigned &b); | |
169 | void bitShiftLeft(const BigUnsigned &a, unsigned int b); | |
170 | void bitShiftRight(const BigUnsigned &a, unsigned int b); | |
171 | ||
172 | /* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'. | |
173 | * / and % use semantics similar to Knuth's, which differ from the | |
174 | * primitive integer semantics under division by zero. See the | |
175 | * implementation in BigUnsigned.cc for details. | |
176 | * `a.divideWithRemainder(b, a)' throws an exception: it doesn't make | |
177 | * sense to write quotient and remainder into the same variable. */ | |
05780f4b | 178 | void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); |
3e132790 MM |
179 | |
180 | /* `divide' and `modulo' are no longer offered. Use | |
181 | * `divideWithRemainder' instead. */ | |
182 | ||
183 | // OVERLOADED RETURN-BY-VALUE OPERATORS | |
184 | BigUnsigned operator +(const BigUnsigned &x) const; | |
185 | BigUnsigned operator -(const BigUnsigned &x) const; | |
186 | BigUnsigned operator *(const BigUnsigned &x) const; | |
187 | BigUnsigned operator /(const BigUnsigned &x) const; | |
188 | BigUnsigned operator %(const BigUnsigned &x) const; | |
189 | /* OK, maybe unary minus could succeed in one case, but it really | |
190 | * shouldn't be used, so it isn't provided. */ | |
191 | BigUnsigned operator &(const BigUnsigned &x) const; | |
192 | BigUnsigned operator |(const BigUnsigned &x) const; | |
193 | BigUnsigned operator ^(const BigUnsigned &x) const; | |
194 | BigUnsigned operator <<(unsigned int b) const; | |
195 | BigUnsigned operator >>(unsigned int b) const; | |
ef2b7c59 | 196 | // Additional operators in an attempt to avoid overloading tangles. |
3e132790 | 197 | // XXX Why exactly are these needed? |
ef2b7c59 MM |
198 | BigUnsigned operator <<(int b) const; |
199 | BigUnsigned operator >>(int b) const; | |
5ff40cf5 | 200 | |
3e132790 MM |
201 | // OVERLOADED ASSIGNMENT OPERATORS |
202 | void operator +=(const BigUnsigned &x); | |
203 | void operator -=(const BigUnsigned &x); | |
204 | void operator *=(const BigUnsigned &x); | |
205 | void operator /=(const BigUnsigned &x); | |
206 | void operator %=(const BigUnsigned &x); | |
207 | void operator &=(const BigUnsigned &x); | |
208 | void operator |=(const BigUnsigned &x); | |
209 | void operator ^=(const BigUnsigned &x); | |
210 | void operator <<=(unsigned int b); | |
211 | void operator >>=(unsigned int b); | |
ef2b7c59 | 212 | // Additional operators in an attempt to avoid overloading tangles. |
3e132790 | 213 | // XXX Why exactly are these needed? |
ef2b7c59 MM |
214 | void operator <<=(int b); |
215 | void operator >>=(int b); | |
5ff40cf5 | 216 | |
3e132790 MM |
217 | /* INCREMENT/DECREMENT OPERATORS |
218 | * To discourage messy coding, these do not return *this, so prefix | |
219 | * and postfix behave the same. */ | |
220 | void operator ++( ); | |
221 | void operator ++(int); | |
222 | void operator --( ); | |
223 | void operator --(int); | |
5ff40cf5 | 224 | |
4efbb076 | 225 | // Helper function that needs access to BigUnsigned internals |
3e132790 MM |
226 | friend Blk getShiftedBlock(const BigUnsigned &num, Index x, |
227 | unsigned int y); | |
228 | ||
229 | // See BigInteger.cc. | |
230 | template <class X> | |
231 | friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a); | |
e67d6049 MM |
232 | }; |
233 | ||
3e132790 MM |
234 | /* Implementing the return-by-value and assignment operators in terms of the |
235 | * copy-less operations. The copy-less operations are responsible for making | |
236 | * any necessary temporary copies to work around aliasing. */ | |
237 | ||
e67d6049 MM |
238 | inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { |
239 | BigUnsigned ans; | |
240 | ans.add(*this, x); | |
241 | return ans; | |
242 | } | |
243 | inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const { | |
244 | BigUnsigned ans; | |
245 | ans.subtract(*this, x); | |
246 | return ans; | |
247 | } | |
248 | inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { | |
249 | BigUnsigned ans; | |
250 | ans.multiply(*this, x); | |
251 | return ans; | |
252 | } | |
253 | inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { | |
3e132790 MM |
254 | BigUnsigned q, r; |
255 | r = *this; | |
256 | r.divideWithRemainder(x, q); | |
257 | return q; | |
e67d6049 MM |
258 | } |
259 | inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { | |
3e132790 MM |
260 | BigUnsigned q, r; |
261 | r = *this; | |
262 | r.divideWithRemainder(x, q); | |
263 | return r; | |
e67d6049 MM |
264 | } |
265 | inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { | |
266 | BigUnsigned ans; | |
267 | ans.bitAnd(*this, x); | |
268 | return ans; | |
269 | } | |
270 | inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const { | |
271 | BigUnsigned ans; | |
272 | ans.bitOr(*this, x); | |
273 | return ans; | |
274 | } | |
275 | inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { | |
276 | BigUnsigned ans; | |
277 | ans.bitXor(*this, x); | |
278 | return ans; | |
279 | } | |
ef2b7c59 MM |
280 | inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const { |
281 | BigUnsigned ans; | |
282 | ans.bitShiftLeft(*this, b); | |
283 | return ans; | |
284 | } | |
285 | inline BigUnsigned BigUnsigned::operator >>(unsigned int b) const { | |
286 | BigUnsigned ans; | |
287 | ans.bitShiftRight(*this, b); | |
288 | return ans; | |
289 | } | |
290 | inline BigUnsigned BigUnsigned::operator <<(int b) const { | |
291 | if (b < 0) | |
3e132790 | 292 | throw "BigUnsigned::operator <<(int): Negative shift amounts are not allowed"; |
ef2b7c59 MM |
293 | return *this << (unsigned int)(b); |
294 | } | |
295 | inline BigUnsigned BigUnsigned::operator >>(int b) const { | |
296 | if (b < 0) | |
3e132790 | 297 | throw "BigUnsigned::operator >>(int): Negative shift amounts are not allowed"; |
ef2b7c59 MM |
298 | return *this >> (unsigned int)(b); |
299 | } | |
e67d6049 | 300 | |
e67d6049 | 301 | inline void BigUnsigned::operator +=(const BigUnsigned &x) { |
8c16728a | 302 | add(*this, x); |
e67d6049 MM |
303 | } |
304 | inline void BigUnsigned::operator -=(const BigUnsigned &x) { | |
8c16728a | 305 | subtract(*this, x); |
e67d6049 MM |
306 | } |
307 | inline void BigUnsigned::operator *=(const BigUnsigned &x) { | |
8c16728a | 308 | multiply(*this, x); |
e67d6049 MM |
309 | } |
310 | inline void BigUnsigned::operator /=(const BigUnsigned &x) { | |
3e132790 MM |
311 | /* The following technique is slightly faster than copying *this first |
312 | * when x is large. */ | |
313 | BigUnsigned q; | |
314 | divideWithRemainder(x, q); | |
315 | // *this contains the remainder, but we overwrite it with the quotient. | |
316 | *this = q; | |
e67d6049 MM |
317 | } |
318 | inline void BigUnsigned::operator %=(const BigUnsigned &x) { | |
05780f4b | 319 | BigUnsigned q; |
3e132790 | 320 | // Mods *this by x. Don't care about quotient left in q. |
05780f4b | 321 | divideWithRemainder(x, q); |
e67d6049 MM |
322 | } |
323 | inline void BigUnsigned::operator &=(const BigUnsigned &x) { | |
8c16728a | 324 | bitAnd(*this, x); |
e67d6049 MM |
325 | } |
326 | inline void BigUnsigned::operator |=(const BigUnsigned &x) { | |
8c16728a | 327 | bitOr(*this, x); |
e67d6049 MM |
328 | } |
329 | inline void BigUnsigned::operator ^=(const BigUnsigned &x) { | |
8c16728a | 330 | bitXor(*this, x); |
e67d6049 | 331 | } |
ef2b7c59 MM |
332 | inline void BigUnsigned::operator <<=(unsigned int b) { |
333 | bitShiftLeft(*this, b); | |
334 | } | |
335 | inline void BigUnsigned::operator >>=(unsigned int b) { | |
336 | bitShiftRight(*this, b); | |
337 | } | |
338 | inline void BigUnsigned::operator <<=(int b) { | |
339 | if (b < 0) | |
340 | throw "BigUnsigned::operator <<=(int): Negative shift amounts are not supported"; | |
341 | *this <<= (unsigned int)(b); | |
342 | } | |
343 | inline void BigUnsigned::operator >>=(int b) { | |
344 | if (b < 0) | |
345 | throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported"; | |
346 | *this >>= (unsigned int)(b); | |
347 | } | |
e67d6049 MM |
348 | |
349 | #endif |