1 #ifndef BIGINTEGER_H
2 #define BIGINTEGER_H
3
4 #include "BigUnsigned.hh"
5
6 /* A BigInteger object represents a signed 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.
9 *
10 * A BigInteger is just an aggregate of a BigUnsigned and a sign. (It is no
11 * longer derived from BigUnsigned because that led to harmful implicit
12 * conversions.) */
13 class BigInteger {
14
15 public:
16 typedef BigUnsigned::Blk Blk;
17 typedef BigUnsigned::Index Index;
18 typedef BigUnsigned::CmpRes CmpRes;
19 static const CmpRes
20 less = BigUnsigned::less ,
21 equal = BigUnsigned::equal ,
22 greater = BigUnsigned::greater;
23 // Enumeration for the sign of a BigInteger.
24 enum Sign { negative = -1, zero = 0, positive = 1 };
25
26 protected:
27 Sign sign;
28 BigUnsigned mag;
29
30 public:
31 // Constructs zero.
BigInteger()32 BigInteger() : sign(zero), mag() {}
33
34 // Copy constructor
BigInteger(const BigInteger & x)35 BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
36
37 // Assignment operator
38 void operator=(const BigInteger &x);
39
40 // Constructor that copies from a given array of blocks with a sign.
41 BigInteger(const Blk *b, Index blen, Sign s);
42
43 // Nonnegative constructor that copies from a given array of blocks.
BigInteger(const Blk * b,Index blen)44 BigInteger(const Blk *b, Index blen) : mag(b, blen) {
45 sign = mag.isZero() ? zero : positive;
46 }
47
48 // Constructor from a BigUnsigned and a sign
49 BigInteger(const BigUnsigned &x, Sign s);
50
51 // Nonnegative constructor from a BigUnsigned
BigInteger(const BigUnsigned & x)52 BigInteger(const BigUnsigned &x) : mag(x) {
53 sign = mag.isZero() ? zero : positive;
54 }
55
56 // Constructors from primitive integer types
57 BigInteger(unsigned long x);
58 BigInteger( long x);
59 BigInteger(unsigned int x);
60 BigInteger( int x);
61 BigInteger(unsigned short x);
62 BigInteger( short x);
63
64 /* Converters to primitive integer types
65 * The implicit conversion operators caused trouble, so these are now
66 * named. */
67 unsigned long toUnsignedLong () const;
68 long toLong () const;
69 unsigned int toUnsignedInt () const;
70 int toInt () const;
71 unsigned short toUnsignedShort() const;
72 short toShort () const;
73 protected:
74 // Helper
75 template <class X> X convertToUnsignedPrimitive() const;
76 template <class X, class UX> X convertToSignedPrimitive() const;
77 public:
78
79 // ACCESSORS
getSign() const80 Sign getSign() const { return sign; }
81 /* The client can't do any harm by holding a read-only reference to the
82 * magnitude. */
getMagnitude() const83 const BigUnsigned &getMagnitude() const { return mag; }
84
85 // Some accessors that go through to the magnitude
getLength() const86 Index getLength() const { return mag.getLength(); }
getCapacity() const87 Index getCapacity() const { return mag.getCapacity(); }
getBlock(Index i) const88 Blk getBlock(Index i) const { return mag.getBlock(i); }
isZero() const89 bool isZero() const { return sign == zero; } // A bit special
90
91 // COMPARISONS
92
93 // Compares this to x like Perl's <=>
94 CmpRes compareTo(const BigInteger &x) const;
95
96 // Ordinary comparison operators
operator ==(const BigInteger & x) const97 bool operator ==(const BigInteger &x) const {
98 return sign == x.sign && mag == x.mag;
99 }
operator !=(const BigInteger & x) const100 bool operator !=(const BigInteger &x) const { return !operator ==(x); };
operator <(const BigInteger & x) const101 bool operator < (const BigInteger &x) const { return compareTo(x) == less ; }
operator <=(const BigInteger & x) const102 bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
operator >=(const BigInteger & x) const103 bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; }
operator >(const BigInteger & x) const104 bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
105
106 // OPERATORS -- See the discussion in BigUnsigned.hh.
107 void add (const BigInteger &a, const BigInteger &b);
108 void subtract(const BigInteger &a, const BigInteger &b);
109 void multiply(const BigInteger &a, const BigInteger &b);
110 /* See the comment on BigUnsigned::divideWithRemainder. Semantics
111 * differ from those of primitive integers when negatives and/or zeros
112 * are involved. */
113 void divideWithRemainder(const BigInteger &b, BigInteger &q);
114 void negate(const BigInteger &a);
115
116 /* Bitwise operators are not provided for BigIntegers. Use
117 * getMagnitude to get the magnitude and operate on that instead. */
118
119 BigInteger operator +(const BigInteger &x) const;
120 BigInteger operator -(const BigInteger &x) const;
121 BigInteger operator *(const BigInteger &x) const;
122 BigInteger operator /(const BigInteger &x) const;
123 BigInteger operator %(const BigInteger &x) const;
124 BigInteger operator -() const;
125
126 void operator +=(const BigInteger &x);
127 void operator -=(const BigInteger &x);
128 void operator *=(const BigInteger &x);
129 void operator /=(const BigInteger &x);
130 void operator %=(const BigInteger &x);
131 void flipSign();
132
133 // INCREMENT/DECREMENT OPERATORS
134 void operator ++( );
135 void operator ++(int);
136 void operator --( );
137 void operator --(int);
138 };
139
140 // NORMAL OPERATORS
141 /* These create an object to hold the result and invoke
142 * the appropriate put-here operation on it, passing
143 * this and x. The new object is then returned. */
operator +(const BigInteger & x) const144 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
145 BigInteger ans;
146 ans.add(*this, x);
147 return ans;
148 }
operator -(const BigInteger & x) const149 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
150 BigInteger ans;
151 ans.subtract(*this, x);
152 return ans;
153 }
operator *(const BigInteger & x) const154 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
155 BigInteger ans;
156 ans.multiply(*this, x);
157 return ans;
158 }
operator /(const BigInteger & x) const159 inline BigInteger BigInteger::operator /(const BigInteger &x) const {
160 if (x.isZero()) throw "BigInteger::operator /: division by zero";
161 BigInteger q, r;
162 r = *this;
163 r.divideWithRemainder(x, q);
164 return q;
165 }
operator %(const BigInteger & x) const166 inline BigInteger BigInteger::operator %(const BigInteger &x) const {
167 if (x.isZero()) throw "BigInteger::operator %: division by zero";
168 BigInteger q, r;
169 r = *this;
170 r.divideWithRemainder(x, q);
171 return r;
172 }
operator -() const173 inline BigInteger BigInteger::operator -() const {
174 BigInteger ans;
175 ans.negate(*this);
176 return ans;
177 }
178
179 /*
180 * ASSIGNMENT OPERATORS
181 *
182 * Now the responsibility for making a temporary copy if necessary
183 * belongs to the put-here operations. See Assignment Operators in
184 * BigUnsigned.hh.
185 */
operator +=(const BigInteger & x)186 inline void BigInteger::operator +=(const BigInteger &x) {
187 add(*this, x);
188 }
operator -=(const BigInteger & x)189 inline void BigInteger::operator -=(const BigInteger &x) {
190 subtract(*this, x);
191 }
operator *=(const BigInteger & x)192 inline void BigInteger::operator *=(const BigInteger &x) {
193 multiply(*this, x);
194 }
operator /=(const BigInteger & x)195 inline void BigInteger::operator /=(const BigInteger &x) {
196 if (x.isZero()) throw "BigInteger::operator /=: division by zero";
197 /* The following technique is slightly faster than copying *this first
198 * when x is large. */
199 BigInteger q;
200 divideWithRemainder(x, q);
201 // *this contains the remainder, but we overwrite it with the quotient.
202 *this = q;
203 }
operator %=(const BigInteger & x)204 inline void BigInteger::operator %=(const BigInteger &x) {
205 if (x.isZero()) throw "BigInteger::operator %=: division by zero";
206 BigInteger q;
207 // Mods *this by x. Don't care about quotient left in q.
208 divideWithRemainder(x, q);
209 }
210 // This one is trivial
flipSign()211 inline void BigInteger::flipSign() {
212 sign = Sign(-sign);
213 }
214
215 #endif
216