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 | |
83a639e6 | 65 | template <class X> void initFromPrimitive (X x); |
3e132790 | 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; | |
83a639e6 | 81 | template <class X> X convertToPrimitive () const; |
2301f99c | 82 | public: |
3e132790 | 83 | |
88dbe518 | 84 | // BIT/BLOCK ACCESSORS |
3e132790 MM |
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]; } |
88dbe518 | 93 | void setBlock(Index i, Blk newBlock); |
3e132790 MM |
94 | |
95 | // The number is zero if and only if the canonical length is zero. | |
96 | bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } | |
5ff40cf5 | 97 | |
88dbe518 MM |
98 | /* Returns the length of the number in bits, i.e., zero if the number |
99 | * is zero and otherwise one more than the largest value of bi for | |
100 | * which getBit(bi) returns true. */ | |
101 | Index bitLength() const; | |
102 | // Get or set bit number bi, which has value 2^bi. | |
103 | bool getBit(Index bi) const { | |
104 | return (getBlock(bi / N) & (1 << (bi % N))) != 0; | |
105 | } | |
106 | void setBit(Index bi, bool newBit); | |
107 | ||
e67d6049 | 108 | // COMPARISONS |
3e132790 | 109 | |
e67d6049 MM |
110 | // Compares this to x like Perl's <=> |
111 | CmpRes compareTo(const BigUnsigned &x) const; | |
3e132790 MM |
112 | |
113 | // Ordinary comparison operators | |
918d66f2 MM |
114 | bool operator ==(const BigUnsigned &x) const { |
115 | return NumberlikeArray<Blk>::operator ==(x); | |
116 | } | |
117 | bool operator !=(const BigUnsigned &x) const { | |
118 | return NumberlikeArray<Blk>::operator !=(x); | |
119 | } | |
05780f4b MM |
120 | bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; } |
121 | bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; } | |
122 | bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; } | |
123 | bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; } | |
a8b42b68 MM |
124 | |
125 | /* | |
6e1e0f2f MM |
126 | * BigUnsigned and BigInteger both provide three kinds of operators. |
127 | * Here ``big-integer'' refers to BigInteger or BigUnsigned. | |
128 | * | |
129 | * (1) Overloaded ``return-by-value'' operators: | |
3e132790 MM |
130 | * +, -, *, /, %, unary -, &, |, ^, <<, >>. |
131 | * Big-integer code using these operators looks identical to code using | |
132 | * the primitive integer types. These operators take one or two | |
133 | * big-integer inputs and return a big-integer result, which can then | |
134 | * be assigned to a BigInteger variable or used in an expression. | |
135 | * Example: | |
6e1e0f2f MM |
136 | * BigInteger a(1), b = 1; |
137 | * BigInteger c = a + b; | |
138 | * | |
139 | * (2) Overloaded assignment operators: | |
3e132790 MM |
140 | * +=, -=, *=, /=, %=, flipSign, &=, |=, ^=, <<=, >>=, ++, --. |
141 | * Again, these are used on big integers just like on ints. They take | |
142 | * one writable big integer that both provides an operand and receives a | |
143 | * result. Most also take a second read-only operand. | |
144 | * Example: | |
6e1e0f2f MM |
145 | * BigInteger a(1), b(1); |
146 | * a += b; | |
147 | * | |
3e132790 MM |
148 | * (3) Copy-less operations: `add', `subtract', etc. |
149 | * These named methods take operands as arguments and store the result | |
150 | * in the receiver (*this), avoiding unnecessary copies and allocations. | |
151 | * `divideWithRemainder' is special: it both takes the dividend from and | |
152 | * stores the remainder into the receiver, and it takes a separate | |
153 | * object in which to store the quotient. NOTE: If you are wondering | |
154 | * why these don't return a value, you probably mean to use the | |
155 | * overloaded return-by-value operators instead. | |
156 | * | |
6e1e0f2f MM |
157 | * Examples: |
158 | * BigInteger a(43), b(7), c, d; | |
3e132790 | 159 | * |
6e1e0f2f | 160 | * c = a + b; // Now c == 50. |
3e132790 MM |
161 | * c.add(a, b); // Same effect but without the two copies. |
162 | * | |
163 | * c.divideWithRemainder(b, d); | |
164 | * // 50 / 7; now d == 7 (quotient) and c == 1 (remainder). | |
165 | * | |
166 | * // ``Aliased'' calls now do the right thing using a temporary | |
167 | * // copy, but see note on `divideWithRemainder'. | |
168 | * a.add(a, b); | |
6e1e0f2f | 169 | */ |
5ff40cf5 | 170 | |
3e132790 MM |
171 | // COPY-LESS OPERATIONS |
172 | ||
173 | // These 8: Arguments are read-only operands, result is saved in *this. | |
174 | void add(const BigUnsigned &a, const BigUnsigned &b); | |
175 | void subtract(const BigUnsigned &a, const BigUnsigned &b); | |
176 | void multiply(const BigUnsigned &a, const BigUnsigned &b); | |
177 | void bitAnd(const BigUnsigned &a, const BigUnsigned &b); | |
178 | void bitOr(const BigUnsigned &a, const BigUnsigned &b); | |
179 | void bitXor(const BigUnsigned &a, const BigUnsigned &b); | |
0afe80d5 MM |
180 | /* Negative shift amounts translate to opposite-direction shifts, |
181 | * except for -2^(8*sizeof(int)-1) which is unimplemented. */ | |
182 | void bitShiftLeft(const BigUnsigned &a, int b); | |
183 | void bitShiftRight(const BigUnsigned &a, int b); | |
3e132790 MM |
184 | |
185 | /* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'. | |
186 | * / and % use semantics similar to Knuth's, which differ from the | |
187 | * primitive integer semantics under division by zero. See the | |
188 | * implementation in BigUnsigned.cc for details. | |
189 | * `a.divideWithRemainder(b, a)' throws an exception: it doesn't make | |
190 | * sense to write quotient and remainder into the same variable. */ | |
05780f4b | 191 | void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); |
3e132790 MM |
192 | |
193 | /* `divide' and `modulo' are no longer offered. Use | |
194 | * `divideWithRemainder' instead. */ | |
195 | ||
196 | // OVERLOADED RETURN-BY-VALUE OPERATORS | |
197 | BigUnsigned operator +(const BigUnsigned &x) const; | |
198 | BigUnsigned operator -(const BigUnsigned &x) const; | |
199 | BigUnsigned operator *(const BigUnsigned &x) const; | |
200 | BigUnsigned operator /(const BigUnsigned &x) const; | |
201 | BigUnsigned operator %(const BigUnsigned &x) const; | |
202 | /* OK, maybe unary minus could succeed in one case, but it really | |
203 | * shouldn't be used, so it isn't provided. */ | |
204 | BigUnsigned operator &(const BigUnsigned &x) const; | |
205 | BigUnsigned operator |(const BigUnsigned &x) const; | |
206 | BigUnsigned operator ^(const BigUnsigned &x) const; | |
ef2b7c59 MM |
207 | BigUnsigned operator <<(int b) const; |
208 | BigUnsigned operator >>(int b) const; | |
5ff40cf5 | 209 | |
3e132790 MM |
210 | // OVERLOADED ASSIGNMENT OPERATORS |
211 | void operator +=(const BigUnsigned &x); | |
212 | void operator -=(const BigUnsigned &x); | |
213 | void operator *=(const BigUnsigned &x); | |
214 | void operator /=(const BigUnsigned &x); | |
215 | void operator %=(const BigUnsigned &x); | |
216 | void operator &=(const BigUnsigned &x); | |
217 | void operator |=(const BigUnsigned &x); | |
218 | void operator ^=(const BigUnsigned &x); | |
ef2b7c59 MM |
219 | void operator <<=(int b); |
220 | void operator >>=(int b); | |
5ff40cf5 | 221 | |
3e132790 MM |
222 | /* INCREMENT/DECREMENT OPERATORS |
223 | * To discourage messy coding, these do not return *this, so prefix | |
224 | * and postfix behave the same. */ | |
225 | void operator ++( ); | |
226 | void operator ++(int); | |
227 | void operator --( ); | |
228 | void operator --(int); | |
5ff40cf5 | 229 | |
4efbb076 | 230 | // Helper function that needs access to BigUnsigned internals |
3e132790 MM |
231 | friend Blk getShiftedBlock(const BigUnsigned &num, Index x, |
232 | unsigned int y); | |
233 | ||
234 | // See BigInteger.cc. | |
235 | template <class X> | |
236 | friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a); | |
e67d6049 MM |
237 | }; |
238 | ||
3e132790 MM |
239 | /* Implementing the return-by-value and assignment operators in terms of the |
240 | * copy-less operations. The copy-less operations are responsible for making | |
241 | * any necessary temporary copies to work around aliasing. */ | |
242 | ||
e67d6049 MM |
243 | inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { |
244 | BigUnsigned ans; | |
245 | ans.add(*this, x); | |
246 | return ans; | |
247 | } | |
248 | inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const { | |
249 | BigUnsigned ans; | |
250 | ans.subtract(*this, x); | |
251 | return ans; | |
252 | } | |
253 | inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { | |
254 | BigUnsigned ans; | |
255 | ans.multiply(*this, x); | |
256 | return ans; | |
257 | } | |
258 | inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { | |
0afe80d5 | 259 | if (x.isZero()) throw "BigUnsigned::operator /: division by zero"; |
3e132790 MM |
260 | BigUnsigned q, r; |
261 | r = *this; | |
262 | r.divideWithRemainder(x, q); | |
263 | return q; | |
e67d6049 MM |
264 | } |
265 | inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { | |
0afe80d5 | 266 | if (x.isZero()) throw "BigUnsigned::operator %: division by zero"; |
3e132790 MM |
267 | BigUnsigned q, r; |
268 | r = *this; | |
269 | r.divideWithRemainder(x, q); | |
270 | return r; | |
e67d6049 MM |
271 | } |
272 | inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { | |
273 | BigUnsigned ans; | |
274 | ans.bitAnd(*this, x); | |
275 | return ans; | |
276 | } | |
277 | inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const { | |
278 | BigUnsigned ans; | |
279 | ans.bitOr(*this, x); | |
280 | return ans; | |
281 | } | |
282 | inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { | |
283 | BigUnsigned ans; | |
284 | ans.bitXor(*this, x); | |
285 | return ans; | |
286 | } | |
0afe80d5 | 287 | inline BigUnsigned BigUnsigned::operator <<(int b) const { |
ef2b7c59 MM |
288 | BigUnsigned ans; |
289 | ans.bitShiftLeft(*this, b); | |
290 | return ans; | |
291 | } | |
0afe80d5 | 292 | inline BigUnsigned BigUnsigned::operator >>(int b) const { |
ef2b7c59 MM |
293 | BigUnsigned ans; |
294 | ans.bitShiftRight(*this, b); | |
295 | return ans; | |
296 | } | |
e67d6049 | 297 | |
e67d6049 | 298 | inline void BigUnsigned::operator +=(const BigUnsigned &x) { |
8c16728a | 299 | add(*this, x); |
e67d6049 MM |
300 | } |
301 | inline void BigUnsigned::operator -=(const BigUnsigned &x) { | |
8c16728a | 302 | subtract(*this, x); |
e67d6049 MM |
303 | } |
304 | inline void BigUnsigned::operator *=(const BigUnsigned &x) { | |
8c16728a | 305 | multiply(*this, x); |
e67d6049 MM |
306 | } |
307 | inline void BigUnsigned::operator /=(const BigUnsigned &x) { | |
0afe80d5 | 308 | if (x.isZero()) throw "BigUnsigned::operator /=: division by zero"; |
3e132790 MM |
309 | /* The following technique is slightly faster than copying *this first |
310 | * when x is large. */ | |
311 | BigUnsigned q; | |
312 | divideWithRemainder(x, q); | |
313 | // *this contains the remainder, but we overwrite it with the quotient. | |
314 | *this = q; | |
e67d6049 MM |
315 | } |
316 | inline void BigUnsigned::operator %=(const BigUnsigned &x) { | |
0afe80d5 | 317 | if (x.isZero()) throw "BigUnsigned::operator %=: division by zero"; |
05780f4b | 318 | BigUnsigned q; |
3e132790 | 319 | // Mods *this by x. Don't care about quotient left in q. |
05780f4b | 320 | divideWithRemainder(x, q); |
e67d6049 MM |
321 | } |
322 | inline void BigUnsigned::operator &=(const BigUnsigned &x) { | |
8c16728a | 323 | bitAnd(*this, x); |
e67d6049 MM |
324 | } |
325 | inline void BigUnsigned::operator |=(const BigUnsigned &x) { | |
8c16728a | 326 | bitOr(*this, x); |
e67d6049 MM |
327 | } |
328 | inline void BigUnsigned::operator ^=(const BigUnsigned &x) { | |
8c16728a | 329 | bitXor(*this, x); |
e67d6049 | 330 | } |
ef2b7c59 | 331 | inline void BigUnsigned::operator <<=(int b) { |
0afe80d5 | 332 | bitShiftLeft(*this, b); |
ef2b7c59 MM |
333 | } |
334 | inline void BigUnsigned::operator >>=(int b) { | |
0afe80d5 | 335 | bitShiftRight(*this, b); |
ef2b7c59 | 336 | } |
e67d6049 | 337 | |
83a639e6 MM |
338 | /* Templates for conversions of BigUnsigned to and from primitive integers. |
339 | * BigInteger.cc needs to instantiate convertToPrimitive, and the uses in | |
340 | * BigUnsigned.cc didn't do the trick; I think gcc inlined convertToPrimitive | |
341 | * instead of generating linkable instantiations. So for consistency, I put | |
342 | * all the templates here. */ | |
343 | ||
344 | // CONSTRUCTION FROM PRIMITIVE INTEGERS | |
345 | ||
346 | /* Initialize this BigUnsigned from the given primitive integer. The same | |
347 | * pattern works for all primitive integer types, so I put it into a template to | |
348 | * reduce code duplication. (Don't worry: this is protected and we instantiate | |
349 | * it only with primitive integer types.) Type X could be signed, but x is | |
350 | * known to be nonnegative. */ | |
351 | template <class X> | |
352 | void BigUnsigned::initFromPrimitive(X x) { | |
353 | if (x == 0) | |
354 | ; // NumberlikeArray already initialized us to zero. | |
355 | else { | |
356 | // Create a single block. blk is NULL; no need to delete it. | |
357 | cap = 1; | |
358 | blk = new Blk[1]; | |
359 | len = 1; | |
360 | blk[0] = Blk(x); | |
361 | } | |
362 | } | |
363 | ||
364 | /* Ditto, but first check that x is nonnegative. I could have put the check in | |
365 | * initFromPrimitive and let the compiler optimize it out for unsigned-type | |
366 | * instantiations, but I wanted to avoid the warning stupidly issued by g++ for | |
367 | * a condition that is constant in *any* instantiation, even if not in all. */ | |
368 | template <class X> | |
369 | void BigUnsigned::initFromSignedPrimitive(X x) { | |
370 | if (x < 0) | |
371 | throw "BigUnsigned constructor: " | |
372 | "Cannot construct a BigUnsigned from a negative number"; | |
373 | else | |
374 | initFromPrimitive(x); | |
375 | } | |
376 | ||
377 | // CONVERSION TO PRIMITIVE INTEGERS | |
378 | ||
379 | /* Template with the same idea as initFromPrimitive. This might be slightly | |
380 | * slower than the previous version with the masks, but it's much shorter and | |
381 | * clearer, which is the library's stated goal. */ | |
382 | template <class X> | |
383 | X BigUnsigned::convertToPrimitive() const { | |
384 | if (len == 0) | |
385 | // The number is zero; return zero. | |
386 | return 0; | |
387 | else if (len == 1) { | |
388 | // The single block might fit in an X. Try the conversion. | |
389 | X x = X(blk[0]); | |
390 | // Make sure the result accurately represents the block. | |
391 | if (Blk(x) == blk[0]) | |
392 | // Successful conversion. | |
393 | return x; | |
394 | // Otherwise fall through. | |
395 | } | |
396 | throw "BigUnsigned::to<Primitive>: " | |
397 | "Value is too big to fit in the requested type"; | |
398 | } | |
399 | ||
400 | /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, | |
401 | * not a negative one that happened to convert back into the correct nonnegative | |
402 | * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, | |
403 | * separated to avoid a g++ warning. */ | |
404 | template <class X> | |
405 | X BigUnsigned::convertToSignedPrimitive() const { | |
406 | X x = convertToPrimitive<X>(); | |
407 | if (x >= 0) | |
408 | return x; | |
409 | else | |
410 | throw "BigUnsigned::to(Primitive): " | |
411 | "Value is too big to fit in the requested type"; | |
412 | } | |
413 | ||
e67d6049 | 414 | #endif |