#include "BigUnsigned.hh"
-// The "management" routines that used to be here are now in 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);
+// Memory management definitions have moved to the bottom of NumberlikeArray.hh.
+
+// The templates used by these constructors and converters are at the bottom of
+// BigUnsigned.hh.
+
+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); }
+
+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>(); }
+
+// BIT/BLOCK ACCESSORS
+
+void BigUnsigned::setBlock(Index i, Blk newBlock) {
+ if (newBlock == 0) {
+ if (i < len) {
+ blk[i] = 0;
+ zapLeadingZeros();
+ }
+ // If i >= len, no effect.
+ } else {
+ 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(int 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)
- ;
+/* 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 {
- cap = 1;
- blk = new Blk[1];
- len = 1;
- blk[0] = Blk(x);
+ Blk leftmostBlock = getBlock(len - 1);
+ Index leftmostBlockLen = 0;
+ while (leftmostBlock != 0) {
+ leftmostBlock >>= 1;
+ leftmostBlockLen++;
+ }
+ return leftmostBlockLen + (len - 1) * N;
}
}
-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";
-}
-
-// 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)
- 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";
-}
-
-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
/*
- * 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''.
- */
-
-/*
- * 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) {
+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--;
}
-// Bitwise shift right
-void BigUnsigned::bitShiftRight(const BigUnsigned &a, unsigned int b) {
+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;
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;
Matt McCutchen's Web Site / bigint / bigint.git / blobdiff