2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
9 #include "BigUnsigned.hh"
12 * A BigInteger object represents a signed integer of size
13 * limited only by available memory. A BigInteger can be
14 * created from and converted back to most integral types,
15 * and many math operations are defined on BigIntegers.
17 * The number is stored as a series of blocks in a
18 * dynamically allocated array. It is as if the numbers
19 * were written digit by digit in base 256 ^ sizeof(unsigned long).
21 * This class is derived from BigUnsigned, which represents
22 * a large nonnegative integer. BigUnsigned should be studied
23 * first, as only new or different things are declared here.
24 * Some things are redeclared so that they use the BigInteger
25 * versions of methods, rather than the BigUnsigned versions.
28 class BigInteger : public BigUnsigned {
32 enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger
36 Sign sign; // The sign of this BigInteger
40 BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
43 BigInteger() : BigUnsigned(), sign(zero) {} // Default constructor (value is 0)
44 BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) {}; // Copy constructor
45 void operator=(const BigInteger &x); // Assignment operator
46 BigInteger(const Blk *b, Index l) : BigUnsigned(b, l) { // Constructor from an array of blocks
47 sign = (len == 0) ? zero : positive;
49 BigInteger(const Blk *b, Index l, Sign s); // Constructor from an array of blocks and a sign
50 BigInteger(const BigUnsigned &x) : BigUnsigned(x) { // Constructor from a BigUnsigned
51 sign = (len == 0) ? zero : positive;
53 BigInteger(const BigUnsigned &x, Sign s); // Constructor from a BigUnsigned and a sign
54 // Constructors from integral types
55 BigInteger(unsigned long x);
57 BigInteger(unsigned int x);
59 BigInteger(unsigned short x);
61 // Note that a BigInteger can be converted to a BigUnsigned
62 // automatically; this takes its absolute value.
64 // CONVERTERS to integral types
66 operator unsigned long () const;
67 operator long () const;
68 operator unsigned int () const;
69 operator int () const;
70 operator unsigned short() const;
71 operator short() const;
74 // These accessors can be used to get the pieces of the number
80 // Compares this to x like Perl's <=>
81 CmpRes compareTo(const BigInteger &x) const;
82 // Normal comparison operators
83 bool operator ==(const BigInteger &x) const {
84 return sign == x.sign && BigUnsigned::operator ==(x);
86 bool operator !=(const BigInteger &x) const { return !operator ==(x); };
87 bool operator < (const BigInteger &x) const { return compareTo(x) == less ; }
88 bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
89 bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; }
90 bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
92 // PUT-HERE OPERATIONS
93 /* These store the result of the operation on the arguments into this.
94 * a.add(b, c) is equivalent to, but faster than, a = b + c.
95 * Calls like a.operation(a, b) are unsafe and not allowed. */
97 void add (const BigInteger &a, const BigInteger &b); // Addition
98 void subtract(const BigInteger &a, const BigInteger &b); // Subtraction
99 void multiply(const BigInteger &a, const BigInteger &b); // Multiplication
101 * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
102 * Semantics similar to Donald E. Knuth's are used for / and %,
103 * and these usually differ from the semantics of primitive-type
104 * / and % when negatives and/or zeroes are involved.
105 * Look in `BigInteger.cc' for details.
107 void divideWithRemainder(const BigInteger &b, BigInteger &q);
108 void divide(const BigInteger &a, const BigInteger &b) {
109 // Division, deprecated and provided for compatibility
111 a2.divideWithRemainder(b, *this);
112 // quotient now in *this
113 // don't care about remainder left in a2
115 void modulo(const BigInteger &a, const BigInteger &b) {
116 // Modular reduction, deprecated and provided for compatibility
119 divideWithRemainder(b, q);
120 // remainder now in *this
121 // don't care about quotient left in q
123 void negate(const BigInteger &a); // Negative
124 // Some operations are inherently unsigned and are not
125 // redefined for BigIntegers. Calling one of these on
126 // a BigInteger will convert it to a BigUnsigned,
127 // which takes its absolute value.
130 // These perform the operation on this (to the left of the operator)
131 // and x (to the right of the operator) and return a new BigInteger with the result.
133 BigInteger operator +(const BigInteger &x) const; // Addition
134 BigInteger operator -(const BigInteger &x) const; // Subtraction
135 BigInteger operator *(const BigInteger &x) const; // Multiplication
136 BigInteger operator /(const BigInteger &x) const; // Division
137 BigInteger operator %(const BigInteger &x) const; // Modular reduction
138 BigInteger operator -( ) const; // Negative
140 // ASSIGNMENT OPERATORS
141 // These perform the operation on this and x, storing the result into this.
143 void operator +=(const BigInteger &x); // Addition
144 void operator -=(const BigInteger &x); // Subtraction
145 void operator *=(const BigInteger &x); // Multiplication
146 void operator /=(const BigInteger &x); // Division
147 void operator %=(const BigInteger &x); // Modular reduction
148 void flipSign(); // Negative
150 // INCREMENT/DECREMENT OPERATORS
151 // These increase or decrease the number by 1. To discourage side effects,
152 // these do not return *this, so prefix and postfix behave the same.
154 void operator ++( ); // Prefix increment
155 void operator ++(int); // Postfix decrement
156 void operator --( ); // Prefix increment
157 void operator --(int); // Postfix decrement
162 inline BigInteger::Sign BigInteger::getSign() const { return sign; }
165 /* These create an object to hold the result and invoke
166 * the appropriate put-here operation on it, passing
167 * this and x. The new object is then returned. */
168 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
173 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
175 ans.subtract(*this, x);
178 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
180 ans.multiply(*this, x);
183 inline BigInteger BigInteger::operator /(const BigInteger &x) const {
185 ans.divide(*this, x);
188 inline BigInteger BigInteger::operator %(const BigInteger &x) const {
190 ans.modulo(*this, x);
193 inline BigInteger BigInteger::operator -() const {
199 // ASSIGNMENT OPERATORS
200 // These create a copy of this, then invoke the appropriate
201 // put-here operation on this, passing the copy and x.
202 inline void BigInteger::operator +=(const BigInteger &x) {
203 BigInteger thisCopy(*this);
206 inline void BigInteger::operator -=(const BigInteger &x) {
207 BigInteger thisCopy(*this);
208 subtract(thisCopy, x);
210 inline void BigInteger::operator *=(const BigInteger &x) {
211 BigInteger thisCopy(*this);
212 multiply(thisCopy, x);
214 inline void BigInteger::operator /=(const BigInteger &x) {
215 // Updated for divideWithRemainder
216 BigInteger thisCopy(*this);
217 thisCopy.divideWithRemainder(x, *this);
218 // quotient left in *this
219 // don't care about remainder left in thisCopy
221 inline void BigInteger::operator %=(const BigInteger &x) {
222 // Shortcut (woohoo!)
224 divideWithRemainder(x, q);
225 // remainder left in *this
226 // don't care about quotient left in q
228 // This one is trivial
229 inline void BigInteger::flipSign() {