#include "BigInteger.hh"
-// MANAGEMENT
-
-// Assignment operator
void BigInteger::operator =(const BigInteger &x) {
// Calls like a = a have no effect
if (this == &x)
// Copy sign
sign = x.sign;
// Copy the rest
- BigUnsigned::operator =(x);
+ mag = x.mag;
}
-// Constructor from an array of blocks and a sign
-BigInteger::BigInteger(const Blk *b, Index l, Sign s) : BigUnsigned(b, l) {
+BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) {
switch (s) {
- case zero:
- case positive:
- case negative:
- sign = (len == 0) ? zero : s;
+ case zero:
+ case positive:
+ case negative:
+ sign = mag.isZero() ? zero : s;
break;
- default:
- throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
+ default:
+ throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid sign";
}
}
-// Constructor from a BigUnsigned and a sign
-BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) {
+BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) {
switch (s) {
- case zero:
- case positive:
- case negative:
- sign = (len == 0) ? zero : s;
+ case zero:
+ case positive:
+ case negative:
+ sign = mag.isZero() ? zero : s;
break;
- default:
+ default:
throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
}
}
-/*
- * The steps for construction of a BigInteger
- * from an integral value x are as follows:
- * 1. If x is zero, create an empty BigInteger and stop.
- * 2. Allocate a one-block number array.
- * 3. If x is positive (or of an unsigned type), set the
- * sign of the BigInteger to positive.
- * 4. If x is of a signed type and is negative, set the
- * sign of the BigInteger to negative.
- * 5. If x is of a signed type, convert x (or -x if x < 0)
- * to the unsigned type of the same length.
- * 6. Expand x (or the result of step 5) to a Blk,
- * and store it in the number array.
- *
- * See remarks in `BigUnsigned.cc' and `NumberlikeArray.hh'
- * about new handling of zero-length arrays.
- */
+/* CONSTRUCTION FROM PRIMITIVE INTEGERS
+ * Same idea as in BigUnsigned.cc, except that negative input results in a
+ * negative BigInteger instead of an exception. */
-BigInteger::BigInteger(unsigned long x) {
- if (x == 0)
- sign = zero; // NumberlikeArray did the rest
- else {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
- }
+// Done longhand to let us use initialization.
+BigInteger::BigInteger(unsigned long x) : mag(x) {
+ sign = mag.isZero() ? zero : positive;
}
-
-BigInteger::BigInteger(long x) {
- if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
- } else if (x < 0) {
- cap = 1;
- blk = new Blk[1];
- sign = negative;
- len = 1;
- blk[0] = Blk(-x);
- } else
- sign = zero;
+BigInteger::BigInteger(unsigned int x) : mag(x) {
+ sign = mag.isZero() ? zero : positive;
}
-
-BigInteger::BigInteger(unsigned int x) {
- if (x == 0)
- sign = zero;
- else {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
- }
+BigInteger::BigInteger(unsigned short x) : mag(x) {
+ sign = mag.isZero() ? zero : positive;
}
-BigInteger::BigInteger(int x) {
- if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
- } else if (x < 0) {
- cap = 1;
- blk = new Blk[1];
- sign = negative;
- len = 1;
- blk[0] = Blk(-x);
- } else
- sign = zero;
-}
+// For signed input, determine the desired magnitude and sign separately.
-BigInteger::BigInteger(unsigned short x) {
- if (x == 0)
- sign = zero;
- else {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
+namespace {
+ template <class X, class UX>
+ BigInteger::Blk magOf(X x) {
+ /* UX(...) cast needed to stop short(-2^15), which negates to
+ * itself, from sign-extending in the conversion to Blk. */
+ return BigInteger::Blk(x < 0 ? UX(-x) : x);
+ }
+ template <class X>
+ BigInteger::Sign signOf(X x) {
+ return (x == 0) ? BigInteger::zero
+ : (x > 0) ? BigInteger::positive
+ : BigInteger::negative;
}
}
-BigInteger::BigInteger(short x) {
- if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- sign = positive;
- len = 1;
- blk[0] = Blk(x);
- } else if (x < 0) {
- cap = 1;
- blk = new Blk[1];
- sign = negative;
- len = 1;
- blk[0] = Blk(-x);
- } else
- sign = zero;
+BigInteger::BigInteger(long x) : sign(signOf(x)),
+ mag(magOf<long, unsigned long>(x)) {}
+BigInteger::BigInteger(int x) : sign(signOf(x)),
+ mag(magOf<int, unsigned int>(x)) {}
+BigInteger::BigInteger(short x) : sign(signOf(x)),
+ mag(magOf<short, unsigned short>(x)) {}
+
+// CONVERSION TO PRIMITIVE INTEGERS
+
+/* Reuse BigUnsigned's conversion to an unsigned primitive integer.
+ * The friend is a separate function rather than
+ * BigInteger::convertToUnsignedPrimitive to avoid requiring BigUnsigned to
+ * declare BigInteger. */
+template <class X>
+inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) {
+ return a.convertToPrimitive<X>();
}
-// CONVERTERS
-/*
- * The steps for conversion of a BigInteger to an
- * integral type are as follows:
- * 1. If the BigInteger is zero, return zero.
- * 2. If the BigInteger is positive:
- * 3. If it is more than one block long or its lowest
- * block has bits set out of the range of the target
- * type, throw an exception.
- * 4. Otherwise, convert the lowest block to the
- * target type and return it.
- * 5. If the BigInteger is negative:
- * 6. If the target type is unsigned, throw an exception.
- * 7. If it is more than one block long or its lowest
- * block has bits set out of the range of the target
- * type, throw an exception.
- * 8. Otherwise, convert the lowest block to the
- * target type, negate it, and return it.
- */
-
-namespace {
- // These masks are used to test whether a Blk has bits
- // set out of the range of a smaller integral type. Note
- // that this range is not considered to include the sign bit.
- const BigUnsigned::Blk lMask = ~0 >> 1;
- const BigUnsigned::Blk uiMask = (unsigned int)(~0);
- const BigUnsigned::Blk iMask = uiMask >> 1;
- const BigUnsigned::Blk usMask = (unsigned short)(~0);
- const BigUnsigned::Blk sMask = usMask >> 1;
+template <class X>
+X BigInteger::convertToUnsignedPrimitive() const {
+ if (sign == negative)
+ throw "BigInteger::to<Primitive>: "
+ "Cannot convert a negative integer to an unsigned type";
+ else
+ return convertBigUnsignedToPrimitiveAccess<X>(mag);
}
-BigInteger::operator unsigned long() const {
- switch (sign) {
- case zero:
+/* Similar to BigUnsigned::convertToPrimitive, but split into two cases for
+ * nonnegative and negative numbers. */
+template <class X, class UX>
+X BigInteger::convertToSignedPrimitive() const {
+ if (sign == zero)
return 0;
- case positive:
- if (len == 1)
- return blk[0];
- else
- throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long";
- case negative:
- throw "BigInteger operator unsigned long() const: Cannot convert a negative integer to an unsigned type";
- default:
- throw "BigInteger: Internal error";
+ else if (mag.getLength() == 1) {
+ // The single block might fit in an X. Try the conversion.
+ Blk b = mag.getBlock(0);
+ if (sign == positive) {
+ X x = X(b);
+ if (x >= 0 && Blk(x) == b)
+ return x;
+ } else {
+ X x = -X(b);
+ /* UX(...) needed to avoid rejecting conversion of
+ * -2^15 to a short. */
+ if (x < 0 && Blk(UX(-x)) == b)
+ return x;
+ }
+ // Otherwise fall through.
}
+ throw "BigInteger::to<Primitive>: "
+ "Value is too big to fit in the requested type";
}
-BigInteger::operator long() const {
- switch (sign) {
- case zero:
- return 0;
- case positive:
- if (len == 1 && (blk[0] & ~lMask) == 0)
- return long(blk[0]);
- else
- throw "BigInteger operator long() const: Value is too big for a long";
- case negative:
- if (len == 1 && (blk[0] & ~lMask) == 0)
- return -long(blk[0]);
- else
- throw "BigInteger operator long() const: Value is too big for a long";
- default:
- throw "BigInteger: Internal error";
- }
+unsigned long BigInteger::toUnsignedLong() const {
+ return convertToUnsignedPrimitive<unsigned long>();
}
-
-BigInteger::operator unsigned int() const {
- switch (sign) {
- case zero:
- return 0;
- case positive:
- if (len == 1 && (blk[0] & ~uiMask) == 0)
- return (unsigned int)(blk[0]);
- else
- throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int";
- case negative:
- throw "BigInteger operator unsigned int() const: Cannot convert a negative integer to an unsigned type";
- default:
- throw "BigInteger: Internal error";
- }
+unsigned int BigInteger::toUnsignedInt() const {
+ return convertToUnsignedPrimitive<unsigned int>();
}
-
-BigInteger::operator int() const {
- switch (sign) {
- case zero:
- return 0;
- case positive:
- if (len == 1 && (blk[0] & ~iMask) == 0)
- return int(blk[0]);
- else
- throw "BigInteger operator int() const: Value is too big for an int";
- case negative:
- if (len == 1 && (blk[0] & ~iMask) == 0)
- return -int(blk[0]);
- else
- throw "BigInteger operator int() const: Value is too big for an int";
- default:
- throw "BigInteger: Internal error";
- }
+unsigned short BigInteger::toUnsignedShort() const {
+ return convertToUnsignedPrimitive<unsigned short>();
}
-
-BigInteger::operator unsigned short() const {
- switch (sign) {
- case zero:
- return 0;
- case positive:
- if (len == 1 && (blk[0] & ~usMask) == 0)
- return (unsigned short)(blk[0]);
- else
- throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short";
- case negative:
- throw "BigInteger operator unsigned short() const: Cannot convert a negative integer to an unsigned type";
- default:
- throw "BigInteger: Internal error";
- }
+long BigInteger::toLong() const {
+ return convertToSignedPrimitive<long, unsigned long>();
}
-
-BigInteger::operator short() const {
- switch (sign) {
- case zero:
- return 0;
- case positive:
- if (len == 1 && (blk[0] & ~sMask) == 0)
- return short(blk[0]);
- else
- throw "BigInteger operator short() const: Value is too big for a short";
- case negative:
- if (len == 1 && (blk[0] & ~sMask) == 0)
- return -short(blk[0]);
- else
- throw "BigInteger operator short() const: Value is too big for a short";
- default:
- throw "BigInteger: Internal error";
- }
+int BigInteger::toInt() const {
+ return convertToSignedPrimitive<int, unsigned int>();
+}
+short BigInteger::toShort() const {
+ return convertToSignedPrimitive<short, unsigned short>();
}
// COMPARISON
return greater;
else switch (sign) {
// If the signs are the same...
- case zero:
+ case zero:
return equal; // Two zeros are equal
- case positive:
+ case positive:
// Compare the magnitudes
- return BigUnsigned::compareTo(x);
- case negative:
+ return mag.compareTo(x.mag);
+ case negative:
// Compare the magnitudes, but return the opposite result
- return CmpRes(-BigUnsigned::compareTo(x));
- default:
- throw "BigInteger: Internal error";
+ return CmpRes(-mag.compareTo(x.mag));
+ default:
+ throw "BigInteger internal error";
}
}
-// PUT-HERE OPERATIONS
-// These do some messing around to determine the sign of the result,
-// then call one of BigUnsigned's put-heres.
+/* COPY-LESS OPERATIONS
+ * These do some messing around to determine the sign of the result,
+ * then call one of BigUnsigned's copy-less operations. */
// See remarks about aliased calls in BigUnsigned.cc .
#define DTRT_ALIASED(cond, op) \
return; \
}
-// Addition
void BigInteger::add(const BigInteger &a, const BigInteger &b) {
DTRT_ALIASED(this == &a || this == &b, add(a, b));
// If one argument is zero, copy the other.
// common sign and add their magnitudes.
else if (a.sign == b.sign) {
sign = a.sign;
- BigUnsigned::add(a, b);
+ mag.add(a.mag, b.mag);
} else {
// Otherwise, their magnitudes must be compared.
- switch (a.BigUnsigned::compareTo(b)) {
+ switch (a.mag.compareTo(b.mag)) {
+ case equal:
// If their magnitudes are the same, copy zero.
- case equal:
- len = 0;
+ mag = 0;
sign = zero;
break;
// Otherwise, take the sign of the greater, and subtract
// the lesser magnitude from the greater magnitude.
- case greater:
+ case greater:
sign = a.sign;
- BigUnsigned::subtract(a, b);
+ mag.subtract(a.mag, b.mag);
break;
- case less:
+ case less:
sign = b.sign;
- BigUnsigned::subtract(b, a);
+ mag.subtract(b.mag, a.mag);
break;
}
}
}
-// Subtraction
void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
// Notice that this routine is identical to BigInteger::add,
// if one replaces b.sign by its opposite.
DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
// If a is zero, copy b and flip its sign. If b is zero, copy a.
if (a.sign == zero) {
- BigUnsigned::operator =(b);
+ mag = b.mag;
// Take the negative of _b_'s, sign, not ours.
// Bug pointed out by Sam Larkin on 2005.03.30.
sign = Sign(-b.sign);
// If their signs differ, take a.sign and add the magnitudes.
else if (a.sign != b.sign) {
sign = a.sign;
- BigUnsigned::add(a, b);
+ mag.add(a.mag, b.mag);
} else {
// Otherwise, their magnitudes must be compared.
- switch (a.BigUnsigned::compareTo(b)) {
+ switch (a.mag.compareTo(b.mag)) {
// If their magnitudes are the same, copy zero.
- case equal:
- len = 0;
+ case equal:
+ mag = 0;
sign = zero;
break;
// If a's magnitude is greater, take a.sign and
// subtract a from b.
- case greater:
+ case greater:
sign = a.sign;
- BigUnsigned::subtract(a, b);
+ mag.subtract(a.mag, b.mag);
break;
// If b's magnitude is greater, take the opposite
// of b.sign and subtract b from a.
- case less:
+ case less:
sign = Sign(-b.sign);
- BigUnsigned::subtract(b, a);
+ mag.subtract(b.mag, a.mag);
break;
}
}
}
-// Multiplication
void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
// If one object is zero, copy zero and return.
if (a.sign == zero || b.sign == zero) {
sign = zero;
- len = 0;
+ mag = 0;
return;
}
// If the signs of the arguments are the same, the result
// is positive, otherwise it is negative.
sign = (a.sign == b.sign) ? positive : negative;
// Multiply the magnitudes.
- BigUnsigned::multiply(a, b);
+ mag.multiply(a.mag, b.mag);
}
/*
// Division by zero gives quotient 0 and remainder *this
if (b.sign == zero) {
- q.len = 0;
+ q.mag = 0;
q.sign = zero;
return;
}
// 0 / b gives quotient 0 and remainder 0
if (sign == zero) {
- q.len = 0;
+ q.mag = 0;
q.sign = zero;
return;
}
// No: harder case. Quotient is negative.
q.sign = negative;
// Decrease the magnitude of the dividend by one.
- BigUnsigned::operator --();
+ mag--;
/*
* We tinker with the dividend before and with the
* quotient and remainder after so that the result
}
// Divide the magnitudes.
- BigUnsigned::divideWithRemainder(b, q);
+ mag.divideWithRemainder(b.mag, q.mag);
if (sign != b.sign) {
// More for the harder case (as described):
// Increase the magnitude of the quotient by one.
- q.BigUnsigned::operator ++();
+ q.mag++;
// Modify the remainder.
- BigUnsigned temp(*this);
- BigUnsigned::subtract(b, temp);
- BigUnsigned::operator --();
+ mag.subtract(b.mag, mag);
+ mag--;
}
// Sign of the remainder is always the sign of the divisor b.
sign = b.sign;
// Set signs to zero as necessary. (Thanks David Allen!)
- if (len == 0)
+ if (mag.isZero())
sign = zero;
- if (q.len == 0)
+ if (q.mag.isZero())
q.sign = zero;
// WHEW!!!
void BigInteger::negate(const BigInteger &a) {
DTRT_ALIASED(this == &a, negate(a));
// Copy a's magnitude
- BigUnsigned::operator =(a);
+ mag = a.mag;
// Copy the opposite of a.sign
sign = Sign(-a.sign);
}
// Prefix increment
void BigInteger::operator ++() {
- switch (sign) {
- case zero:
- allocate(1);
- sign = positive;
- len = 1;
- blk[0] = 1;
- break;
- case positive:
- BigUnsigned::operator ++();
- break;
- case negative:
- BigUnsigned::operator --();
- if (len == 0)
+ if (sign == negative) {
+ mag--;
+ if (mag == 0)
sign = zero;
- break;
+ } else {
+ mag++;
+ sign = positive; // if not already
}
}
// Prefix decrement
void BigInteger::operator --() {
- switch (sign) {
- case zero:
- allocate(1);
- sign = negative;
- len = 1;
- blk[0] = 1;
- break;
- case negative:
- BigUnsigned::operator ++();
- break;
- case positive:
- BigUnsigned::operator --();
- if (len == 0)
+ if (sign == positive) {
+ mag--;
+ if (mag == 0)
sign = zero;
- break;
+ } else {
+ mag++;
+ sign = negative;
}
}
#include "BigUnsigned.hh"
-/*
- * A BigInteger object represents a signed integer of size
- * limited only by available memory. A BigInteger can be
- * created from and converted back to most integral types,
- * and many math operations are defined on BigIntegers.
- *
- * The number is stored as a series of blocks in a
- * dynamically allocated array. It is as if the number
- * were written digit by digit in base 2 ^ N, **where N is the
- * number of bits in an unsigned long.**
+/* A BigInteger object represents a signed integer of size limited only by
+ * available memory. BigUnsigneds support most mathematical operators and can
+ * be converted to and from most primitive integer types.
*
- * This class is derived from BigUnsigned, which represents
- * a large nonnegative integer. BigUnsigned should be studied
- * first, as only new or different things are declared here.
- * Some things are redeclared so that they use the BigInteger
- * versions of methods, rather than the BigUnsigned versions.
- */
-
-class BigInteger : public BigUnsigned {
+ * A BigInteger is just an aggregate of a BigUnsigned and a sign. (It is no
+ * longer derived from BigUnsigned because that led to harmful implicit
+ * conversions.) */
+class BigInteger {
- // TYPES & CONSTANTS
public:
- enum Sign { negative = -1, zero = 0, positive = 1 }; // Enumeration for the sign of a BigInteger
+ typedef BigUnsigned::Blk Blk;
+ typedef BigUnsigned::Index Index;
+ typedef BigUnsigned::CmpRes CmpRes;
+ static const CmpRes
+ less = BigUnsigned::less ,
+ equal = BigUnsigned::equal ,
+ greater = BigUnsigned::greater;
+ // Enumeration for the sign of a BigInteger.
+ enum Sign { negative = -1, zero = 0, positive = 1 };
- // FIELDS
protected:
- Sign sign; // The sign of this BigInteger
+ Sign sign;
+ BigUnsigned mag;
- // MANAGEMENT
-protected:
- BigInteger(Sign s, Index c) : BigUnsigned(0, c), sign(s) {}; // Creates a BigInteger with a sign and capacity
public:
+ // Constructs zero.
+ BigInteger() : sign(zero), mag() {}
+
+ // Copy constructor
+ BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
+
+ // Assignment operator
+ void operator=(const BigInteger &x);
+
+ // Constructor that copies from a given array of blocks with a sign.
+ BigInteger(const Blk *b, Index blen, Sign s);
- BigInteger() : BigUnsigned(), sign(zero) {} // Default constructor (value is 0)
- BigInteger(const BigInteger &x) : BigUnsigned(x), sign(x.sign) {}; // Copy constructor
- void operator=(const BigInteger &x); // Assignment operator
- BigInteger(const Blk *b, Index l) : BigUnsigned(b, l) { // Constructor from an array of blocks
- sign = (len == 0) ? zero : positive;
+ // Nonnegative constructor that copies from a given array of blocks.
+ BigInteger(const Blk *b, Index blen) : mag(b, blen) {
+ sign = mag.isZero() ? zero : positive;
}
- BigInteger(const Blk *b, Index l, Sign s); // Constructor from an array of blocks and a sign
- BigInteger(const BigUnsigned &x) : BigUnsigned(x) { // Constructor from a BigUnsigned
- sign = (len == 0) ? zero : positive;
+
+ // Constructor from a BigUnsigned and a sign
+ BigInteger(const BigUnsigned &x, Sign s);
+
+ // Nonnegative constructor from a BigUnsigned
+ BigInteger(const BigUnsigned &x) : mag(x) {
+ sign = mag.isZero() ? zero : positive;
}
- BigInteger(const BigUnsigned &x, Sign s); // Constructor from a BigUnsigned and a sign
- // Constructors from integral types
+
+ // Constructors from primitive integer types
BigInteger(unsigned long x);
BigInteger( long x);
BigInteger(unsigned int x);
BigInteger( int x);
BigInteger(unsigned short x);
BigInteger( short x);
- // Note that a BigInteger can be converted to a BigUnsigned
- // automatically; this takes its absolute value.
- // CONVERTERS to integral types
-public:
- operator unsigned long () const;
- operator long () const;
- operator unsigned int () const;
- operator int () const;
- operator unsigned short() const;
- operator short() const;
-
- // PICKING APART
- // These accessors can be used to get the pieces of the number
+ /* 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:
+ // Helper
+ template <class X> X convertToUnsignedPrimitive() const;
+ template <class X, class UX> X convertToSignedPrimitive() const;
public:
- Sign getSign() const;
+
+ // ACCESSORS
+ Sign getSign() const { return sign; }
+ /* The client can't do any harm by holding a read-only reference to the
+ * magnitude. */
+ const BigUnsigned &getMagnitude() const { return mag; }
+
+ // Some accessors that go through to the magnitude
+ Index getLength() const { return mag.getLength(); }
+ Index getCapacity() const { return mag.getCapacity(); }
+ Blk getBlock(Index i) const { return mag.getBlock(i); }
+ bool isZero() const { return sign == zero; } // A bit special
// COMPARISONS
-public:
+
// Compares this to x like Perl's <=>
CmpRes compareTo(const BigInteger &x) const;
- // Normal comparison operators
+
+ // Ordinary comparison operators
bool operator ==(const BigInteger &x) const {
- return sign == x.sign && BigUnsigned::operator ==(x);
+ return sign == x.sign && mag == x.mag;
}
bool operator !=(const BigInteger &x) const { return !operator ==(x); };
bool operator < (const BigInteger &x) const { return compareTo(x) == less ; }
bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; }
bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
- // PUT-HERE OPERATIONS
- /* These store the result of the operation on the arguments into this.
- * a.add(b, c) is equivalent to, but faster than, a = b + c.
- * See explanation of "put-here operations" in BigUnsigned.cc . */
-public:
- void add (const BigInteger &a, const BigInteger &b); // Addition
- void subtract(const BigInteger &a, const BigInteger &b); // Subtraction
- void multiply(const BigInteger &a, const BigInteger &b); // Multiplication
- /* Divisive stuff
- * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
- * Semantics similar to Donald E. Knuth's are used for / and %,
- * and these usually differ from the semantics of primitive-type
- * / and % when negatives and/or zeroes are involved.
- * Look in `BigInteger.cc' for details.
- * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
- * sense to write quotient and remainder into the same variable.
- */
+ // OPERATORS -- See the discussion in BigUnsigned.hh.
+ void add (const BigInteger &a, const BigInteger &b);
+ void subtract(const BigInteger &a, const BigInteger &b);
+ void multiply(const BigInteger &a, const BigInteger &b);
+ /* See the comment on BigUnsigned::divideWithRemainder. Semantics
+ * differ from those of primitive integers when negatives and/or zeros
+ * are involved. */
void divideWithRemainder(const BigInteger &b, BigInteger &q);
- void divide(const BigInteger &a, const BigInteger &b) {
- BigInteger a2(a);
- a2.divideWithRemainder(b, *this);
- // quotient now in *this
- // don't care about remainder left in a2
- }
- void modulo(const BigInteger &a, const BigInteger &b) {
- *this = a;
- BigInteger q;
- divideWithRemainder(b, q);
- // remainder now in *this
- // don't care about quotient left in q
- }
- void negate(const BigInteger &a); // Negative
- // Some operations are inherently unsigned and are not
- // redefined for BigIntegers. Calling one of these on
- // a BigInteger will convert it to a BigUnsigned,
- // which takes its absolute value.
-
- // NORMAL OPERATORS
- // These perform the operation on this (to the left of the operator)
- // and x (to the right of the operator) and return a new BigInteger with the result.
-public:
- BigInteger operator +(const BigInteger &x) const; // Addition
- BigInteger operator -(const BigInteger &x) const; // Subtraction
- BigInteger operator *(const BigInteger &x) const; // Multiplication
- BigInteger operator /(const BigInteger &x) const; // Division
- BigInteger operator %(const BigInteger &x) const; // Modular reduction
- BigInteger operator -( ) const; // Negative
-
- // ASSIGNMENT OPERATORS
- // These perform the operation on this and x, storing the result into this.
-public:
- void operator +=(const BigInteger &x); // Addition
- void operator -=(const BigInteger &x); // Subtraction
- void operator *=(const BigInteger &x); // Multiplication
- void operator /=(const BigInteger &x); // Division
- void operator %=(const BigInteger &x); // Modular reduction
- void flipSign(); // Negative
+ void negate(const BigInteger &a);
+
+ /* Bitwise operators are not provided for BigIntegers. Use
+ * getMagnitude to get the magnitude and operate on that instead. */
+
+ BigInteger operator +(const BigInteger &x) const;
+ BigInteger operator -(const BigInteger &x) const;
+ BigInteger operator *(const BigInteger &x) const;
+ BigInteger operator /(const BigInteger &x) const;
+ BigInteger operator %(const BigInteger &x) const;
+ BigInteger operator -() const;
+
+ void operator +=(const BigInteger &x);
+ void operator -=(const BigInteger &x);
+ void operator *=(const BigInteger &x);
+ void operator /=(const BigInteger &x);
+ void operator %=(const BigInteger &x);
+ void flipSign();
// INCREMENT/DECREMENT OPERATORS
- // These increase or decrease the number by 1. To discourage side effects,
- // these do not return *this, so prefix and postfix behave the same.
-public:
- void operator ++( ); // Prefix increment
- void operator ++(int); // Postfix decrement
- void operator --( ); // Prefix increment
- void operator --(int); // Postfix decrement
-
+ void operator ++( );
+ void operator ++(int);
+ void operator --( );
+ void operator --(int);
};
-// PICKING APART
-inline BigInteger::Sign BigInteger::getSign() const { return sign; }
-
// NORMAL OPERATORS
/* These create an object to hold the result and invoke
* the appropriate put-here operation on it, passing
return ans;
}
inline BigInteger BigInteger::operator /(const BigInteger &x) const {
- BigInteger ans;
- ans.divide(*this, x);
- return ans;
+ BigInteger q, r;
+ r = *this;
+ r.divideWithRemainder(x, q);
+ return q;
}
inline BigInteger BigInteger::operator %(const BigInteger &x) const {
- BigInteger ans;
- ans.modulo(*this, x);
- return ans;
+ BigInteger q, r;
+ r = *this;
+ r.divideWithRemainder(x, q);
+ return r;
}
inline BigInteger BigInteger::operator -() const {
BigInteger ans;
-// This header file includes all the other header files.
+// This header file includes all of the library header files.
#include "NumberlikeArray.hh"
#include "BigUnsigned.hh"
}
std::string easyBItoString(const BigInteger &x) {
- return (x.getSign() == BigInteger::negative) ?
- (std::string("-") + easyBUtoString(x)) : (easyBUtoString(x));
+ return (x.getSign() == BigInteger::negative)
+ ? (std::string("-") + easyBUtoString(x.getMagnitude()))
+ : (easyBUtoString(x.getMagnitude()));
}
BigUnsigned easyStringToBU(const std::string &s) {
std::ostream &operator <<(std::ostream &os, const BigInteger &x) {
if (x.getSign() == BigInteger::negative)
os << '-';
- os << (const BigUnsigned &)(x);
+ os << x.getMagnitude();
return os;
}
#include "BigUnsigned.hh"
-// The "management" routines that used to be here are now in NumberlikeArray.hh.
+// Memory management definitions have moved to the bottom of NumberlikeArray.hh.
-/*
- * The steps for construction of a BigUnsigned
- * from an integral value x are as follows:
- * 1. If x is zero, create an empty BigUnsigned and stop.
- * 2. If x is negative, throw an exception.
- * 3. Allocate a one-block number array.
- * 4. If x is of a signed type, convert x to the unsigned
- * type of the same length.
- * 5. Expand x to a Blk, and store it in the number array.
- *
- * Since 2005.01.06, NumberlikeArray uses `NULL' rather
- * than a real array if one of zero length is needed.
- * These constructors implicitly call NumberlikeArray's
- * default constructor, which sets `blk = NULL, cap = len = 0'.
- * So if the input number is zero, they can just return.
- * See remarks in `NumberlikeArray.hh'.
- */
-
-BigUnsigned::BigUnsigned(unsigned long x) {
- if (x == 0)
- ; // NumberlikeArray already did all the work
- else {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- }
-}
-
-BigUnsigned::BigUnsigned(long x) {
- if (x == 0)
- ;
- else if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- } else
- throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
-}
-
-BigUnsigned::BigUnsigned(unsigned int x) {
- if (x == 0)
- ;
- else {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- }
-}
+// CONSTRUCTION FROM PRIMITIVE INTEGERS
-BigUnsigned::BigUnsigned(int x) {
+/* 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)
- ;
- else if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- } else
- throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
-}
-
-BigUnsigned::BigUnsigned(unsigned short 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;
}
}
-BigUnsigned::BigUnsigned(short x) {
- if (x == 0)
- ;
- else if (x > 0) {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- } else
- throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
+/* 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);
}
-// CONVERTERS
-/*
- * The steps for conversion of a BigUnsigned to an
- * integral type are as follows:
- * 1. If the BigUnsigned is zero, return zero.
- * 2. If it is more than one block long or its lowest
- * block has bits set out of the range of the target
- * type, throw an exception.
- * 3. Otherwise, convert the lowest block to the
- * target type and return it.
- */
+BigUnsigned::BigUnsigned(unsigned long x) { initFromPrimitive (x); }
+BigUnsigned::BigUnsigned(unsigned int x) { initFromPrimitive (x); }
+BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive (x); }
+BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); }
+BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); }
+BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); }
-namespace {
- // These masks are used to test whether a Blk has bits
- // set out of the range of a smaller integral type. Note
- // that this range is not considered to include the sign bit.
- const BigUnsigned::Blk lMask = ~0 >> 1;
- const BigUnsigned::Blk uiMask = (unsigned int)(~0);
- const BigUnsigned::Blk iMask = uiMask >> 1;
- const BigUnsigned::Blk usMask = (unsigned short)(~0);
- const BigUnsigned::Blk sMask = usMask >> 1;
-}
+// CONVERSION TO PRIMITIVE INTEGERS
-BigUnsigned::operator unsigned long() const {
+/* 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)
- return (unsigned long) blk[0];
- else
- throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
+ 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";
}
-BigUnsigned::operator long() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & lMask) == blk[0])
- return (long) blk[0];
+/* 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::operator long: Value is too big for a long";
+ throw "BigUnsigned::to(Primitive): "
+ "Value is too big to fit in the requested type";
}
-BigUnsigned::operator unsigned int() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & uiMask) == blk[0])
- return (unsigned int) blk[0];
- else
- throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
+unsigned long BigUnsigned::toUnsignedLong() const {
+ return convertToPrimitive<unsigned long>();
}
-
-BigUnsigned::operator int() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & iMask) == blk[0])
- return (int) blk[0];
- else
- throw "BigUnsigned::operator int: Value is too big for an int";
+unsigned int BigUnsigned::toUnsignedInt() const {
+ return convertToPrimitive<unsigned int>();
}
-
-BigUnsigned::operator unsigned short() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & usMask) == blk[0])
- return (unsigned short) blk[0];
- else
- throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
+unsigned short BigUnsigned::toUnsignedShort() const {
+ return convertToPrimitive<unsigned short>();
}
-
-BigUnsigned::operator short() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & sMask) == blk[0])
- return (short) blk[0];
- else
- throw "BigUnsigned::operator short: Value is too big for a short";
+long BigUnsigned::toLong() const {
+ return convertToSignedPrimitive<long>();
+}
+int BigUnsigned::toInt() const {
+ return convertToSignedPrimitive<int>();
+}
+short BigUnsigned::toShort() const {
+ return convertToSignedPrimitive<short>();
}
// COMPARISON
}
}
-// PUT-HERE OPERATIONS
-
-/*
- * Below are implementations of the four basic arithmetic operations
- * for `BigUnsigned's. Their purpose is to use a mechanism that can
- * calculate the sum, difference, product, and quotient/remainder of
- * two individual blocks in order to calculate the sum, difference,
- * product, and quotient/remainder of two multi-block BigUnsigned
- * numbers.
- *
- * As alluded to in the comment before class `BigUnsigned',
- * these algorithms bear a remarkable similarity (in purpose, if
- * not in implementation) to the way humans operate on big numbers.
- * The built-in `+', `-', `*', `/' and `%' operators are analogous
- * to elementary-school ``math facts'' and ``times tables''; the
- * four routines below are analogous to ``long division'' and its
- * relatives. (Only a computer can ``memorize'' a times table with
- * 18446744073709551616 entries! (For 32-bit blocks.))
- *
- * The discovery of these four algorithms, called the ``classical
- * algorithms'', marked the beginning of the study of computer science.
- * See Section 4.3.1 of Knuth's ``The Art of Computer Programming''.
- */
+// COPY-LESS OPERATIONS
/*
- * On most calls to put-here operations, it's safe to read the inputs little by
+ * On most calls to copy-less operations, it's safe to read the inputs little by
* little and write the outputs little by little. However, if one of the
* inputs is coming from the same variable into which the output is to be
* stored (an "aliased" call), we risk overwriting the input before we read it.
return; \
}
-// Addition
+
+
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, add(a, b));
// If one argument is zero, copy the other.
len--;
}
-// Subtraction
void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
- // If b is zero, copy a. If a is shorter than b, the result is negative.
if (b.len == 0) {
+ // If b is zero, copy a.
operator =(a);
return;
} else if (a.len < b.len)
- throw "BigUnsigned::subtract: Negative result in unsigned calculation";
+ // If a is shorter than b, the result is negative.
+ throw "BigUnsigned::subtract: "
+ "Negative result in unsigned calculation";
// Some variables...
bool borrowIn, borrowOut;
Blk temp;
// For each block index that is present in both inputs...
for (i = 0, borrowIn = false; i < b.len; i++) {
temp = a.blk[i] - b.blk[i];
- // If a reverse rollover occurred, the result is greater than the block from a.
+ // If a reverse rollover occurred,
+ // the result is greater than the block from a.
borrowOut = (temp > a.blk[i]);
// Handle an incoming borrow
if (borrowIn) {
borrowIn = (a.blk[i] == 0);
blk[i] = a.blk[i] - 1;
}
- // If there's still a borrow, the result is negative.
- // Throw an exception, but zero out this object first just in case.
+ /* If there's still a borrow, the result is negative.
+ * Throw an exception, but zero out this object so as to leave it in a
+ * predictable state. */
if (borrowIn) {
len = 0;
throw "BigUnsigned::subtract: Negative result in unsigned calculation";
- } else // Copy over the rest of the blocks
- for (; i < a.len; i++)
- blk[i] = a.blk[i];
+ } else
+ // Copy over the rest of the blocks
+ for (; i < a.len; i++)
+ blk[i] = a.blk[i];
// Zap leading zeros
zapLeadingZeros();
}
/*
* About the multiplication and division algorithms:
*
- * I searched unsucessfully for fast built-in operations like the `b_0'
+ * I searched unsucessfully for fast C++ built-in operations like the `b_0'
* and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
* Programming'' (replace `place' by `Blk'):
*
return part1 | part2;
}
-// Multiplication
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
// If either a or b is zero, set to zero.
/*
* DIVISION WITH REMAINDER
- * The functionality of divide, modulo, and %= is included in this one monstrous call,
- * which deserves some explanation.
- *
- * The division *this / b is performed.
- * Afterwards, q has the quotient, and *this has the remainder.
- * Thus, a call is like q = *this / b, *this %= b.
- *
- * This seemingly bizarre pattern of inputs and outputs has a justification. The
- * ``put-here operations'' are supposed to be fast. Therefore, they accept inputs
- * and provide outputs in the most convenient places so that no value ever needs
- * to be copied in its entirety. That way, the client can perform exactly the
- * copying it needs depending on where the inputs are and where it wants the output.
- * A better name for this function might be "modWithQuotient", but I would rather
- * not change the name now.
+ * This monstrous function mods *this by the given divisor b while storing the
+ * quotient in the given object q; at the end, *this contains the remainder.
+ * The seemingly bizarre pattern of inputs and outputs was chosen so that the
+ * function copies as little as possible (since it is implemented by repeated
+ * subtraction of multiples of b from *this).
+ *
+ * "modWithQuotient" might be a better name for this function, but I would
+ * rather not change the name now.
*/
void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
- /*
- * Defending against aliased calls is a bit tricky because we are
- * writing to both *this and q.
+ /* Defending against aliased calls is more complex than usual because we
+ * are writing to both *this and q.
*
* It would be silly to try to write quotient and remainder to the
- * same variable. Rule that out right away.
- */
+ * same variable. Rule that out right away. */
if (this == &q)
throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable";
- /*
- * Now *this and q are separate, so the only concern is that b might be
- * aliased to one of them. If so, use a temporary copy of b.
- */
+ /* Now *this and q are separate, so the only concern is that b might be
+ * aliased to one of them. If so, use a temporary copy of b. */
if (this == &b || &q == &b) {
BigUnsigned tmpB(b);
divideWithRemainder(tmpB, q);
}
/*
- * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
- * different from the way the normal C++ % operator behaves in the case of division by 0.
- * This function does it Knuth's way.
+ * Knuth's definition of mod (which this function uses) is somewhat
+ * different from the C++ definition of % in case of division by 0.
*
- * We let a / 0 == 0 (it doesn't matter) and a % 0 == a, no exceptions thrown.
- * This allows us to preserve both Knuth's demand that a mod 0 == a
- * and the useful property that (a / b) * b + (a % b) == a.
+ * We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no
+ * exceptions thrown. This allows us to preserve both Knuth's demand
+ * that a mod 0 == a and the useful property that
+ * (a / b) * b + (a % b) == a.
*/
if (b.len == 0) {
q.len = 0;
return;
}
- /*
- * At this point we know *this > b > 0. (Whew!)
- */
+ // At this point we know (*this).len >= b.len > 0. (Whew!)
/*
* Overall method:
*
* For each appropriate i and i2, decreasing:
- * Try to subtract (b << (i blocks and i2 bits)) from *this.
- * (`work2' holds the result of this subtraction.)
- * If the result is nonnegative:
+ * Subtract (b << (i blocks and i2 bits)) from *this, storing the
+ * result in subtractBuf.
+ * If the subtraction succeeds with a nonnegative result:
* Turn on bit i2 of block i of the quotient q.
- * Save the result of the subtraction back into *this.
- * Otherwise:
- * Bit i2 of block i remains off, and *this is unchanged.
+ * Copy subtractBuf back into *this.
+ * Otherwise bit i2 of block i remains off, and *this is unchanged.
*
* Eventually q will contain the entire quotient, and *this will
* be left with the remainder.
*
- * We use work2 to temporarily store the result of a subtraction.
- * work2[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
- * If the subtraction is successful, we copy work2 back to blk.
- * (There's no `work1'. In a previous version, when division was
- * coded for a read-only dividend, `work1' played the role of
- * the here-modifiable `*this' and got the remainder.)
- *
- * We never touch the i lowest blocks of either blk or work2 because
- * they are unaffected by the subtraction: we are subtracting
- * (b << (i blocks and i2 bits)), which ends in at least `i' zero blocks.
- */
+ * subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
+ * But on a single iteration, we don't touch the i lowest blocks of blk
+ * (and don't use those of subtractBuf) because these blocks are
+ * unaffected by the subtraction: we are subtracting
+ * (b << (i blocks and i2 bits)), which ends in at least `i' zero
+ * blocks. */
// Variables for the calculation
Index i, j, k;
unsigned int i2;
* and then we'll try to compare these extra bits with
* a nonexistent block to the left of the dividend. The
* extra zero block ensures sensible behavior; we need
- * an extra block in `work2' for exactly the same reason.
- *
- * See below `divideWithRemainder' for the interesting and
- * amusing story of this section of code.
+ * an extra block in `subtractBuf' for exactly the same reason.
*/
Index origLen = len; // Save real length.
- // 2006.05.03: Copy the number and then change the length!
- allocateAndCopy(len + 1); // Get the space.
- len++; // Increase the length.
- blk[origLen] = 0; // Zero the extra block.
+ /* To avoid an out-of-bounds access in case of reallocation, allocate
+ * first and then increment the logical length. */
+ allocateAndCopy(len + 1);
+ len++;
+ blk[origLen] = 0; // Zero the added block.
- // work2 holds part of the result of a subtraction; see above.
- Blk *work2 = new Blk[len];
+ // subtractBuf holds part of the result of a subtraction; see above.
+ Blk *subtractBuf = new Blk[len];
// Set preliminary length for quotient and make room
q.len = origLen - b.len + 1;
i2--;
/*
* Subtract b, shifted left i blocks and i2 bits, from *this,
- * and store the answer in work2. In the for loop, `k == i + j'.
+ * and store the answer in subtractBuf. In the for loop, `k == i + j'.
*
* Compare this to the middle section of `multiply'. They
* are in many ways analogous. See especially the discussion
borrowOut |= (temp == 0);
temp--;
}
- // Since 2005.01.11, indices of `work2' directly match those of `blk', so use `k'.
- work2[k] = temp;
+ // Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'.
+ subtractBuf[k] = temp;
borrowIn = borrowOut;
}
// No more extra iteration to deal with `bHigh'.
// Roll-over a borrow as necessary.
for (; k < origLen && borrowIn; k++) {
borrowIn = (blk[k] == 0);
- work2[k] = blk[k] - 1;
+ subtractBuf[k] = blk[k] - 1;
}
/*
* If the subtraction was performed successfully (!borrowIn),
* set bit i2 in block i of the quotient.
*
- * Then, copy the portion of work2 filled by the subtraction
+ * Then, copy the portion of subtractBuf filled by the subtraction
* back to *this. This portion starts with block i and ends--
* where? Not necessarily at block `i + b.len'! Well, we
- * increased k every time we saved a block into work2, so
- * the region of work2 we copy is just [i, k).
+ * increased k every time we saved a block into subtractBuf, so
+ * the region of subtractBuf we copy is just [i, k).
*/
if (!borrowIn) {
q.blk[i] |= (Blk(1) << i2);
while (k > i) {
k--;
- blk[k] = work2[k];
+ blk[k] = subtractBuf[k];
}
}
}
q.len--;
// Zap any/all leading zeros in remainder
zapLeadingZeros();
- // Deallocate temporary array.
+ // Deallocate subtractBuf.
// (Thanks to Brad Spencer for noticing my accidental omission of this!)
- delete [] work2;
-
+ delete [] subtractBuf;
}
-/*
- * The out-of-bounds accesses story:
- *
- * On 2005.01.06 or 2005.01.07 (depending on your time zone),
- * Milan Tomic reported out-of-bounds memory accesses in
- * the Big Integer Library. To investigate the problem, I
- * added code to bounds-check every access to the `blk' array
- * of a `NumberlikeArray'.
- *
- * This gave me warnings that fell into two categories of false
- * positives. The bounds checker was based on length, not
- * capacity, and in two places I had accessed memory that I knew
- * was inside the capacity but that wasn't inside the length:
- *
- * (1) The extra zero block at the left of `*this'. Earlier
- * versions said `allocateAndCopy(len + 1); blk[len] = 0;'
- * but did not increment `len'.
- *
- * (2) The entire digit array in the conversion constructor
- * ``BigUnsignedInABase(BigUnsigned)''. It was allocated with
- * a conservatively high capacity, but the length wasn't set
- * until the end of the constructor.
- *
- * To simplify matters, I changed both sections of code so that
- * all accesses occurred within the length. The messages went
- * away, and I told Milan that I couldn't reproduce the problem,
- * sending a development snapshot of the bounds-checked code.
- *
- * Then, on 2005.01.09-10, he told me his debugger still found
- * problems, specifically at the line `delete [] work2'.
- * It was `work2', not `blk', that was causing the problems;
- * this possibility had not occurred to me at all. In fact,
- * the problem was that `work2' needed an extra block just
- * like `*this'. Go ahead and laugh at me for finding (1)
- * without seeing what was actually causing the trouble. :-)
- *
- * The 2005.01.11 version fixes this problem. I hope this is
- * the last of my memory-related bloopers. So this is what
- * starts happening to your C++ code if you use Java too much!
- */
-// Bitwise and
+/* BITWISE OPERATORS
+ * These are straightforward blockwise operations except that they differ in
+ * the output length and the necessity of zapLeadingZeros. */
+
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
+ // The bitwise & can't be longer than either operand.
len = (a.len >= b.len) ? b.len : a.len;
allocate(len);
Index i;
zapLeadingZeros();
}
-// Bitwise or
void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
Index i;
for (; i < a2->len; i++)
blk[i] = a2->blk[i];
len = a2->len;
+ // Doesn't need zapLeadingZeros.
}
-// Bitwise xor
void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
Index i;
zapLeadingZeros();
}
-// Bitwise shift left
void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) {
DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
Index shiftBlocks = b / N;
len--;
}
-// Bitwise shift right
void BigUnsigned::bitShiftRight(const BigUnsigned &a, unsigned int b) {
DTRT_ALIASED(this == &a, bitShiftRight(a, b));
// This calculation is wacky, but expressing the shift as a left bit shift
carry = (blk[i] == 0);
}
if (carry) {
- // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
- // Matt fixed another bug 2006.04.24:
- // old number only has len blocks, so copy before increasing length
+ // Allocate and then increase length, as in divideWithRemainder
allocateAndCopy(len + 1);
len++;
blk[i] = 1;
#include "NumberlikeArray.hh"
-/*
- * A BigUnsigned object represents a nonnegative integer of size
- * limited only by available memory. A BigUnsigned can be
- * created from and converted back to most integral types,
- * and many math operations are defined on BigUnsigneds.
+/* 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 series of blocks in a
- * dynamically allocated array. It is as if the number
- * were written digit by digit in base 2 ^ N, **where N is the
- * number of bits in an unsigned long.**
- *
- * The memory-management details that used to be in here have
- * been moved into NumberlikeArray, which BigUnsigned now derives from.
- * `(NlA)' means that member(s) are declared identically in NumberlikeArray.
- * Such members are either redeclared here to make them public or are
- * here, commented out, for reference.
- */
-
+ * 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> {
- // TYPES & CONSTANTS
public:
- enum CmpRes { less = -1, equal = 0, greater = 1 }; // Enumeration for the result of a comparison
- typedef unsigned long Blk; // The number block type that BigUnsigneds are built from
- typedef NumberlikeArray<Blk>::Index Index; // (NlA) Type for the index of a block in the array
- NumberlikeArray<Blk>::N; // Number of bits in a Blk
+ // Enumeration for the result of a comparison.
+ enum CmpRes { less = -1, equal = 0, greater = 1 };
- /*
- // FIELDS
-protected:
- Index cap; // (NlA) The current allocated capacity of this BigUnsigned (in blocks)
- Index len; // (NlA) The actual length of the number stored in this BigUnsigned (in blocks)
- Blk *blk; // (NlA) Dynamically allocated array of the number blocks
- */
+ // BigUnsigneds are built with a Blk type of unsigned long.
+ typedef unsigned long Blk;
- // MANAGEMENT
-protected:
- // These members generally defer to those in NumberlikeArray, possibly with slight changes.
- // It might be nice if one could request that constructors be inherited in C++.
+ typedef NumberlikeArray<Blk>::Index Index;
+ NumberlikeArray<Blk>::N;
- BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} // Creates a BigUnsigned with a capacity
+protected:
+ // Creates a BigUnsigned with a capacity; for internal use.
+ BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {}
- void zapLeadingZeros() { // Decreases len to eliminate leading zeros
+ // Decreases len to eliminate any leading zero blocks.
+ void zapLeadingZeros() {
while (len > 0 && blk[len - 1] == 0)
len--;
}
- //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
- //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents
-
public:
- BigUnsigned() : NumberlikeArray<Blk>() {} // Default constructor (value is 0)
- BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {} // Copy constructor
+ // Constructs zero.
+ BigUnsigned() : NumberlikeArray<Blk>() {}
+
+ // Copy constructor
+ BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {}
- void operator=(const BigUnsigned &x) { // Assignment operator
+ // Assignment operator
+ void operator=(const BigUnsigned &x) {
NumberlikeArray<Blk>::operator =(x);
}
- BigUnsigned(const Blk *b, Index l) : NumberlikeArray<Blk>(b, l) { // Constructor from an array of blocks
+ // 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();
}
- // Constructors from integral types
+ // 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);
- ~BigUnsigned() {} // Destructor
-
- // CONVERTERS to integral types
+protected:
+ // Helpers
+ template <class X> void initFromPrimitive(X x);
+ template <class X> void initFromSignedPrimitive(X x);
public:
- operator unsigned long () const;
- operator long () const;
- operator unsigned int () const;
- operator int () const;
- operator unsigned short() const;
- operator short() const;
-
- // PICKING APART
- // These accessors can be used to get the pieces of the number
+
+ /* 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:
+
+ // ACCESSORS
+
+ // Expose these from NumberlikeArray directly.
NumberlikeArray<Blk>::getCapacity;
NumberlikeArray<Blk>::getLength;
- // Note that getBlock returns 0 if the block index is beyond the length of the number.
- // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left.
+
+ /* 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]; }
- // Note how we replace one level of abstraction with another. Isn't that neat?
- bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } // Often convenient for loops
+
+ // The number is zero if and only if the canonical length is zero.
+ bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); }
// COMPARISONS
-public:
+
// Compares this to x like Perl's <=>
CmpRes compareTo(const BigUnsigned &x) const;
- // Normal comparison operators
- // Bug fixed 2006.04.24: Only we, not the user, can pass a BigUnsigned off as a
- // NumberlikeArray, so we have to wrap == and !=.
+
+ // Ordinary comparison operators
bool operator ==(const BigUnsigned &x) const {
return NumberlikeArray<Blk>::operator ==(x);
}
* 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:
+ * +, -, *, /, %, 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. The first eight also take
- * a second read-only operand. Example:
+ * +=, -=, *=, /=, %=, 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) ``Put-here'' operations: `add', `subtract', etc.
- * Using a return-by-value or assignment operator generally involves
- * copy constructions and/or assignments. The ``put-here'' operations
- * require none, but they are more of a hassle to use. Most take two
- * read-only operands and save the result in the calling object `*this',
- * whose previous value is ignored. `divideWithRemainder' is an exception.
- * <<< NOTE >>>: Put-here operations do not return a value: they don't need to!!
+ * (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 bulk-copies.
- * c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder).
- * a.add(a, b); // ``Aliased'' calls now do the right thing using a
- * // temporary copy, but see note on divideWithRemainder.
+ * 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);
*/
- // PUT-HERE OPERATIONS
-public:
- /* These 3: Two read-only operands as arguments. Result left in *this. */
- void add(const BigUnsigned &a, const BigUnsigned &b); // Addition
- void subtract(const BigUnsigned &a, const BigUnsigned &b); // Subtraction
- void multiply(const BigUnsigned &a, const BigUnsigned &b); // Multiplication
- /* Divisive stuff
- * `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'.
- * Semantics similar to Donald E. Knuth's are used for / and %,
- * and these differ from the semantics of primitive-type
- * / and % under division by zero.
- * Look in `BigUnsigned.cc' for details.
- * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make
- * sense to write quotient and remainder into the same variable.
- */
+ // 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);
+ void bitShiftLeft(const BigUnsigned &a, unsigned int b);
+ void bitShiftRight(const BigUnsigned &a, unsigned 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);
- void divide(const BigUnsigned &a, const BigUnsigned &b) {
- BigUnsigned a2(a);
- a2.divideWithRemainder(b, *this);
- // quotient now in *this
- // don't care about remainder left in a2
- }
- void modulo(const BigUnsigned &a, const BigUnsigned &b) {
- *this = a;
- BigUnsigned q;
- divideWithRemainder(b, q);
- // remainder now in *this
- // don't care about quotient left in q
- }
- // Bitwise operations. Result left in *this.
- // These are not provided for BigIntegers; I think that using them on BigIntegers
- // will discard the sign first.
- void bitAnd(const BigUnsigned &a, const BigUnsigned &b); // Bitwise AND
- void bitOr(const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR
- void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR
- void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift
- void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift
-
- // NORMAL OPERATORS
- // These perform the operation on this (to the left of the operator)
- // and x (to the right of the operator) and return a new BigUnsigned with the result.
-public:
- BigUnsigned operator +(const BigUnsigned &x) const; // Addition
- BigUnsigned operator -(const BigUnsigned &x) const; // Subtraction
- BigUnsigned operator *(const BigUnsigned &x) const; // Multiplication
- BigUnsigned operator /(const BigUnsigned &x) const; // Division
- BigUnsigned operator %(const BigUnsigned &x) const; // Modular reduction
- BigUnsigned operator &(const BigUnsigned &x) const; // Bitwise AND
- BigUnsigned operator |(const BigUnsigned &x) const; // Bitwise OR
- BigUnsigned operator ^(const BigUnsigned &x) const; // Bitwise XOR
- BigUnsigned operator <<(unsigned int b) const; // Bitwise left shift
- BigUnsigned operator >>(unsigned int b) const; // Bitwise right shift
+
+ /* `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 <<(unsigned int b) const;
+ BigUnsigned operator >>(unsigned int b) const;
// Additional operators in an attempt to avoid overloading tangles.
+ // XXX Why exactly are these needed?
BigUnsigned operator <<(int b) const;
BigUnsigned operator >>(int b) const;
- // ASSIGNMENT OPERATORS
- // These perform the operation on this and x, storing the result into this.
-public:
- void operator +=(const BigUnsigned &x); // Addition
- void operator -=(const BigUnsigned &x); // Subtraction
- void operator *=(const BigUnsigned &x); // Multiplication
- void operator /=(const BigUnsigned &x); // Division
- void operator %=(const BigUnsigned &x); // Modular reduction
- void operator &=(const BigUnsigned &x); // Bitwise AND
- void operator |=(const BigUnsigned &x); // Bitwise OR
- void operator ^=(const BigUnsigned &x); // Bitwise XOR
- void operator <<=(unsigned int b); // Bitwise left shift
- void operator >>=(unsigned int b); // Bitwise right shift
+ // 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 <<=(unsigned int b);
+ void operator >>=(unsigned int b);
// Additional operators in an attempt to avoid overloading tangles.
+ // XXX Why exactly are these needed?
void operator <<=(int b);
void operator >>=(int b);
- // INCREMENT/DECREMENT OPERATORS
- // These increase or decrease the number by 1. To discourage side effects,
- // these do not return *this, so prefix and postfix behave the same.
-public:
- void operator ++( ); // Prefix increment
- void operator ++(int); // Postfix decrement
- void operator --( ); // Prefix increment
- void operator --(int); // Postfix decrement
+ /* 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);
+ friend Blk getShiftedBlock(const BigUnsigned &num, Index x,
+ unsigned int y);
+
+ // See BigInteger.cc.
+ template <class X>
+ friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a);
};
-// NORMAL OPERATORS
-/* These create an object to hold the result and invoke
- * the appropriate put-here operation on it, passing
- * this and x. The new object is then returned. */
+/* 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.divide(*this, x);
- return ans;
+ BigUnsigned q, r;
+ r = *this;
+ r.divideWithRemainder(x, q);
+ return q;
}
inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const {
- BigUnsigned ans;
- ans.modulo(*this, x);
- return ans;
+ BigUnsigned q, r;
+ r = *this;
+ r.divideWithRemainder(x, q);
+ return r;
}
inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const {
BigUnsigned ans;
}
inline BigUnsigned BigUnsigned::operator <<(int b) const {
if (b < 0)
- throw "BigUnsigned::operator <<(int): Negative shift amounts are not supported";
+ throw "BigUnsigned::operator <<(int): Negative shift amounts are not allowed";
return *this << (unsigned int)(b);
}
inline BigUnsigned BigUnsigned::operator >>(int b) const {
if (b < 0)
- throw "BigUnsigned::operator >>(int): Negative shift amounts are not supported";
+ throw "BigUnsigned::operator >>(int): Negative shift amounts are not allowed";
return *this >> (unsigned int)(b);
}
-/*
- * ASSIGNMENT OPERATORS
- *
- * Now the responsibility for making a temporary copy if necessary
- * belongs to the put-here operations. I made this change on 2007.02.13 after
- * Boris Dessy pointed out that the old implementation handled calls like
- * "a *= a" badly: it translated them to essentially "a.multiply(aCopy, a)",
- * which threw an exception.
- */
inline void BigUnsigned::operator +=(const BigUnsigned &x) {
add(*this, x);
}
multiply(*this, x);
}
inline void BigUnsigned::operator /=(const BigUnsigned &x) {
- // Updated for divideWithRemainder
- BigUnsigned thisCopy(*this);
- thisCopy.divideWithRemainder(x, *this);
- // quotient left in *this
- // don't care about remainder left in thisCopy
+ /* 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) {
- // Shortcut (woohoo!)
BigUnsigned q;
+ // Mods *this by x. Don't care about quotient left in q.
divideWithRemainder(x, q);
- // remainder left in *this
- // don't care about quotient left in q
}
inline void BigUnsigned::operator &=(const BigUnsigned &x) {
bitAnd(*this, x);
int maxBitLenOfX = x.getLength() * BigUnsigned::N;
int minBitsPerDigit = bitLen(base) - 1;
int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
- len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'.
+ len = maxDigitLenOfX; // Another change to comply with `staying in bounds'.
allocate(len); // Get the space
BigUnsigned x2(x), buBase(base);
BigUnsigned lastDigit(x2);
lastDigit.divideWithRemainder(buBase, x2);
// Save the digit.
- blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter
+ blk[digitNum] = lastDigit.toUnsignedShort();
// Move on. We can't run out of room: we figured it out above.
digitNum++;
}
-/*
- * This mechanism prevents files from being included twice.
- * Each file gets its own `id' (here `NUMBERLIKEARRAY').
- * When `#include'd, this file checks whether its `id' has
- * already been flagged. If not, it flags the `id' and
- * loads the declarations.
- */
#ifndef NUMBERLIKEARRAY_H
#define NUMBERLIKEARRAY_H
-// An essential memory-management constant.
-// I wish this were built into C++ just as it is in Java.
+// Make sure we have NULL.
#ifndef NULL
#define NULL 0
#endif
-/*
- * A NumberlikeArray<Blk> object holds a dynamically
- * allocated array of Blk. It provides certain basic
- * memory management features needed by both BigUnsigned
- * and BigUnsignedInABase, which are both derived from it.
+/* A NumberlikeArray<Blk> object holds a heap-allocated array of Blk with a
+ * length and a capacity and provides basic memory management features.
+ * BigUnsigned and BigUnsignedInABase both subclass it.
*
- * NumberlikeArray provides no information hiding, so make
- * sure you know what you are doing if you use it directly.
- * Classes derived from it will probably wish to pass on
- * some members of NumberlikeArray to their clients while
- * keeping some safe for themselves. These classes should
- * use protected inheritance and manually make some members
- * public with declarations like this:
+ * NumberlikeArray provides no information hiding. Subclasses should use
+ * nonpublic inheritance and manually expose members as desired using
+ * declarations like this:
*
* public:
- * NumberlikeArray< whatever >::getLength;
+ * NumberlikeArray< the-type-argument >::getLength;
*/
-
template <class Blk>
class NumberlikeArray {
public:
- typedef unsigned int Index; // Type for the index of a block in the array
- static const unsigned int N; // The number of bits in a block, defined below.
-
- // FIELDS
- Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
- Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
- Blk *blk; // Dynamically allocated array of the blocks
-
- /*
- * Change made on 2005.01.06:
- *
- * If a zero-length NumberlikeArray is desired, no array is actually allocated.
- * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
- *
- * `blk' is never dereferenced if the array has zero length. Furthermore,
- * `delete NULL;' does nothing and causes no error. Therefore, we can use
- * `NULL' as if it were a zero-length array from `new'.
- *
- * This is a great convenience because the only code that need be changed
- * is the array allocation code. All other code will still work fine.
- */
-
- // MANAGEMENT
- NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
+ // Type for the index of a block in the array
+ typedef unsigned int Index;
+ // The number of bits in a block, defined below.
+ static const unsigned int N;
+
+ // The current allocated capacity of this NumberlikeArray (in blocks)
+ Index cap;
+ // The actual length of the value stored in this NumberlikeArray (in blocks)
+ Index len;
+ // Heap-allocated array of the blocks (can be NULL if len == 0)
+ Blk *blk;
+
+ // Constructs a ``zero'' NumberlikeArray with the given capacity.
+ NumberlikeArray(Index c) : cap(c), len(0) {
blk = (cap > 0) ? (new Blk[cap]) : NULL;
}
- void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
- void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
-
- /*
- * Default constructor.
- *
- * If a class derived from NumberlikeArray knows at initializer time what size array
- * it wants, it can call the first constructor listed above in an initializer.
- *
- * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
- * `NULL', a fake zero-length block array. The derived class can allocate the desired
- * array itself and overwrite `blk'; it need not `delete [] blk' first.
- *
- * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
- * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
- * allocated their own array of length 0 or 1 after seeing whether the input is zero.
- * But when the NumberlikeArray transition occurred, these constructors contained an
- * implicit initializer call to the old NumberlikeArray default constructor, which
- * created a real `new'-allocated zero-length array. This array would then be lost,
- * causing a small but annoying memory leak.
- */
+
+ /* Constructs a zero NumberlikeArray without allocating a backing array.
+ * A subclass that doesn't know the needed capacity at initialization
+ * time can use this constructor and then overwrite blk without first
+ * deleting it. */
NumberlikeArray() : cap(0), len(0) {
blk = NULL;
}
- NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
- void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
- NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
- ~NumberlikeArray() { // Destructor
- delete [] blk; // Does nothing and causes no error if `blk' is null.
+
+ // Destructor. Note that `delete NULL' is a no-op.
+ ~NumberlikeArray() {
+ delete [] blk;
}
- // PICKING APART
- // These accessors can be used to get the pieces of the value
- Index getCapacity() const { return cap; }
- Index getLength() const { return len; }
- Blk getBlock(Index i) const { return blk[i]; };
- bool isEmpty() const { return len == 0; }
+ /* Ensures that the array has at least the requested capacity; may
+ * destroy the contents. */
+ void allocate(Index c);
+
+ /* Ensures that the array has at least the requested capacity; does not
+ * destroy the contents. */
+ void allocateAndCopy(Index c);
+
+ // Copy constructor
+ NumberlikeArray(const NumberlikeArray<Blk> &x);
+
+ // Assignment operator
+ void operator=(const NumberlikeArray<Blk> &x);
- // Equality comparison: checks if arrays have same length and matching values
- // Derived classes may wish to override these if differing arrays can
- // sometimes be considered equivalent.
+ // Constructor that copies from a given array of blocks
+ NumberlikeArray(const Blk *b, Index blen);
+
+ // ACCESSORS
+ Index getCapacity() const { return cap; }
+ Index getLength() const { return len; }
+ Blk getBlock(Index i) const { return blk[i]; }
+ bool isEmpty() const { return len == 0; }
+
+ /* Equality comparison: checks if both objects have the same length and
+ * equal (==) array elements to that length. Subclasses may wish to
+ * override. */
bool operator ==(const NumberlikeArray<Blk> &x) const;
- bool operator !=(const NumberlikeArray<Blk> &x) const { return !operator ==(x); }
+ bool operator !=(const NumberlikeArray<Blk> &x) const {
+ return !operator ==(x);
+ }
};
-/*
- * =================================
- * BELOW THIS POINT are template definitions; above are declarations.
- *
- * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
- * be compiled once into NumberlikeArray.o and then linked.
- *
- * However, because of the way templates are usually implemented,
- * template ``definitions'' are treated as declarations by the compiler.
- * When someone uses an instance of the template, definitions are generated,
- * and the linker is smart enough to toss duplicate definitions for the same
- * instance generated by different files.
- *
- * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
- * so other files including NumberlikeArray will be able to generate real definitions.
- */
+/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that
+ * include this header file can generate the necessary real definitions. */
template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
-// MANAGEMENT
-
-// This routine is called to ensure the array is at least a
-// certain size before another value is written into it.
template <class Blk>
void NumberlikeArray<Blk>::allocate(Index c) {
// If the requested capacity is more than the current capacity...
}
}
-// This routine is called to ensure the array is at least a
-// certain size without losing its contents.
template <class Blk>
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
// If the requested capacity is more than the current capacity...
}
}
-// Copy constructor
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
+ : len(x.len) {
// Create array
cap = len;
blk = new Blk[cap];
blk[i] = x.blk[i];
}
-// Assignment operator
template <class Blk>
void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
- // Calls like a = a have no effect
+ /* Calls like a = a have no effect; catch them before the aliasing
+ * causes a problem */
if (this == &x)
return;
// Copy length
blk[i] = x.blk[i];
}
-// Constructor from an array of blocks
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
+NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
+ : cap(blen), len(blen) {
// Create array
blk = new Blk[cap];
// Copy blocks
blk[i] = b[i];
}
-
-// EQUALITY TEST
-// This uses == to compare Blks for equality.
-// Therefore, Blks must have an == operator with the desired semantics.
template <class Blk>
bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
- // Different lengths imply different objects.
if (len != x.len)
+ // Definitely unequal.
return false;
else {
- // Compare matching blocks one by one.
+ // Compare corresponding blocks one by one.
Index i;
for (i = 0; i < len; i++)
if (blk[i] != x.blk[i])
return false;
- // If no blocks differed, the objects are equal.
+ // No blocks differed, so the objects are equal.
return true;
}
}
C++ Big Integer Library
(see ChangeLog for version)
- http://www.kepreon.com/~matt/bigint/
+ http://mattmccutchen.net/bigint/
- Written and maintained by Matt McCutchen <hashproduct@gmail.com>
+ Written and maintained by Matt McCutchen <matt@mattmccutchen.net>
You can use this library in a C++ program to do arithmetic on integers of size
limited only by your computer's memory. The library provides BigUnsigned and
If you want more detail or a feature not shown in `sample.cc', consult the
consult the actual header and source files, which are heavily commented.
+The code is intended to be reasonably portable across computers and modern C++
+compilers; in particular, it uses whatever word size the computer provides
+(32-bit, 64-bit, or whatever). Please report any portability problems.
+
Compiling programs that use the library
---------------------------------------
The library consists of a folder full of C++ header files (`.hh') and source
You are also welcome to request enhancements, but I am unlikely to do
substantial amounts of work on enhancements at this point. When I fix a bug you
report or make an enhancement you request, I will generally credit you by name
-in the source code and/or the Change Log unless you request otherwise. New
-versions of the library will be available at its Web site (above).
+in the Change Log unless you request otherwise. New versions of the library
+will be available at its Web site (above).
Note
----
BigInteger a; // a is 0
int b = 535;
- a = b; // From int to BigInteger...
- b = a; // ...and back, no casts required!
+ a = b; // From int to BigInteger implicitly...
+ b = a.toInt(); // ...and back explicitly.
/*
* If a were too big for an int you'd get a runtime exception.
* The Big Integer Library throws C-strings (that is,
314^9 = 29673367320587092457984
314^10 = 9317437338664347031806976
- */
+*/
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff