X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/a8b42b686243a175ea328c74609c7de6a0163274..b35b69671758932989823d1912627c4c2507792c:/BigUnsigned.hh diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 2a55625..3af3866 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -1,40 +1,35 @@ -/* -* Matt McCutchen's Big Integer Library -* http://mysite.verizon.net/mccutchen/bigint/ -*/ - -#ifndef BIGUNSIGNED -#define BIGUNSIGNED +#ifndef BIGUNSIGNED_H +#define BIGUNSIGNED_H #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. -* -* 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. -*/ + * 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. + * + * 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. + */ 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 - + /* // FIELDS protected: @@ -42,34 +37,34 @@ class BigUnsigned : protected NumberlikeArray { 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 */ - + // 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++. - + BigUnsigned(int, Index c) : NumberlikeArray(0, c) {} // Creates a BigUnsigned with a capacity - + void zapLeadingZeros() { // Decreases len to eliminate leading zeros 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 - + void operator=(const BigUnsigned &x) { // Assignment operator NumberlikeArray::operator =(x); } - + BigUnsigned(const Blk *b, Index l) : NumberlikeArray(b, l) { // Constructor from an array of blocks zapLeadingZeros(); } - + // Constructors from integral types BigUnsigned(unsigned long x); BigUnsigned( long x); @@ -78,7 +73,7 @@ class BigUnsigned : protected NumberlikeArray { BigUnsigned(unsigned short x); BigUnsigned( short x); ~BigUnsigned() {} // Destructor - + // CONVERTERS to integral types public: operator unsigned long () const; @@ -87,7 +82,7 @@ class BigUnsigned : protected NumberlikeArray { operator int () const; operator unsigned short() const; operator short() const; - + // PICKING APART // These accessors can be used to get the pieces of the number public: @@ -98,57 +93,64 @@ class BigUnsigned : protected NumberlikeArray { 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 - + // COMPARISONS public: // Compares this to x like Perl's <=> CmpRes compareTo(const BigUnsigned &x) const; // Normal comparison operators - NumberlikeArray::operator ==; // (NlA) The body used to be `{ return compareTo(x) == equal; }'. For performance reasons we use NumberlikeArray code that only worries about (in)equality and doesn't waste time determining which is bigger - NumberlikeArray::operator !=; // (NlA) Ditto. + // Bug fixed 2006.04.24: Only we, not the user, can pass a BigUnsigned off as a + // NumberlikeArray, so we have to wrap == and !=. + bool operator ==(const BigUnsigned &x) const { + return NumberlikeArray::operator ==(x); + } + bool operator !=(const BigUnsigned &x) const { + return NumberlikeArray::operator !=(x); + } bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; } bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; } bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; } bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; } /* - * BigUnsigned and BigInteger both provide three kinds of operators. - * Here ``big-integer'' refers to BigInteger or BigUnsigned. - * - * (1) Overloaded ``return-by-value'' operators: - * +, -, *, /, %, unary -. - * Big-integer code using these operators looks identical to - * code using the primitive integer types. These operators take - * one or two big-integer inputs and return a big-integer result, - * which can then be assigned to a BigInteger variable or used - * in an expression. Example: - * BigInteger a(1), b = 1; - * BigInteger c = a + b; - * - * (2) Overloaded assignment operators: - * +=, -=, *=, /=, %=, &=, |=, ^=, ++, --, flipSign. - * Again, these are used on big integers just like on ints. - * They take one writable big integer that both provides an - * operand and receives a result. The first eight 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!! - * 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); // Unsafe ``aliased'' call; causes a runtime error. - */ - + * BigUnsigned and BigInteger both provide three kinds of operators. + * Here ``big-integer'' refers to BigInteger or BigUnsigned. + * + * (1) Overloaded ``return-by-value'' operators: + * +, -, *, /, %, unary -. + * Big-integer code using these operators looks identical to + * code using the primitive integer types. These operators take + * one or two big-integer inputs and return a big-integer result, + * which can then be assigned to a BigInteger variable or used + * in an expression. Example: + * BigInteger a(1), b = 1; + * BigInteger c = a + b; + * + * (2) Overloaded assignment operators: + * +=, -=, *=, /=, %=, &=, |=, ^=, ++, --, flipSign. + * Again, these are used on big integers just like on ints. + * They take one writable big integer that both provides an + * operand and receives a result. The first eight 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!! + * 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. + */ + // PUT-HERE OPERATIONS public: /* These 3: Two read-only operands as arguments. Result left in *this. */ @@ -156,40 +158,37 @@ class BigUnsigned : protected NumberlikeArray { 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, 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. + */ void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); void divide(const BigUnsigned &a, const BigUnsigned &b) { - // Division, deprecated and provided for backward compatibility 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) { - // Modular reduction, deprecated and provided for backward compatibility *this = a; BigUnsigned q; divideWithRemainder(b, q); // remainder now in *this // don't care about quotient left in q } - // Bitwise operations. Two read-only operands as arguments. Result left in *this. + // 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 - - // These functions are declared but not defined. (Sorry.) - // Trying to call either will result in a link-time error. 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. @@ -202,7 +201,12 @@ class BigUnsigned : protected NumberlikeArray { 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. + 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: @@ -214,7 +218,12 @@ class BigUnsigned : protected NumberlikeArray { 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. + 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. @@ -223,15 +232,15 @@ class BigUnsigned : protected NumberlikeArray { void operator ++(int); // Postfix decrement void operator --( ); // Prefix increment void operator --(int); // Postfix decrement - + // Helper function that needs access to BigUnsigned internals friend Blk getShiftedBlock(const BigUnsigned &num, Index x, unsigned int y); }; // 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. */ + * the appropriate put-here operation on it, passing + * this and x. The new object is then returned. */ inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { BigUnsigned ans; ans.add(*this, x); @@ -272,22 +281,44 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { ans.bitXor(*this, x); return ans; } +inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const { + BigUnsigned ans; + ans.bitShiftLeft(*this, b); + return ans; +} +inline BigUnsigned BigUnsigned::operator >>(unsigned 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 -// These create a copy of this, then invoke the appropriate -// put-here operation on this, passing the copy and x. -// Exception: those updated for divideWithRemainder. +/* + * 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) { - BigUnsigned thisCopy(*this); - add(thisCopy, x); + add(*this, x); } inline void BigUnsigned::operator -=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - subtract(thisCopy, x); + subtract(*this, x); } inline void BigUnsigned::operator *=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - multiply(thisCopy, x); + multiply(*this, x); } inline void BigUnsigned::operator /=(const BigUnsigned &x) { // Updated for divideWithRemainder @@ -304,16 +335,29 @@ inline void BigUnsigned::operator %=(const BigUnsigned &x) { // don't care about quotient left in q } inline void BigUnsigned::operator &=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitAnd(thisCopy, x); + bitAnd(*this, x); } inline void BigUnsigned::operator |=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitOr(thisCopy, x); + bitOr(*this, x); } inline void BigUnsigned::operator ^=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitXor(thisCopy, x); + bitXor(*this, x); +} +inline void BigUnsigned::operator <<=(unsigned int b) { + bitShiftLeft(*this, b); +} +inline void BigUnsigned::operator >>=(unsigned 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); +} +inline void BigUnsigned::operator >>=(int b) { + if (b < 0) + throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported"; + *this >>= (unsigned int)(b); } #endif