-/*
-* Matt McCutchen's Big Integer Library
-* http://mysite.verizon.net/mccutchen/bigint/
-*/
-
#include "BigUnsigned.hh"
-// The "management" routines that used to be here are now in NumberlikeArray.cpp.
+// 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.
-*/
-
-BigUnsigned::BigUnsigned(unsigned long x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 0;
- } else {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- }
-}
+// The templates used by these constructors and converters are at the bottom of
+// BigUnsigned.hh.
-BigUnsigned::BigUnsigned(long x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 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 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); }
-BigUnsigned::BigUnsigned(unsigned int x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 0;
- } else {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
- }
-}
+unsigned long BigUnsigned::toUnsignedLong () const { return convertToPrimitive <unsigned long >(); }
+unsigned int BigUnsigned::toUnsignedInt () const { return convertToPrimitive <unsigned int >(); }
+unsigned short BigUnsigned::toUnsignedShort() const { return convertToPrimitive <unsigned short>(); }
+long BigUnsigned::toLong () const { return convertToSignedPrimitive< long >(); }
+int BigUnsigned::toInt () const { return convertToSignedPrimitive< int >(); }
+short BigUnsigned::toShort () const { return convertToSignedPrimitive< short>(); }
-BigUnsigned::BigUnsigned(int x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 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";
-}
+// BIT/BLOCK ACCESSORS
-BigUnsigned::BigUnsigned(unsigned short x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 0;
+void BigUnsigned::setBlock(Index i, Blk newBlock) {
+ if (newBlock == 0) {
+ if (i < len) {
+ blk[i] = 0;
+ zapLeadingZeros();
+ }
+ // If i >= len, no effect.
} else {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
+ if (i >= len) {
+ // The nonzero block extends the number.
+ allocateAndCopy(i+1);
+ // Zero any added blocks that we aren't setting.
+ for (Index j = len; j < i; j++)
+ blk[j] = 0;
+ len = i+1;
+ }
+ blk[i] = newBlock;
}
}
-BigUnsigned::BigUnsigned(short x) {
- if (x == 0) {
- cap = 0;
- blk = new Blk[0];
- len = 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";
-}
-
-// 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.
-*/
-
-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;
-}
-
-BigUnsigned::operator unsigned long() const {
- if (len == 0)
- 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";
-}
-
-BigUnsigned::operator long() const {
- if (len == 0)
- return 0;
- else if (len == 1 && (blk[0] & lMask) == blk[0])
- return (long) blk[0];
- else
- throw "BigUnsigned::operator long: Value is too big for a long";
-}
-
-BigUnsigned::operator unsigned int() const {
- if (len == 0)
+/* Evidently the compiler wants BigUnsigned:: on the return type because, at
+ * that point, it hasn't yet parsed the BigUnsigned:: on the name to get the
+ * proper scope. */
+BigUnsigned::Index BigUnsigned::bitLength() const {
+ if (isZero())
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";
-}
-
-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";
+ else {
+ Blk leftmostBlock = getBlock(len - 1);
+ Index leftmostBlockLen = 0;
+ while (leftmostBlock != 0) {
+ leftmostBlock >>= 1;
+ leftmostBlockLen++;
+ }
+ return leftmostBlockLen + (len - 1) * N;
+ }
}
-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";
-}
-
-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";
+void BigUnsigned::setBit(Index bi, bool newBit) {
+ Index blockI = bi / N;
+ Blk block = getBlock(blockI), mask = 1 << (bi % N);
+ block = newBit ? (block | mask) : (block & ~mask);
+ setBlock(blockI, block);
}
// COMPARISON
}
}
-// PUT-HERE OPERATIONS
+// COPY-LESS OPERATIONS
+
+/*
+ * 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.
+ * In this case, we first compute the result into a temporary BigUnsigned
+ * variable and then copy it into the requested output variable *this.
+ * Each put-here operation uses the DTRT_ALIASED macro (Do The Right Thing on
+ * aliased calls) to generate code for this check.
+ *
+ * I adopted this approach on 2007.02.13 (see Assignment Operators in
+ * BigUnsigned.hh). Before then, put-here operations rejected aliased calls
+ * with an exception. I think doing the right thing is better.
+ *
+ * Some of the put-here operations can probably handle aliased calls safely
+ * without the extra copy because (for example) they process blocks strictly
+ * right-to-left. At some point I might determine which ones don't need the
+ * copy, but my reasoning would need to be verified very carefully. For now
+ * I'll leave in the copy.
+ */
+#define DTRT_ALIASED(cond, op) \
+ if (cond) { \
+ BigUnsigned tmpThis; \
+ tmpThis.op; \
+ *this = tmpThis; \
+ return; \
+ }
+
+
-// Addition
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::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.len == 0) {
operator =(b);
operator =(a);
return;
}
+ // Some variables...
// Carries in and out of an addition stage
bool carryIn, carryOut;
Blk temp;
len--;
}
-// Subtraction
void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::subtract: One of the arguments is the invoked object";
- // If b is zero, copy a. If a is shorter than b, the result is negative.
+ DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
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;
Index i;
// 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();
}
-// Multiplication
+/*
+ * About the multiplication and division algorithms:
+ *
+ * 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'):
+ *
+ * ``b_0[:] multiplication of a one-place integer by another one-place
+ * integer, giving a two-place answer;
+ *
+ * ``c_0[:] division of a two-place integer by a one-place integer,
+ * provided that the quotient is a one-place integer, and yielding
+ * also a one-place remainder.''
+ *
+ * I also missed his note that ``[b]y adjusting the word size, if
+ * necessary, nearly all computers will have these three operations
+ * available'', so I gave up on trying to use algorithms similar to his.
+ * A future version of the library might include such algorithms; I
+ * would welcome contributions from others for this.
+ *
+ * I eventually decided to use bit-shifting algorithms. To multiply `a'
+ * and `b', we zero out the result. Then, for each `1' bit in `a', we
+ * shift `b' left the appropriate amount and add it to the result.
+ * Similarly, to divide `a' by `b', we shift `b' left varying amounts,
+ * repeatedly trying to subtract it from `a'. When we succeed, we note
+ * the fact by setting a bit in the quotient. While these algorithms
+ * have the same O(n^2) time complexity as Knuth's, the ``constant factor''
+ * is likely to be larger.
+ *
+ * Because I used these algorithms, which require single-block addition
+ * and subtraction rather than single-block multiplication and division,
+ * the innermost loops of all four routines are very similar. Study one
+ * of them and all will become clear.
+ */
+
+/*
+ * This is a little inline function used by both the multiplication
+ * routine and the division routine.
+ *
+ * `getShiftedBlock' returns the `x'th block of `num << y'.
+ * `y' may be anything from 0 to N - 1, and `x' may be anything from
+ * 0 to `num.len'.
+ *
+ * Two things contribute to this block:
+ *
+ * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
+ *
+ * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
+ *
+ * But we must be careful if `x == 0' or `x == num.len', in
+ * which case we should use 0 instead of (2) or (1), respectively.
+ *
+ * If `y == 0', then (2) contributes 0, as it should. However,
+ * in some computer environments, for a reason I cannot understand,
+ * `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
+ * will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
+ * the test `y == 0' handles this case specially.
+ */
+inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
+ BigUnsigned::Index x, unsigned int y) {
+ BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
+ BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
+ return part1 | part2;
+}
+
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::multiply: One of the arguments is the invoked object";
+ DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
// If either a or b is zero, set to zero.
if (a.len == 0 || b.len == 0) {
len = 0;
return;
}
- // Overall method: this = 0, then for each 1-bit of a, add b
- // to this shifted the appropriate amount.
+ /*
+ * Overall method:
+ *
+ * Set this = 0.
+ * For each 1-bit of `a' (say the `i2'th bit of block `i'):
+ * Add `b << (i blocks and i2 bits)' to *this.
+ */
// Variables for the calculation
Index i, j, k;
unsigned int i2;
- Blk aBlk, bHigh, temp;
+ Blk temp;
bool carryIn, carryOut;
// Set preliminary length and make room
len = a.len + b.len;
// For each block of the first number...
for (i = 0; i < a.len; i++) {
// For each 1-bit of that block...
- for (i2 = 0, aBlk = a.blk[i]; aBlk != 0; i2++, aBlk >>= 1) {
- if ((aBlk & 1) == 0)
+ for (i2 = 0; i2 < N; i2++) {
+ if ((a.blk[i] & (Blk(1) << i2)) == 0)
continue;
- /* Add b to this, shifted left i blocks and i2 bits.
- * j is the index in b, and k = i + j is the index in this.
- * The low bits of b.blk[j] are shifted and added to blk[k].
- * bHigh is used to carry the high bits to the next addition. */
- bHigh = 0;
- for (j = 0, k = i, carryIn = false; j < b.len; j++, k++) {
- temp = blk[k] + ((b.blk[j] << i2) | bHigh);
+ /*
+ * Add b to this, shifted left i blocks and i2 bits.
+ * j is the index in b, and k = i + j is the index in this.
+ *
+ * `getShiftedBlock', a short inline function defined above,
+ * is now used for the bit handling. It replaces the more
+ * complex `bHigh' code, in which each run of the loop dealt
+ * immediately with the low bits and saved the high bits to
+ * be picked up next time. The last run of the loop used to
+ * leave leftover high bits, which were handled separately.
+ * Instead, this loop runs an additional time with j == b.len.
+ * These changes were made on 2005.01.11.
+ */
+ for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
+ /*
+ * The body of this loop is very similar to the body of the first loop
+ * in `add', except that this loop does a `+=' instead of a `+'.
+ */
+ temp = blk[k] + getShiftedBlock(b, j, i2);
carryOut = (temp < blk[k]);
if (carryIn) {
temp++;
}
blk[k] = temp;
carryIn = carryOut;
- bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
- }
- temp = blk[k] + bHigh;
- carryOut = (temp < blk[k]);
- if (carryIn) {
- temp++;
- carryOut |= (temp == 0);
}
- blk[k] = temp;
- carryIn = carryOut;
- k++; // Added by Matt 2004.12.23: Move to the next block. It belongs here (and there was a corresponding line in the division routine), but I'm not certain whether it ever matters.
+ // No more extra iteration to deal with `bHigh'.
+ // Roll-over a carry as necessary.
for (; carryIn; k++) {
blk[k]++;
carryIn = (blk[k] == 0);
}
/*
-* 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.
-*/
+ * DIVISION WITH REMAINDER
+ * 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) {
- // Block unsafe calls
- if (this == &b || &q == &b || this == &q)
- throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
-
+ /* 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. */
+ 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. */
+ if (this == &b || &q == &b) {
+ BigUnsigned tmpB(b);
+ divideWithRemainder(tmpB, q);
+ return;
+ }
+
/*
- * 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.
- *
- * 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.
- */
+ * 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 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;
}
-
+
/*
- * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
- * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
- */
+ * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
+ * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
+ */
if (len < b.len) {
q.len = 0;
return;
}
-
- /*
- * At this point we know *this > b > 0. (Whew!)
- */
-
- /* DEBUG *
- std::cout << "divideWithRemainder starting\n"
- << "length of dividend: " << len
- << "\nlast block of dividend: " << getBlock(0)
- << "\nlength of divisor: " << b.len
- << "\nlast block of divisor: " << b.getBlock(0)
- << std::endl; */
-
+
+ // At this point we know (*this).len >= b.len > 0. (Whew!)
+
/*
- * Overall method: Subtract b, shifted varying amounts to
- * the left, from this, setting the bit in the quotient q
- * whenever the subtraction succeeds. 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.
- * But we don't even compute the i lowest blocks of the result,
- * because they are unaffected (we shift left i places).
- * */
+ * Overall method:
+ *
+ * For each appropriate i and i2, decreasing:
+ * 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.
+ * 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.
+ *
+ * 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;
- Blk bHigh, temp;
+ Blk temp;
bool borrowIn, borrowOut;
-
- // Make sure we have an extra zero block just past the value,
- // but don't increase the logical length. A shifted subtraction
- // (for example, subtracting 1 << 2 from 4) might stick into
- // this block.
+
+ /*
+ * Make sure we have an extra zero block just past the value.
+ *
+ * When we attempt a subtraction, we might shift `b' so
+ * its first block begins a few bits left of the dividend,
+ * 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 `subtractBuf' for exactly the same reason.
+ */
+ Index origLen = len; // Save real length.
+ /* To avoid an out-of-bounds access in case of reallocation, allocate
+ * first and then increment the logical length. */
allocateAndCopy(len + 1);
- blk[len] = 0;
-
- // work2 holds part of the result of a subtraction.
- // (There's no work1. The name work2 is from a previous version.)
- Blk *work2 = new Blk[len];
-
+ len++;
+ blk[origLen] = 0; // Zero the added block.
+
+ // 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 = len - b.len + 1;
+ q.len = origLen - b.len + 1;
q.allocate(q.len);
// Zero out the quotient
for (i = 0; i < q.len; i++)
q.blk[i] = 0;
-
+
// For each possible left-shift of b in blocks...
i = q.len;
while (i > 0) {
i--;
// For each possible left-shift of b in bits...
+ // (Remember, N is the number of bits in a Blk.)
q.blk[i] = 0;
- i2 = 8 * sizeof(Blk);
+ i2 = N;
while (i2 > 0) {
i2--;
/*
- * Subtract b, shifted left i blocks and i2 bits, from this.
- * and store the answer in work2.
- *
- * Compare this to the middle section of `multiply'. They
- * are in many ways analogous.
- */
- bHigh = 0;
- for (j = 0, k = i, borrowIn = false; j < b.len; j++, k++) {
- temp = blk[k] - ((b.blk[j] << i2) | bHigh);
+ * Subtract b, shifted left i blocks and i2 bits, from *this,
+ * 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
+ * of `getShiftedBlock'.
+ */
+ for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
+ temp = blk[k] - getShiftedBlock(b, j, i2);
borrowOut = (temp > blk[k]);
if (borrowIn) {
borrowOut |= (temp == 0);
temp--;
}
- work2[j] = temp;
+ // Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'.
+ subtractBuf[k] = temp;
borrowIn = borrowOut;
- bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
}
- temp = blk[k] - bHigh;
- borrowOut = (temp > blk[k]);
- if (borrowIn) {
- borrowOut |= (temp == 0);
- temp--;
- }
- work2[j] = temp;
- borrowIn = borrowOut;
- j++;
- k++;
- for (; k < len && borrowIn; j++, k++) {
+ // No more extra iteration to deal with `bHigh'.
+ // Roll-over a borrow as necessary.
+ for (; k < origLen && borrowIn; k++) {
borrowIn = (blk[k] == 0);
- work2[j] = blk[k] - 1;
+ subtractBuf[k] = blk[k] - 1;
}
- /* If the subtraction was performed successfully (!borrowIn), set bit i2
- * in block i of the quotient, and copy the changed portion of
- * work2 back to this. Otherwise, reset that bit and move on. */
+ /*
+ * If the subtraction was performed successfully (!borrowIn),
+ * set bit i2 in block i of the quotient.
+ *
+ * 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 subtractBuf, so
+ * the region of subtractBuf we copy is just [i, k).
+ */
if (!borrowIn) {
- q.blk[i] |= (1 << i2);
- while (j > 0) {
- j--;
+ q.blk[i] |= (Blk(1) << i2);
+ while (k > i) {
k--;
- blk[k] = work2[j];
+ 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;
-
- /* DEBUG *
- std::cout << "divideWithRemainder complete\n"
- << "length of quotient: " << q.len
- << "\nlast block of quotient: " << q.getBlock(0)
- << "\nlength of remainder: " << len
- << "\nlast block of remainder: " << getBlock(0)
- << std::endl; */
+ delete [] subtractBuf;
}
-// 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) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
+ 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) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
+ DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
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) {
- // Block unsafe calls
- if (this == &a || this == &b)
- throw "BigUnsigned::bitXor: One of the arguments is the invoked object";
+ DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
Index i;
const BigUnsigned *a2, *b2;
if (a.len >= b.len) {
a2 = &b;
b2 = &a;
}
- allocate(b2->len);
+ allocate(a2->len);
for (i = 0; i < b2->len; i++)
blk[i] = a2->blk[i] ^ b2->blk[i];
for (; i < a2->len; i++)
zapLeadingZeros();
}
+void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) {
+ DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
+ if (b < 0) {
+ if (b << 1 == 0)
+ throw "BigUnsigned::bitShiftLeft: "
+ "Pathological shift amount not implemented";
+ else {
+ bitShiftRight(a, -b);
+ return;
+ }
+ }
+ Index shiftBlocks = b / N;
+ unsigned int shiftBits = b % N;
+ // + 1: room for high bits nudged left into another block
+ len = a.len + shiftBlocks + 1;
+ allocate(len);
+ Index i, j;
+ for (i = 0; i < shiftBlocks; i++)
+ blk[i] = 0;
+ for (j = 0, i = shiftBlocks; j <= a.len; j++, i++)
+ blk[i] = getShiftedBlock(a, j, shiftBits);
+ // Zap possible leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
+void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) {
+ DTRT_ALIASED(this == &a, bitShiftRight(a, b));
+ if (b < 0) {
+ if (b << 1 == 0)
+ throw "BigUnsigned::bitShiftRight: "
+ "Pathological shift amount not implemented";
+ else {
+ bitShiftLeft(a, -b);
+ return;
+ }
+ }
+ // This calculation is wacky, but expressing the shift as a left bit shift
+ // within each block lets us use getShiftedBlock.
+ Index rightShiftBlocks = (b + N - 1) / N;
+ unsigned int leftShiftBits = N * rightShiftBlocks - b;
+ // Now (N * rightShiftBlocks - leftShiftBits) == b
+ // and 0 <= leftShiftBits < N.
+ if (rightShiftBlocks >= a.len + 1) {
+ // All of a is guaranteed to be shifted off, even considering the left
+ // bit shift.
+ len = 0;
+ return;
+ }
+ // Now we're allocating a positive amount.
+ // + 1: room for high bits nudged left into another block
+ len = a.len + 1 - rightShiftBlocks;
+ allocate(len);
+ Index i, j;
+ for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++)
+ blk[i] = getShiftedBlock(a, j, leftShiftBits);
+ // Zap possible leading zero
+ if (blk[len - 1] == 0)
+ len--;
+}
+
// INCREMENT/DECREMENT OPERATORS
// Prefix increment
carry = (blk[i] == 0);
}
if (carry) {
- // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
+ // Allocate and then increase length, as in divideWithRemainder
+ allocateAndCopy(len + 1);
len++;
- allocateAndCopy(len);
blk[i] = 1;
}
}