X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/2301f99c6175d543626d61c0bda90e80f85e7eac..a305e8a577403b7c952e3900f64bbacf464edd98:/BigUnsigned.hh diff --git a/BigUnsigned.hh b/BigUnsigned.hh index d5557c7..683ac8b 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -3,104 +3,118 @@ #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 { - // 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::Index Index; // (NlA) Type for the index of a block in the array - NumberlikeArray::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::Index Index; + NumberlikeArray::N; - BigUnsigned(int, Index c) : NumberlikeArray(0, c) {} // Creates a BigUnsigned with a capacity +protected: + // Creates a BigUnsigned with a capacity; for internal use. + BigUnsigned(int, Index c) : NumberlikeArray(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() {} // Default constructor (value is 0) - BigUnsigned(const BigUnsigned &x) : NumberlikeArray(x) {} // Copy constructor + // Constructs zero. + BigUnsigned() : NumberlikeArray() {} + + // Copy constructor + BigUnsigned(const BigUnsigned &x) : NumberlikeArray(x) {} - void operator=(const BigUnsigned &x) { // Assignment operator + // Assignment operator + void operator=(const BigUnsigned &x) { NumberlikeArray::operator =(x); } - BigUnsigned(const Blk *b, Index l) : NumberlikeArray(b, l) { // Constructor from an array of blocks + // Constructor that copies from a given array of blocks. + BigUnsigned(const Blk *b, Index blen) : NumberlikeArray(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 void initFromPrimitive (X x); + template 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 X convertToSignedPrimitive() const; + template X convertToPrimitive () const; public: + + // BIT/BLOCK ACCESSORS + + // Expose these from NumberlikeArray directly. NumberlikeArray::getCapacity; NumberlikeArray::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::isEmpty(); } // Often convenient for loops + /* 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::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) & (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 -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::operator ==(x); } @@ -117,130 +131,119 @@ public: * 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); + /* 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); - 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 - // Additional operators in an attempt to avoid overloading tangles. + + /* `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; - // 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 - // Additional operators in an attempt to avoid overloading tangles. + // 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 - // 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 + 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); @@ -257,14 +260,18 @@ inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { return ans; } inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { - BigUnsigned ans; - ans.divide(*this, x); - return ans; + 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 { - BigUnsigned ans; - ans.modulo(*this, x); - return ans; + 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; @@ -281,36 +288,17 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { ans.bitXor(*this, x); return ans; } -inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const { +inline BigUnsigned BigUnsigned::operator <<(int b) const { BigUnsigned ans; ans.bitShiftLeft(*this, b); return ans; } -inline BigUnsigned BigUnsigned::operator >>(unsigned int b) const { +inline BigUnsigned BigUnsigned::operator >>(int b) const { BigUnsigned ans; ans.bitShiftRight(*this, b); return ans; } -inline BigUnsigned BigUnsigned::operator <<(int b) const { - if (b < 0) - throw "BigUnsigned::operator <<(int): Negative shift amounts are not supported"; - 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"; - 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); } @@ -321,18 +309,19 @@ inline void BigUnsigned::operator *=(const BigUnsigned &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 + 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) { - // Shortcut (woohoo!) + 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); - // remainder left in *this - // don't care about quotient left in q } inline void BigUnsigned::operator &=(const BigUnsigned &x) { bitAnd(*this, x); @@ -343,21 +332,87 @@ inline void BigUnsigned::operator |=(const BigUnsigned &x) { inline void BigUnsigned::operator ^=(const BigUnsigned &x) { bitXor(*this, x); } -inline void BigUnsigned::operator <<=(unsigned int b) { +inline void BigUnsigned::operator <<=(int b) { bitShiftLeft(*this, b); } -inline void BigUnsigned::operator >>=(unsigned int b) { +inline void BigUnsigned::operator >>=(int b) { bitShiftRight(*this, b); } -inline void BigUnsigned::operator <<=(int b) { - if (b < 0) - throw "BigUnsigned::operator <<=(int): Negative shift amounts are not supported"; - *this <<= (unsigned int)(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 +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); + } } -inline void BigUnsigned::operator >>=(int b) { - if (b < 0) - throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported"; - *this >>= (unsigned int)(b); + +/* 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 +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 +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: " + "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 +X BigUnsigned::convertToSignedPrimitive() const { + X x = convertToPrimitive(); + if (x >= 0) + return x; + else + throw "BigUnsigned::to(Primitive): " + "Value is too big to fit in the requested type"; } #endif