4 #include "NumberlikeArray.hh"
7 * A BigUnsigned object represents a nonnegative integer of size
8 * limited only by available memory. A BigUnsigned can be
9 * created from and converted back to most integral types,
10 * and many math operations are defined on BigUnsigneds.
12 * The number is stored as a series of blocks in a
13 * dynamically allocated array. It is as if the number
14 * were written digit by digit in base 2 ^ N, **where N is the
15 * number of bits in an unsigned long.**
17 * The memory-management details that used to be in here have
18 * been moved into NumberlikeArray, which BigUnsigned now derives from.
19 * `(NlA)' means that member(s) are declared identically in NumberlikeArray.
20 * Such members are either redeclared here to make them public or are
21 * here, commented out, for reference.
24 class BigUnsigned : protected NumberlikeArray<unsigned long> {
28 enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison
29 typedef unsigned long Blk; // The number block type that BigUnsigneds are built from
30 typedef NumberlikeArray<Blk>::Index Index; // (NlA) Type for the index of a block in the array
31 NumberlikeArray<Blk>::N; // Number of bits in a Blk
36 Index cap; // (NlA) The current allocated capacity of this BigUnsigned (in blocks)
37 Index len; // (NlA) The actual length of the number stored in this BigUnsigned (in blocks)
38 Blk *blk; // (NlA) Dynamically allocated array of the number blocks
43 // These members generally defer to those in NumberlikeArray, possibly with slight changes.
44 // It might be nice if one could request that constructors be inherited in C++.
46 BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} // Creates a BigUnsigned with a capacity
48 void zapLeadingZeros() { // Decreases len to eliminate leading zeros
49 while (len > 0 && blk[len - 1] == 0)
53 //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
54 //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents
57 BigUnsigned() : NumberlikeArray<Blk>() {} // Default constructor (value is 0)
58 BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {} // Copy constructor
60 void operator=(const BigUnsigned &x) { // Assignment operator
61 NumberlikeArray<Blk>::operator =(x);
64 BigUnsigned(const Blk *b, Index l) : NumberlikeArray<Blk>(b, l) { // Constructor from an array of blocks
68 // Constructors from integral types
69 BigUnsigned(unsigned long x);
71 BigUnsigned(unsigned int x);
73 BigUnsigned(unsigned short x);
74 BigUnsigned( short x);
75 ~BigUnsigned() {} // Destructor
77 // CONVERTERS to integral types
79 operator unsigned long () const;
80 operator long () const;
81 operator unsigned int () const;
82 operator int () const;
83 operator unsigned short() const;
84 operator short() const;
87 // These accessors can be used to get the pieces of the number
89 NumberlikeArray<Blk>::getCapacity;
90 NumberlikeArray<Blk>::getLength;
91 // Note that getBlock returns 0 if the block index is beyond the length of the number.
92 // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left.
93 Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; }
94 // Note how we replace one level of abstraction with another. Isn't that neat?
95 bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } // Often convenient for loops
99 // Compares this to x like Perl's <=>
100 CmpRes compareTo(const BigUnsigned &x) const;
101 // Normal comparison operators
102 // Bug fixed 2006.04.24: Only we, not the user, can pass a BigUnsigned off as a
103 // NumberlikeArray, so we have to wrap == and !=.
104 bool operator ==(const BigUnsigned &x) const {
105 return NumberlikeArray<Blk>::operator ==(x);
107 bool operator !=(const BigUnsigned &x) const {
108 return NumberlikeArray<Blk>::operator !=(x);
110 bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; }
111 bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; }
112 bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; }
113 bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; }
116 * BigUnsigned and BigInteger both provide three kinds of operators.
117 * Here ``big-integer'' refers to BigInteger or BigUnsigned.
119 * (1) Overloaded ``return-by-value'' operators:
120 * +, -, *, /, %, unary -.
121 * Big-integer code using these operators looks identical to
122 * code using the primitive integer types. These operators take
123 * one or two big-integer inputs and return a big-integer result,
124 * which can then be assigned to a BigInteger variable or used
125 * in an expression. Example:
126 * BigInteger a(1), b = 1;
127 * BigInteger c = a + b;
129 * (2) Overloaded assignment operators:
130 * +=, -=, *=, /=, %=, &=, |=, ^=, ++, --, flipSign.
131 * Again, these are used on big integers just like on ints.
132 * They take one writable big integer that both provides an
133 * operand and receives a result. The first eight also take
134 * a second read-only operand. Example:
135 * BigInteger a(1), b(1);
138 * (3) ``Put-here'' operations: `add', `subtract', etc.
139 * Using a return-by-value or assignment operator generally involves
140 * copy constructions and/or assignments. The ``put-here'' operations
141 * require none, but they are more of a hassle to use. Most take two
142 * read-only operands and save the result in the calling object `*this',
143 * whose previous value is ignored. `divideWithRemainder' is an exception.
144 * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
146 * BigInteger a(43), b(7), c, d;
147 * c = a + b; // Now c == 50.
148 * c.add(a, b); // Same effect but without the two bulk-copies.
149 * c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
150 * a.add(a, b); // ``Aliased'' calls now do the right thing using a
151 * // temporary copy, but see note on divideWithRemainder.
154 // PUT-HERE OPERATIONS
156 /* These 3: Two read-only operands as arguments. Result left in *this. */
157 void add(const BigUnsigned &a, const BigUnsigned &b); // Addition
158 void subtract(const BigUnsigned &a, const BigUnsigned &b); // Subtraction
159 void multiply(const BigUnsigned &a, const BigUnsigned &b); // Multiplication
161 * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
162 * Semantics similar to Donald E. Knuth's are used for / and %,
163 * and these differ from the semantics of primitive-type
164 * / and % under division by zero.
165 * Look in `BigUnsigned.cc' for details.
166 * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
167 * sense to write quotient and remainder into the same variable.
169 void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
170 void divide(const BigUnsigned &a, const BigUnsigned &b) {
172 a2.divideWithRemainder(b, *this);
173 // quotient now in *this
174 // don't care about remainder left in a2
176 void modulo(const BigUnsigned &a, const BigUnsigned &b) {
179 divideWithRemainder(b, q);
180 // remainder now in *this
181 // don't care about quotient left in q
183 // Bitwise operations. Result left in *this.
184 // These are not provided for BigIntegers; I think that using them on BigIntegers
185 // will discard the sign first.
186 void bitAnd(const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
187 void bitOr(const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
188 void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
189 void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
190 void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
193 // These perform the operation on this (to the left of the operator)
194 // and x (to the right of the operator) and return a new BigUnsigned with the result.
196 BigUnsigned operator +(const BigUnsigned &x) const; // Addition
197 BigUnsigned operator -(const BigUnsigned &x) const; // Subtraction
198 BigUnsigned operator *(const BigUnsigned &x) const; // Multiplication
199 BigUnsigned operator /(const BigUnsigned &x) const; // Division
200 BigUnsigned operator %(const BigUnsigned &x) const; // Modular reduction
201 BigUnsigned operator &(const BigUnsigned &x) const; // Bitwise AND
202 BigUnsigned operator |(const BigUnsigned &x) const; // Bitwise OR
203 BigUnsigned operator ^(const BigUnsigned &x) const; // Bitwise XOR
204 BigUnsigned operator <<(unsigned int b) const; // Bitwise left shift
205 BigUnsigned operator >>(unsigned int b) const; // Bitwise right shift
206 // Additional operators in an attempt to avoid overloading tangles.
207 BigUnsigned operator <<(int b) const;
208 BigUnsigned operator >>(int b) const;
210 // ASSIGNMENT OPERATORS
211 // These perform the operation on this and x, storing the result into this.
213 void operator +=(const BigUnsigned &x); // Addition
214 void operator -=(const BigUnsigned &x); // Subtraction
215 void operator *=(const BigUnsigned &x); // Multiplication
216 void operator /=(const BigUnsigned &x); // Division
217 void operator %=(const BigUnsigned &x); // Modular reduction
218 void operator &=(const BigUnsigned &x); // Bitwise AND
219 void operator |=(const BigUnsigned &x); // Bitwise OR
220 void operator ^=(const BigUnsigned &x); // Bitwise XOR
221 void operator <<=(unsigned int b); // Bitwise left shift
222 void operator >>=(unsigned int b); // Bitwise right shift
223 // Additional operators in an attempt to avoid overloading tangles.
224 void operator <<=(int b);
225 void operator >>=(int b);
227 // INCREMENT/DECREMENT OPERATORS
228 // These increase or decrease the number by 1. To discourage side effects,
229 // these do not return *this, so prefix and postfix behave the same.
231 void operator ++( ); // Prefix increment
232 void operator ++(int); // Postfix decrement
233 void operator --( ); // Prefix increment
234 void operator --(int); // Postfix decrement
236 // Helper function that needs access to BigUnsigned internals
237 friend Blk getShiftedBlock(const BigUnsigned &num, Index x, unsigned int y);
241 /* These create an object to hold the result and invoke
242 * the appropriate put-here operation on it, passing
243 * this and x. The new object is then returned. */
244 inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const {
249 inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const {
251 ans.subtract(*this, x);
254 inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const {
256 ans.multiply(*this, x);
259 inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const {
261 ans.divide(*this, x);
264 inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const {
266 ans.modulo(*this, x);
269 inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const {
271 ans.bitAnd(*this, x);
274 inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const {
279 inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const {
281 ans.bitXor(*this, x);
284 inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const {
286 ans.bitShiftLeft(*this, b);
289 inline BigUnsigned BigUnsigned::operator >>(unsigned int b) const {
291 ans.bitShiftRight(*this, b);
294 inline BigUnsigned BigUnsigned::operator <<(int b) const {
296 throw "BigUnsigned::operator <<(int): Negative shift amounts are not supported";
297 return *this << (unsigned int)(b);
299 inline BigUnsigned BigUnsigned::operator >>(int b) const {
301 throw "BigUnsigned::operator >>(int): Negative shift amounts are not supported";
302 return *this >> (unsigned int)(b);
306 * ASSIGNMENT OPERATORS
308 * Now the responsibility for making a temporary copy if necessary
309 * belongs to the put-here operations. I made this change on 2007.02.13 after
310 * Boris Dessy pointed out that the old implementation handled calls like
311 * "a *= a" badly: it translated them to essentially "a.multiply(aCopy, a)",
312 * which threw an exception.
314 inline void BigUnsigned::operator +=(const BigUnsigned &x) {
317 inline void BigUnsigned::operator -=(const BigUnsigned &x) {
320 inline void BigUnsigned::operator *=(const BigUnsigned &x) {
323 inline void BigUnsigned::operator /=(const BigUnsigned &x) {
324 // Updated for divideWithRemainder
325 BigUnsigned thisCopy(*this);
326 thisCopy.divideWithRemainder(x, *this);
327 // quotient left in *this
328 // don't care about remainder left in thisCopy
330 inline void BigUnsigned::operator %=(const BigUnsigned &x) {
331 // Shortcut (woohoo!)
333 divideWithRemainder(x, q);
334 // remainder left in *this
335 // don't care about quotient left in q
337 inline void BigUnsigned::operator &=(const BigUnsigned &x) {
340 inline void BigUnsigned::operator |=(const BigUnsigned &x) {
343 inline void BigUnsigned::operator ^=(const BigUnsigned &x) {
346 inline void BigUnsigned::operator <<=(unsigned int b) {
347 bitShiftLeft(*this, b);
349 inline void BigUnsigned::operator >>=(unsigned int b) {
350 bitShiftRight(*this, b);
352 inline void BigUnsigned::operator <<=(int b) {
354 throw "BigUnsigned::operator <<=(int): Negative shift amounts are not supported";
355 *this <<= (unsigned int)(b);
357 inline void BigUnsigned::operator >>=(int b) {
359 throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported";
360 *this >>= (unsigned int)(b);