Commit | Line | Data |
---|---|---|
b35b6967 MM |
1 | #ifndef BIGINTEGER_H |
2 | #define BIGINTEGER_H | |
e67d6049 | 3 | |
05780f4b | 4 | #include "BigUnsigned.hh" |
e67d6049 | 5 | |
3e132790 MM |
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. | |
6e1e0f2f | 9 | * |
3e132790 MM |
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 { | |
5ff40cf5 | 14 | |
2301f99c | 15 | public: |
3e132790 MM |
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 }; | |
5ff40cf5 | 25 | |
2301f99c | 26 | protected: |
3e132790 MM |
27 | Sign sign; |
28 | BigUnsigned mag; | |
5ff40cf5 | 29 | |
2301f99c | 30 | public: |
3e132790 MM |
31 | // Constructs zero. |
32 | BigInteger() : sign(zero), mag() {} | |
33 | ||
34 | // Copy constructor | |
35 | BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {}; | |
05780f4b | 36 | |
3e132790 MM |
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. | |
44 | BigInteger(const Blk *b, Index blen) : mag(b, blen) { | |
45 | sign = mag.isZero() ? zero : positive; | |
05780f4b | 46 | } |
3e132790 MM |
47 | |
48 | // Constructor from a BigUnsigned and a sign | |
49 | BigInteger(const BigUnsigned &x, Sign s); | |
50 | ||
51 | // Nonnegative constructor from a BigUnsigned | |
52 | BigInteger(const BigUnsigned &x) : mag(x) { | |
53 | sign = mag.isZero() ? zero : positive; | |
05780f4b | 54 | } |
3e132790 MM |
55 | |
56 | // Constructors from primitive integer types | |
e67d6049 MM |
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); | |
5ff40cf5 | 63 | |
3e132790 MM |
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; | |
2301f99c | 77 | public: |
3e132790 MM |
78 | |
79 | // ACCESSORS | |
80 | Sign getSign() const { return sign; } | |
81 | /* The client can't do any harm by holding a read-only reference to the | |
82 | * magnitude. */ | |
83 | const BigUnsigned &getMagnitude() const { return mag; } | |
84 | ||
85 | // Some accessors that go through to the magnitude | |
86 | Index getLength() const { return mag.getLength(); } | |
87 | Index getCapacity() const { return mag.getCapacity(); } | |
88 | Blk getBlock(Index i) const { return mag.getBlock(i); } | |
89 | bool isZero() const { return sign == zero; } // A bit special | |
5ff40cf5 | 90 | |
e67d6049 | 91 | // COMPARISONS |
3e132790 | 92 | |
e67d6049 MM |
93 | // Compares this to x like Perl's <=> |
94 | CmpRes compareTo(const BigInteger &x) const; | |
3e132790 MM |
95 | |
96 | // Ordinary comparison operators | |
05780f4b | 97 | bool operator ==(const BigInteger &x) const { |
3e132790 | 98 | return sign == x.sign && mag == x.mag; |
05780f4b MM |
99 | } |
100 | bool operator !=(const BigInteger &x) const { return !operator ==(x); }; | |
101 | bool operator < (const BigInteger &x) const { return compareTo(x) == less ; } | |
102 | bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; } | |
103 | bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; } | |
104 | bool operator > (const BigInteger &x) const { return compareTo(x) == greater; } | |
5ff40cf5 | 105 | |
3e132790 MM |
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. */ | |
05780f4b | 113 | void divideWithRemainder(const BigInteger &b, BigInteger &q); |
3e132790 MM |
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(); | |
5ff40cf5 | 132 | |
e67d6049 | 133 | // INCREMENT/DECREMENT OPERATORS |
3e132790 MM |
134 | void operator ++( ); |
135 | void operator ++(int); | |
136 | void operator --( ); | |
137 | void operator --(int); | |
e67d6049 MM |
138 | }; |
139 | ||
e67d6049 MM |
140 | // NORMAL OPERATORS |
141 | /* These create an object to hold the result and invoke | |
6e1e0f2f MM |
142 | * the appropriate put-here operation on it, passing |
143 | * this and x. The new object is then returned. */ | |
e67d6049 MM |
144 | inline BigInteger BigInteger::operator +(const BigInteger &x) const { |
145 | BigInteger ans; | |
146 | ans.add(*this, x); | |
147 | return ans; | |
148 | } | |
149 | inline BigInteger BigInteger::operator -(const BigInteger &x) const { | |
150 | BigInteger ans; | |
151 | ans.subtract(*this, x); | |
152 | return ans; | |
153 | } | |
154 | inline BigInteger BigInteger::operator *(const BigInteger &x) const { | |
155 | BigInteger ans; | |
156 | ans.multiply(*this, x); | |
157 | return ans; | |
158 | } | |
159 | inline BigInteger BigInteger::operator /(const BigInteger &x) const { | |
3e132790 MM |
160 | BigInteger q, r; |
161 | r = *this; | |
162 | r.divideWithRemainder(x, q); | |
163 | return q; | |
e67d6049 MM |
164 | } |
165 | inline BigInteger BigInteger::operator %(const BigInteger &x) const { | |
3e132790 MM |
166 | BigInteger q, r; |
167 | r = *this; | |
168 | r.divideWithRemainder(x, q); | |
169 | return r; | |
e67d6049 MM |
170 | } |
171 | inline BigInteger BigInteger::operator -() const { | |
172 | BigInteger ans; | |
173 | ans.negate(*this); | |
174 | return ans; | |
175 | } | |
176 | ||
8c16728a MM |
177 | /* |
178 | * ASSIGNMENT OPERATORS | |
179 | * | |
180 | * Now the responsibility for making a temporary copy if necessary | |
181 | * belongs to the put-here operations. See Assignment Operators in | |
182 | * BigUnsigned.hh. | |
183 | */ | |
e67d6049 | 184 | inline void BigInteger::operator +=(const BigInteger &x) { |
8c16728a | 185 | add(*this, x); |
e67d6049 MM |
186 | } |
187 | inline void BigInteger::operator -=(const BigInteger &x) { | |
8c16728a | 188 | subtract(*this, x); |
e67d6049 MM |
189 | } |
190 | inline void BigInteger::operator *=(const BigInteger &x) { | |
8c16728a | 191 | multiply(*this, x); |
e67d6049 MM |
192 | } |
193 | inline void BigInteger::operator /=(const BigInteger &x) { | |
05780f4b | 194 | // Updated for divideWithRemainder |
e67d6049 | 195 | BigInteger thisCopy(*this); |
05780f4b MM |
196 | thisCopy.divideWithRemainder(x, *this); |
197 | // quotient left in *this | |
198 | // don't care about remainder left in thisCopy | |
e67d6049 MM |
199 | } |
200 | inline void BigInteger::operator %=(const BigInteger &x) { | |
05780f4b MM |
201 | // Shortcut (woohoo!) |
202 | BigInteger q; | |
203 | divideWithRemainder(x, q); | |
204 | // remainder left in *this | |
205 | // don't care about quotient left in q | |
e67d6049 MM |
206 | } |
207 | // This one is trivial | |
208 | inline void BigInteger::flipSign() { | |
209 | sign = Sign(-sign); | |
210 | } | |
211 | ||
212 | #endif |