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); | |
0afe80d5 MM |
169 | /* Negative shift amounts translate to opposite-direction shifts, |
170 | * except for -2^(8*sizeof(int)-1) which is unimplemented. */ | |
171 | void bitShiftLeft(const BigUnsigned &a, int b); | |
172 | void bitShiftRight(const BigUnsigned &a, int b); | |
3e132790 MM |
173 | |
174 | /* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'. | |
175 | * / and % use semantics similar to Knuth's, which differ from the | |
176 | * primitive integer semantics under division by zero. See the | |
177 | * implementation in BigUnsigned.cc for details. | |
178 | * `a.divideWithRemainder(b, a)' throws an exception: it doesn't make | |
179 | * sense to write quotient and remainder into the same variable. */ | |
05780f4b | 180 | void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); |
3e132790 MM |
181 | |
182 | /* `divide' and `modulo' are no longer offered. Use | |
183 | * `divideWithRemainder' instead. */ | |
184 | ||
185 | // OVERLOADED RETURN-BY-VALUE OPERATORS | |
186 | BigUnsigned operator +(const BigUnsigned &x) const; | |
187 | BigUnsigned operator -(const BigUnsigned &x) const; | |
188 | BigUnsigned operator *(const BigUnsigned &x) const; | |
189 | BigUnsigned operator /(const BigUnsigned &x) const; | |
190 | BigUnsigned operator %(const BigUnsigned &x) const; | |
191 | /* OK, maybe unary minus could succeed in one case, but it really | |
192 | * shouldn't be used, so it isn't provided. */ | |
193 | BigUnsigned operator &(const BigUnsigned &x) const; | |
194 | BigUnsigned operator |(const BigUnsigned &x) const; | |
195 | BigUnsigned operator ^(const BigUnsigned &x) const; | |
ef2b7c59 MM |
196 | BigUnsigned operator <<(int b) const; |
197 | BigUnsigned operator >>(int b) const; | |
5ff40cf5 | 198 | |
3e132790 MM |
199 | // OVERLOADED ASSIGNMENT OPERATORS |
200 | void operator +=(const BigUnsigned &x); | |
201 | void operator -=(const BigUnsigned &x); | |
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); | |
ef2b7c59 MM |
208 | void operator <<=(int b); |
209 | void operator >>=(int b); | |
5ff40cf5 | 210 | |
3e132790 MM |
211 | /* INCREMENT/DECREMENT OPERATORS |
212 | * To discourage messy coding, these do not return *this, so prefix | |
213 | * and postfix behave the same. */ | |
214 | void operator ++( ); | |
215 | void operator ++(int); | |
216 | void operator --( ); | |
217 | void operator --(int); | |
5ff40cf5 | 218 | |
4efbb076 | 219 | // Helper function that needs access to BigUnsigned internals |
3e132790 MM |
220 | friend Blk getShiftedBlock(const BigUnsigned &num, Index x, |
221 | unsigned int y); | |
222 | ||
223 | // See BigInteger.cc. | |
224 | template <class X> | |
225 | friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a); | |
e67d6049 MM |
226 | }; |
227 | ||
3e132790 MM |
228 | /* Implementing the return-by-value and assignment operators in terms of the |
229 | * copy-less operations. The copy-less operations are responsible for making | |
230 | * any necessary temporary copies to work around aliasing. */ | |
231 | ||
e67d6049 MM |
232 | inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { |
233 | BigUnsigned ans; | |
234 | ans.add(*this, x); | |
235 | return ans; | |
236 | } | |
237 | inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const { | |
238 | BigUnsigned ans; | |
239 | ans.subtract(*this, x); | |
240 | return ans; | |
241 | } | |
242 | inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { | |
243 | BigUnsigned ans; | |
244 | ans.multiply(*this, x); | |
245 | return ans; | |
246 | } | |
247 | inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { | |
0afe80d5 | 248 | if (x.isZero()) throw "BigUnsigned::operator /: division by zero"; |
3e132790 MM |
249 | BigUnsigned q, r; |
250 | r = *this; | |
251 | r.divideWithRemainder(x, q); | |
252 | return q; | |
e67d6049 MM |
253 | } |
254 | inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { | |
0afe80d5 | 255 | if (x.isZero()) throw "BigUnsigned::operator %: division by zero"; |
3e132790 MM |
256 | BigUnsigned q, r; |
257 | r = *this; | |
258 | r.divideWithRemainder(x, q); | |
259 | return r; | |
e67d6049 MM |
260 | } |
261 | inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { | |
262 | BigUnsigned ans; | |
263 | ans.bitAnd(*this, x); | |
264 | return ans; | |
265 | } | |
266 | inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const { | |
267 | BigUnsigned ans; | |
268 | ans.bitOr(*this, x); | |
269 | return ans; | |
270 | } | |
271 | inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { | |
272 | BigUnsigned ans; | |
273 | ans.bitXor(*this, x); | |
274 | return ans; | |
275 | } | |
0afe80d5 | 276 | inline BigUnsigned BigUnsigned::operator <<(int b) const { |
ef2b7c59 MM |
277 | BigUnsigned ans; |
278 | ans.bitShiftLeft(*this, b); | |
279 | return ans; | |
280 | } | |
0afe80d5 | 281 | inline BigUnsigned BigUnsigned::operator >>(int b) const { |
ef2b7c59 MM |
282 | BigUnsigned ans; |
283 | ans.bitShiftRight(*this, b); | |
284 | return ans; | |
285 | } | |
e67d6049 | 286 | |
e67d6049 | 287 | inline void BigUnsigned::operator +=(const BigUnsigned &x) { |
8c16728a | 288 | add(*this, x); |
e67d6049 MM |
289 | } |
290 | inline void BigUnsigned::operator -=(const BigUnsigned &x) { | |
8c16728a | 291 | subtract(*this, x); |
e67d6049 MM |
292 | } |
293 | inline void BigUnsigned::operator *=(const BigUnsigned &x) { | |
8c16728a | 294 | multiply(*this, x); |
e67d6049 MM |
295 | } |
296 | inline void BigUnsigned::operator /=(const BigUnsigned &x) { | |
0afe80d5 | 297 | if (x.isZero()) throw "BigUnsigned::operator /=: division by zero"; |
3e132790 MM |
298 | /* The following technique is slightly faster than copying *this first |
299 | * when x is large. */ | |
300 | BigUnsigned q; | |
301 | divideWithRemainder(x, q); | |
302 | // *this contains the remainder, but we overwrite it with the quotient. | |
303 | *this = q; | |
e67d6049 MM |
304 | } |
305 | inline void BigUnsigned::operator %=(const BigUnsigned &x) { | |
0afe80d5 | 306 | if (x.isZero()) throw "BigUnsigned::operator %=: division by zero"; |
05780f4b | 307 | BigUnsigned q; |
3e132790 | 308 | // Mods *this by x. Don't care about quotient left in q. |
05780f4b | 309 | divideWithRemainder(x, q); |
e67d6049 MM |
310 | } |
311 | inline void BigUnsigned::operator &=(const BigUnsigned &x) { | |
8c16728a | 312 | bitAnd(*this, x); |
e67d6049 MM |
313 | } |
314 | inline void BigUnsigned::operator |=(const BigUnsigned &x) { | |
8c16728a | 315 | bitOr(*this, x); |
e67d6049 MM |
316 | } |
317 | inline void BigUnsigned::operator ^=(const BigUnsigned &x) { | |
8c16728a | 318 | bitXor(*this, x); |
e67d6049 | 319 | } |
ef2b7c59 | 320 | inline void BigUnsigned::operator <<=(int b) { |
0afe80d5 | 321 | bitShiftLeft(*this, b); |
ef2b7c59 MM |
322 | } |
323 | inline void BigUnsigned::operator >>=(int b) { | |
0afe80d5 | 324 | bitShiftRight(*this, b); |
ef2b7c59 | 325 | } |
e67d6049 MM |
326 | |
327 | #endif |