1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
|
#ifndef BIGUNSIGNED_H
#define BIGUNSIGNED_H
#include "NumberlikeArray.hh"
/* A BigUnsigned object represents a nonnegative integer of size limited only by
* available memory. BigUnsigneds support most mathematical operators and can
* be converted to and from most primitive integer types.
*
* The number is stored as a NumberlikeArray of unsigned longs as if it were
* written in base 256^sizeof(unsigned long). The least significant block is
* first, and the length is such that the most significant block is nonzero. */
class BigUnsigned : protected NumberlikeArray<unsigned long> {
public:
// Enumeration for the result of a comparison.
enum CmpRes { less = -1, equal = 0, greater = 1 };
// BigUnsigneds are built with a Blk type of unsigned long.
typedef unsigned long Blk;
typedef NumberlikeArray<Blk>::Index Index;
using NumberlikeArray<Blk>::N;
protected:
// Creates a BigUnsigned with a capacity; for internal use.
BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {}
// Decreases len to eliminate any leading zero blocks.
void zapLeadingZeros() {
while (len > 0 && blk[len - 1] == 0)
len--;
}
public:
// Constructs zero.
BigUnsigned() : NumberlikeArray<Blk>() {}
// Copy constructor
BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {}
// Assignment operator
void operator=(const BigUnsigned &x) {
NumberlikeArray<Blk>::operator =(x);
}
// Constructor that copies from a given array of blocks.
BigUnsigned(const Blk *b, Index blen) : NumberlikeArray<Blk>(b, blen) {
// Eliminate any leading zeros we may have been passed.
zapLeadingZeros();
}
// Destructor. NumberlikeArray does the delete for us.
~BigUnsigned() {}
// Constructors from primitive integer types
BigUnsigned(unsigned long x);
BigUnsigned( long x);
BigUnsigned(unsigned int x);
BigUnsigned( int x);
BigUnsigned(unsigned short x);
BigUnsigned( short x);
protected:
// Helpers
template <class X> void initFromPrimitive (X x);
template <class X> void initFromSignedPrimitive(X x);
public:
/* Converters to primitive integer types
* The implicit conversion operators caused trouble, so these are now
* named. */
unsigned long toUnsignedLong () const;
long toLong () const;
unsigned int toUnsignedInt () const;
int toInt () const;
unsigned short toUnsignedShort() const;
short toShort () const;
protected:
// Helpers
template <class X> X convertToSignedPrimitive() const;
template <class X> X convertToPrimitive () const;
public:
// BIT/BLOCK ACCESSORS
// Expose these from NumberlikeArray directly.
using NumberlikeArray<Blk>::getCapacity;
using NumberlikeArray<Blk>::getLength;
/* Returns the requested block, or 0 if it is beyond the length (as if
* the number had 0s infinitely to the left). */
Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; }
/* Sets the requested block. The number grows or shrinks as necessary. */
void setBlock(Index i, Blk newBlock);
// The number is zero if and only if the canonical length is zero.
bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); }
/* Returns the length of the number in bits, i.e., zero if the number
* is zero and otherwise one more than the largest value of bi for
* which getBit(bi) returns true. */
Index bitLength() const;
/* Get the state of bit bi, which has value 2^bi. Bits beyond the
* number's length are considered to be 0. */
bool getBit(Index bi) const {
return (getBlock(bi / N) & (Blk(1) << (bi % N))) != 0;
}
/* Sets the state of bit bi to newBit. The number grows or shrinks as
* necessary. */
void setBit(Index bi, bool newBit);
// COMPARISONS
// Compares this to x like Perl's <=>
CmpRes compareTo(const BigUnsigned &x) const;
// Ordinary comparison operators
bool operator ==(const BigUnsigned &x) const {
return NumberlikeArray<Blk>::operator ==(x);
}
bool operator !=(const BigUnsigned &x) const {
return NumberlikeArray<Blk>::operator !=(x);
}
bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; }
bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; }
bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; }
bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; }
/*
* BigUnsigned and BigInteger both provide three kinds of operators.
* Here ``big-integer'' refers to BigInteger or BigUnsigned.
*
* (1) Overloaded ``return-by-value'' operators:
* +, -, *, /, %, unary -, &, |, ^, <<, >>.
* Big-integer code using these operators looks identical to code using
* the primitive integer types. These operators take one or two
* big-integer inputs and return a big-integer result, which can then
* be assigned to a BigInteger variable or used in an expression.
* Example:
* BigInteger a(1), b = 1;
* BigInteger c = a + b;
*
* (2) Overloaded assignment operators:
* +=, -=, *=, /=, %=, flipSign, &=, |=, ^=, <<=, >>=, ++, --.
* Again, these are used on big integers just like on ints. They take
* one writable big integer that both provides an operand and receives a
* result. Most also take a second read-only operand.
* Example:
* BigInteger a(1), b(1);
* a += b;
*
* (3) Copy-less operations: `add', `subtract', etc.
* These named methods take operands as arguments and store the result
* in the receiver (*this), avoiding unnecessary copies and allocations.
* `divideWithRemainder' is special: it both takes the dividend from and
* stores the remainder into the receiver, and it takes a separate
* object in which to store the quotient. NOTE: If you are wondering
* why these don't return a value, you probably mean to use the
* overloaded return-by-value operators instead.
*
* Examples:
* BigInteger a(43), b(7), c, d;
*
* c = a + b; // Now c == 50.
* c.add(a, b); // Same effect but without the two copies.
*
* c.divideWithRemainder(b, d);
* // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
*
* // ``Aliased'' calls now do the right thing using a temporary
* // copy, but see note on `divideWithRemainder'.
* a.add(a, b);
*/
// COPY-LESS OPERATIONS
// These 8: Arguments are read-only operands, result is saved in *this.
void add(const BigUnsigned &a, const BigUnsigned &b);
void subtract(const BigUnsigned &a, const BigUnsigned &b);
void multiply(const BigUnsigned &a, const BigUnsigned &b);
void bitAnd(const BigUnsigned &a, const BigUnsigned &b);
void bitOr(const BigUnsigned &a, const BigUnsigned &b);
void bitXor(const BigUnsigned &a, const BigUnsigned &b);
/* Negative shift amounts translate to opposite-direction shifts,
* except for -2^(8*sizeof(int)-1) which is unimplemented. */
void bitShiftLeft(const BigUnsigned &a, int b);
void bitShiftRight(const BigUnsigned &a, int b);
/* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
* / and % use semantics similar to Knuth's, which differ from the
* primitive integer semantics under division by zero. See the
* implementation in BigUnsigned.cc for details.
* `a.divideWithRemainder(b, a)' throws an exception: it doesn't make
* sense to write quotient and remainder into the same variable. */
void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
/* `divide' and `modulo' are no longer offered. Use
* `divideWithRemainder' instead. */
// OVERLOADED RETURN-BY-VALUE OPERATORS
BigUnsigned operator +(const BigUnsigned &x) const;
BigUnsigned operator -(const BigUnsigned &x) const;
BigUnsigned operator *(const BigUnsigned &x) const;
BigUnsigned operator /(const BigUnsigned &x) const;
BigUnsigned operator %(const BigUnsigned &x) const;
/* OK, maybe unary minus could succeed in one case, but it really
* shouldn't be used, so it isn't provided. */
BigUnsigned operator &(const BigUnsigned &x) const;
BigUnsigned operator |(const BigUnsigned &x) const;
BigUnsigned operator ^(const BigUnsigned &x) const;
BigUnsigned operator <<(int b) const;
BigUnsigned operator >>(int b) const;
// OVERLOADED ASSIGNMENT OPERATORS
void operator +=(const BigUnsigned &x);
void operator -=(const BigUnsigned &x);
void operator *=(const BigUnsigned &x);
void operator /=(const BigUnsigned &x);
void operator %=(const BigUnsigned &x);
void operator &=(const BigUnsigned &x);
void operator |=(const BigUnsigned &x);
void operator ^=(const BigUnsigned &x);
void operator <<=(int b);
void operator >>=(int b);
/* INCREMENT/DECREMENT OPERATORS
* To discourage messy coding, these do not return *this, so prefix
* and postfix behave the same. */
void operator ++( );
void operator ++(int);
void operator --( );
void operator --(int);
// Helper function that needs access to BigUnsigned internals
friend Blk getShiftedBlock(const BigUnsigned &num, Index x,
unsigned int y);
// See BigInteger.cc.
template <class X>
friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a);
};
/* Implementing the return-by-value and assignment operators in terms of the
* copy-less operations. The copy-less operations are responsible for making
* any necessary temporary copies to work around aliasing. */
inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const {
BigUnsigned ans;
ans.add(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const {
BigUnsigned ans;
ans.subtract(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const {
BigUnsigned ans;
ans.multiply(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const {
if (x.isZero()) throw "BigUnsigned::operator /: division by zero";
BigUnsigned q, r;
r = *this;
r.divideWithRemainder(x, q);
return q;
}
inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const {
if (x.isZero()) throw "BigUnsigned::operator %: division by zero";
BigUnsigned q, r;
r = *this;
r.divideWithRemainder(x, q);
return r;
}
inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const {
BigUnsigned ans;
ans.bitAnd(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const {
BigUnsigned ans;
ans.bitOr(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const {
BigUnsigned ans;
ans.bitXor(*this, x);
return ans;
}
inline BigUnsigned BigUnsigned::operator <<(int b) const {
BigUnsigned ans;
ans.bitShiftLeft(*this, b);
return ans;
}
inline BigUnsigned BigUnsigned::operator >>(int b) const {
BigUnsigned ans;
ans.bitShiftRight(*this, b);
return ans;
}
inline void BigUnsigned::operator +=(const BigUnsigned &x) {
add(*this, x);
}
inline void BigUnsigned::operator -=(const BigUnsigned &x) {
subtract(*this, x);
}
inline void BigUnsigned::operator *=(const BigUnsigned &x) {
multiply(*this, x);
}
inline void BigUnsigned::operator /=(const BigUnsigned &x) {
if (x.isZero()) throw "BigUnsigned::operator /=: division by zero";
/* The following technique is slightly faster than copying *this first
* when x is large. */
BigUnsigned q;
divideWithRemainder(x, q);
// *this contains the remainder, but we overwrite it with the quotient.
*this = q;
}
inline void BigUnsigned::operator %=(const BigUnsigned &x) {
if (x.isZero()) throw "BigUnsigned::operator %=: division by zero";
BigUnsigned q;
// Mods *this by x. Don't care about quotient left in q.
divideWithRemainder(x, q);
}
inline void BigUnsigned::operator &=(const BigUnsigned &x) {
bitAnd(*this, x);
}
inline void BigUnsigned::operator |=(const BigUnsigned &x) {
bitOr(*this, x);
}
inline void BigUnsigned::operator ^=(const BigUnsigned &x) {
bitXor(*this, x);
}
inline void BigUnsigned::operator <<=(int b) {
bitShiftLeft(*this, b);
}
inline void BigUnsigned::operator >>=(int b) {
bitShiftRight(*this, b);
}
/* Templates for conversions of BigUnsigned to and from primitive integers.
* BigInteger.cc needs to instantiate convertToPrimitive, and the uses in
* BigUnsigned.cc didn't do the trick; I think g++ inlined convertToPrimitive
* instead of generating linkable instantiations. So for consistency, I put
* all the templates here. */
// CONSTRUCTION FROM PRIMITIVE INTEGERS
/* Initialize this BigUnsigned from the given primitive integer. The same
* pattern works for all primitive integer types, so I put it into a template to
* reduce code duplication. (Don't worry: this is protected and we instantiate
* it only with primitive integer types.) Type X could be signed, but x is
* known to be nonnegative. */
template <class X>
void BigUnsigned::initFromPrimitive(X x) {
if (x == 0)
; // NumberlikeArray already initialized us to zero.
else {
// Create a single block. blk is NULL; no need to delete it.
cap = 1;
blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
}
/* Ditto, but first check that x is nonnegative. I could have put the check in
* initFromPrimitive and let the compiler optimize it out for unsigned-type
* instantiations, but I wanted to avoid the warning stupidly issued by g++ for
* a condition that is constant in *any* instantiation, even if not in all. */
template <class X>
void BigUnsigned::initFromSignedPrimitive(X x) {
if (x < 0)
throw "BigUnsigned constructor: "
"Cannot construct a BigUnsigned from a negative number";
else
initFromPrimitive(x);
}
// CONVERSION TO PRIMITIVE INTEGERS
/* Template with the same idea as initFromPrimitive. This might be slightly
* slower than the previous version with the masks, but it's much shorter and
* clearer, which is the library's stated goal. */
template <class X>
X BigUnsigned::convertToPrimitive() const {
if (len == 0)
// The number is zero; return zero.
return 0;
else if (len == 1) {
// The single block might fit in an X. Try the conversion.
X x = X(blk[0]);
// Make sure the result accurately represents the block.
if (Blk(x) == blk[0])
// Successful conversion.
return x;
// Otherwise fall through.
}
throw "BigUnsigned::to<Primitive>: "
"Value is too big to fit in the requested type";
}
/* Wrap the above in an x >= 0 test to make sure we got a nonnegative result,
* not a negative one that happened to convert back into the correct nonnegative
* one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again,
* separated to avoid a g++ warning. */
template <class X>
X BigUnsigned::convertToSignedPrimitive() const {
X x = convertToPrimitive<X>();
if (x >= 0)
return x;
else
throw "BigUnsigned::to(Primitive): "
"Value is too big to fit in the requested type";
}
#endif
|