X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/05780f4b578d6ae054be0b19b8498d32a4f16c60..6e1e0f2f3c2fee3e1e9df39c6d4816566c10aafb:/BigInteger.cc diff --git a/BigInteger.cc b/BigInteger.cc index 34a4e17..11ac841 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -1,7 +1,6 @@ /* -* Matt McCutchen's Big Integer Library -* http://mysite.verizon.net/mccutchen/bigint/ -*/ + * Matt McCutchen's Big Integer Library + */ #include "BigInteger.hh" @@ -45,32 +44,32 @@ BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) { } /* -* 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. -*/ + * 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. + */ BigInteger::BigInteger(unsigned long x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } else { + if (x == 0) + sign = zero; // NumberlikeArray did the rest + else { cap = 1; blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } @@ -80,33 +79,26 @@ BigInteger::BigInteger(long x) { blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; blk = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + blk[0] = Blk(-x); + } else + sign = zero; } BigInteger::BigInteger(unsigned int x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; + if (x == 0) sign = zero; - len = 0; - } else { + else { cap = 1; blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } @@ -116,33 +108,26 @@ BigInteger::BigInteger(int x) { blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; blk = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + blk[0] = Blk(-x); + } else + sign = zero; } BigInteger::BigInteger(unsigned short x) { - if (x == 0) { - cap = 0; - blk = new Blk[0]; + if (x == 0) sign = zero; - len = 0; - } else { + else { cap = 1; blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } @@ -152,40 +137,36 @@ BigInteger::BigInteger(short x) { blk = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; blk = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); - } else { - cap = 0; - blk = new Blk[0]; - sign = zero; - len = 0; - } + blk[0] = Blk(-x); + } else + sign = zero; } // 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. -*/ + * 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 @@ -204,7 +185,7 @@ BigInteger::operator unsigned long() const { return 0; case positive: if (len == 1) - return *blk; + return blk[0]; else throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long"; case negative: @@ -219,13 +200,13 @@ BigInteger::operator long() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~lMask) == 0) - return long(*blk); + 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 & ~lMask) == 0) - return -long(*blk); + 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: @@ -238,8 +219,8 @@ BigInteger::operator unsigned int() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~uiMask) == 0) - return (unsigned int)(*blk); + 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: @@ -254,13 +235,13 @@ BigInteger::operator int() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~iMask) == 0) - return int(*blk); + 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 & ~iMask) == 0) - return -int(*blk); + 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: @@ -273,8 +254,8 @@ BigInteger::operator unsigned short() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~usMask) == 0) - return (unsigned short)(*blk); + 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: @@ -289,13 +270,13 @@ BigInteger::operator short() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~sMask) == 0) - return short(*blk); + 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 & ~sMask) == 0) - return -short(*blk); + 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: @@ -329,11 +310,18 @@ BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const { // These do some messing around to determine the sign of the result, // then call one of BigUnsigned's put-heres. +// See remarks about aliased calls in BigUnsigned.cc . +#define DTRT_ALIASED(cond, op) \ + if (cond) { \ + BigInteger tmpThis; \ + tmpThis.op; \ + *this = tmpThis; \ + return; \ + } + // Addition void BigInteger::add(const BigInteger &a, const BigInteger &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::add: One of the arguments is the invoked object"; + DTRT_ALIASED(this == &a || this == &b, add(a, b)); // If one argument is zero, copy the other. if (a.sign == zero) operator =(b); @@ -370,15 +358,15 @@ void BigInteger::add(const BigInteger &a, const BigInteger &b) { 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. - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::subtract: One of the arguments is the invoked object"; + 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); - sign = Sign(-sign); + // Take the negative of _b_'s, sign, not ours. + // Bug pointed out by Sam Larkin on 2005.03.30. + sign = Sign(-b.sign); } else if (b.sign == zero) - operator =(a); + operator =(a); // If their signs differ, take a.sign and add the magnitudes. else if (a.sign != b.sign) { sign = a.sign; @@ -409,9 +397,7 @@ void BigInteger::subtract(const BigInteger &a, const BigInteger &b) { // Multiplication void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::multiply: One of the arguments is the invoked object"; + 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; @@ -426,31 +412,38 @@ void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { } /* -* DIVISION WITH REMAINDER -* Please read the comments before the definition of -* `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of -* information you should know before reading this function. -* -* Following Knuth, I decree that x / y is to be -* 0 if y==0 and floor(real-number x / y) if y!=0. -* Then x % y shall be x - y*(integer x / y). -* -* Note that x = y * (x / y) + (x % y) always holds. -* In addition, (x % y) is from 0 to y - 1 if y > 0, -* and from -(|y| - 1) to 0 if y < 0. (x % y) = x if y = 0. -* -* Examples: (q = a / b, r = a % b) -* a b q r -* === === === === -* 4 3 1 1 -* -4 3 -2 2 -* 4 -3 -2 -2 -* -4 -3 1 -1 -*/ + * DIVISION WITH REMAINDER + * Please read the comments before the definition of + * `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of + * information you should know before reading this function. + * + * Following Knuth, I decree that x / y is to be + * 0 if y==0 and floor(real-number x / y) if y!=0. + * Then x % y shall be x - y*(integer x / y). + * + * Note that x = y * (x / y) + (x % y) always holds. + * In addition, (x % y) is from 0 to y - 1 if y > 0, + * and from -(|y| - 1) to 0 if y < 0. (x % y) = x if y = 0. + * + * Examples: (q = a / b, r = a % b) + * a b q r + * === === === === + * 4 3 1 1 + * -4 3 -2 2 + * 4 -3 -2 -2 + * -4 -3 1 -1 + */ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { - // Block unsafe calls - if (this == &b || this == &q || &b == &q) - throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object"; + // Defend against aliased calls; + // same idea as in BigUnsigned::divideWithRemainder . + if (this == &q) + throw "BigInteger::divideWithRemainder: Cannot write quotient and remainder into the same variable"; + if (this == &b || &q == &b) { + BigInteger tmpB(b); + divideWithRemainder(tmpB, q); + return; + } + // Division by zero gives quotient 0 and remainder *this if (b.sign == zero) { q.len = 0; @@ -463,9 +456,9 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { q.sign = zero; return; } - + // Here *this != 0, b != 0. - + // Do the operands have the same sign? if (sign == b.sign) { // Yes: easy case. Quotient is zero or positive. @@ -476,30 +469,30 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { // Decrease the magnitude of the dividend by one. BigUnsigned::operator --(); /* - * We tinker with the dividend before and with the - * quotient and remainder after so that the result - * comes out right. To see why it works, consider the following - * list of examples, where A is the magnitude-decreased - * a, Q and R are the results of BigUnsigned division - * with remainder on A and |b|, and q and r are the - * final results we want: - * - * a A b Q R q r - * -3 -2 3 0 2 -1 0 - * -4 -3 3 1 0 -2 2 - * -5 -4 3 1 1 -2 1 - * -6 -5 3 1 2 -2 0 - * - * It appears that we need a total of 3 corrections: - * Decrease the magnitude of a to get A. Increase the - * magnitude of Q to get q (and make it negative). - * Find r = (b - 1) - R and give it the desired sign. - */ + * We tinker with the dividend before and with the + * quotient and remainder after so that the result + * comes out right. To see why it works, consider the following + * list of examples, where A is the magnitude-decreased + * a, Q and R are the results of BigUnsigned division + * with remainder on A and |b|, and q and r are the + * final results we want: + * + * a A b Q R q r + * -3 -2 3 0 2 -1 0 + * -4 -3 3 1 0 -2 2 + * -5 -4 3 1 1 -2 1 + * -6 -5 3 1 2 -2 0 + * + * It appears that we need a total of 3 corrections: + * Decrease the magnitude of a to get A. Increase the + * magnitude of Q to get q (and make it negative). + * Find r = (b - 1) - R and give it the desired sign. + */ } - + // Divide the magnitudes. BigUnsigned::divideWithRemainder(b, q); - + if (sign != b.sign) { // More for the harder case (as described): // Increase the magnitude of the quotient by one. @@ -509,24 +502,22 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { BigUnsigned::subtract(b, temp); BigUnsigned::operator --(); } - + // 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) sign = zero; if (q.len == 0) q.sign = zero; - + // WHEW!!! } // Negation void BigInteger::negate(const BigInteger &a) { - // Block unsafe calls - if (this == &a) - throw "BigInteger::negate: The argument is the invoked object"; + DTRT_ALIASED(this == &a, negate(a)); // Copy a's magnitude BigUnsigned::operator =(a); // Copy the opposite of a.sign @@ -542,7 +533,7 @@ void BigInteger::operator ++() { allocate(1); sign = positive; len = 1; - *blk = 1; + blk[0] = 1; break; case positive: BigUnsigned::operator ++(); @@ -567,7 +558,7 @@ void BigInteger::operator --() { allocate(1); sign = negative; len = 1; - *blk = 1; + blk[0] = 1; break; case negative: BigUnsigned::operator ++();