2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
10 * A BigUnsigned object represents a nonnegative integer of size
11 * limited only by available memory. A BigUnsigned can be
12 * created from and converted back to most integral types,
13 * and many math operations are defined on them.
15 * The number is stored as a series of blocks in a
16 * dynamically allocated array. It is as if the numbers
17 * were written digit by digit in base 2^32.
24 enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison
25 typedef unsigned long Blk; // The number block type that BigUnsigneds are built from
26 typedef unsigned int BlkNum; // Type for the index of a block in the array
30 BlkNum cap; // The current allocated capacity of this BigUnsigned (in blocks)
31 BlkNum len; // The actual length of the number stored in this BigUnsigned (in blocks)
32 Blk *blk; // Dynamically allocated array of the number blocks
36 BigUnsigned(int, BlkNum c); // Creates a BigUnsigned with a capacity
37 void zapLeadingZeros(); // Decreases len to eliminate leading zeros
38 void allocate(BlkNum c); // Ensures the number array has at least the indicated capacity, maybe discarding contents
39 void allocateAndCopy(BlkNum c); // Ensures the number array has at least the indicated capacity, preserving its contents
41 BigUnsigned(); // Default constructor (value is 0)
42 BigUnsigned(const BigUnsigned &x); // Copy constructor
43 void operator=(const BigUnsigned &x); // Assignment operator
44 BigUnsigned(const Blk *b, BlkNum l); // Constructor from an array of blocks
45 // Constructors from integral types
46 BigUnsigned(unsigned long x);
48 BigUnsigned(unsigned int x);
50 BigUnsigned(unsigned short x);
51 BigUnsigned( short x);
52 ~BigUnsigned(); // Destructor
54 // CONVERTERS to integral types
56 operator unsigned long () const;
57 operator long () const;
58 operator unsigned int () const;
59 operator int () const;
60 operator unsigned short() const;
61 operator short() const;
64 // These accessors can be used to get the pieces of the number
66 BlkNum getCapacity() const;
67 BlkNum getLength() const;
68 Blk getBlock(BlkNum i) const;
69 bool isZero() const; // Often convenient for loops
73 // Compares this to x like Perl's <=>
74 CmpRes compareTo(const BigUnsigned &x) const;
75 // Normal comparison operators
76 bool operator ==(const BigUnsigned &x) const;
77 bool operator !=(const BigUnsigned &x) const;
78 bool operator < (const BigUnsigned &x) const;
79 bool operator <=(const BigUnsigned &x) const;
80 bool operator >=(const BigUnsigned &x) const;
81 bool operator > (const BigUnsigned &x) const;
83 // PUT-HERE OPERATIONS
84 /* These store the result of the operation on the arguments into this.
85 * a.add(b, c) is equivalent to, but faster than, a = b + c.
86 * Calls like a.operation(a, b) are unsafe and not allowed. */
88 void add (const BigUnsigned &a, const BigUnsigned &b); // Addition
89 void subtract (const BigUnsigned &a, const BigUnsigned &b); // Subtraction
90 void multiply (const BigUnsigned &a, const BigUnsigned &b); // Multiplication
91 void divide (const BigUnsigned &a, const BigUnsigned &b); // Division
92 void modulo (const BigUnsigned &a, const BigUnsigned &b); // Modular reduction
93 void bitAnd (const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
94 void bitOr (const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
95 void bitXor (const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
96 void bitShiftLeft (const BigUnsigned &a, unsigned int b); // Bitwise left shift
97 void bitShiftRight(const BigUnsigned &a, const BigUnsigned &b); // Bitwise right shift
100 // These perform the operation on this (to the left of the operator)
101 // and x (to the right of the operator) and return a new BigUnsigned with the result.
103 BigUnsigned operator +(const BigUnsigned &x) const; // Addition
104 BigUnsigned operator -(const BigUnsigned &x) const; // Subtraction
105 BigUnsigned operator *(const BigUnsigned &x) const; // Multiplication
106 BigUnsigned operator /(const BigUnsigned &x) const; // Division
107 BigUnsigned operator %(const BigUnsigned &x) const; // Modular reduction
108 BigUnsigned operator &(const BigUnsigned &x) const; // Bitwise AND
109 BigUnsigned operator |(const BigUnsigned &x) const; // Bitwise OR
110 BigUnsigned operator ^(const BigUnsigned &x) const; // Bitwise XOR
112 // ASSIGNMENT OPERATORS
113 // These perform the operation on this and x, storing the result into this.
115 void operator +=(const BigUnsigned &x); // Addition
116 void operator -=(const BigUnsigned &x); // Subtraction
117 void operator *=(const BigUnsigned &x); // Multiplication
118 void operator /=(const BigUnsigned &x); // Division
119 void operator %=(const BigUnsigned &x); // Modular reduction
120 void operator &=(const BigUnsigned &x); // Bitwise AND
121 void operator |=(const BigUnsigned &x); // Bitwise OR
122 void operator ^=(const BigUnsigned &x); // Bitwise XOR
124 // INCREMENT/DECREMENT OPERATORS
125 // These increase or decrease the number by 1. To discourage side effects,
126 // these do not return *this, so prefix and postfix behave the same.
128 void operator ++( ); // Prefix increment
129 void operator ++(int); // Postfix decrement
130 void operator --( ); // Prefix increment
131 void operator --(int); // Postfix decrement
137 inline BigUnsigned::BigUnsigned(int, BlkNum c) : cap(c), len(0) {
141 inline void BigUnsigned::zapLeadingZeros() {
142 for (Blk *blkLenM1 = blk + len - 1; len > 0 && *blkLenM1 == 0; len--, blkLenM1--)
146 inline BigUnsigned::BigUnsigned() : cap(0), len(0) {
150 inline BigUnsigned::~BigUnsigned() {
155 inline BigUnsigned::BlkNum BigUnsigned::getCapacity() const { return cap; }
156 inline BigUnsigned::BlkNum BigUnsigned::getLength() const { return len; }
157 // Note that getBlock returns 0 if the block index is beyond the length of the number.
158 // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left.
159 inline BigUnsigned::Blk BigUnsigned::getBlock(BlkNum i) const { return i >= len ? 0 : blk[i]; }
160 inline bool BigUnsigned::isZero() const { return len == 0; }
163 inline bool BigUnsigned::operator==(const BigUnsigned &x) const { return compareTo(x) == equal ; }
164 inline bool BigUnsigned::operator!=(const BigUnsigned &x) const { return compareTo(x) != equal ; }
165 inline bool BigUnsigned::operator< (const BigUnsigned &x) const { return compareTo(x) == less ; }
166 inline bool BigUnsigned::operator<=(const BigUnsigned &x) const { return compareTo(x) != greater; }
167 inline bool BigUnsigned::operator>=(const BigUnsigned &x) const { return compareTo(x) != less ; }
168 inline bool BigUnsigned::operator> (const BigUnsigned &x) const { return compareTo(x) == greater; }
171 /* These create an object to hold the result and invoke
172 * the appropriate put-here operation on it, passing
173 * this and x. The new object is then returned. */
174 inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const {
179 inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const {
181 ans.subtract(*this, x);
184 inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const {
186 ans.multiply(*this, x);
189 inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const {
191 ans.divide(*this, x);
194 inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const {
196 ans.modulo(*this, x);
199 inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const {
201 ans.bitAnd(*this, x);
204 inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const {
209 inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const {
211 ans.bitXor(*this, x);
215 // ASSIGNMENT OPERATORS
216 // These create a copy of this, then invoke the appropriate
217 // put-here operation on this, passing the copy and x.
218 inline void BigUnsigned::operator +=(const BigUnsigned &x) {
219 BigUnsigned thisCopy(*this);
222 inline void BigUnsigned::operator -=(const BigUnsigned &x) {
223 BigUnsigned thisCopy(*this);
224 subtract(thisCopy, x);
226 inline void BigUnsigned::operator *=(const BigUnsigned &x) {
227 BigUnsigned thisCopy(*this);
228 multiply(thisCopy, x);
230 inline void BigUnsigned::operator /=(const BigUnsigned &x) {
231 BigUnsigned thisCopy(*this);
234 inline void BigUnsigned::operator %=(const BigUnsigned &x) {
235 BigUnsigned thisCopy(*this);
238 inline void BigUnsigned::operator &=(const BigUnsigned &x) {
239 BigUnsigned thisCopy(*this);
242 inline void BigUnsigned::operator |=(const BigUnsigned &x) {
243 BigUnsigned thisCopy(*this);
246 inline void BigUnsigned::operator ^=(const BigUnsigned &x) {
247 BigUnsigned thisCopy(*this);