* 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 `blk2 = NULL, cap = len = 0'.
+* 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'.
*/
; // NumberlikeArray already did all the work
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk2 = new Blk[1];
+ blk = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
// PUT-HERE 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''.
+*/
+
// Addition
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
// Block unsafe calls
operator =(a);
return;
}
+ // Some variables...
// Carries in and out of an addition stage
bool carryIn, carryOut;
Blk temp;
return;
} else if (a.len < b.len)
throw "BigUnsigned::subtract: Negative result in unsigned calculation";
+ // Some variables...
bool borrowIn, borrowOut;
Blk temp;
Index i;
zapLeadingZeros();
}
+/*
+* About the multiplication and division algorithms:
+*
+* I searched unsucessfully for fast 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;
+}
+
// Multiplication
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
// Block unsafe calls
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] & (1 << i2)) == 0)
continue;
- /* Add b to this, shifted left i blocks and i2 bits.
+ /*
+ * 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);
+ *
+ * `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);
if (this == &b || &q == &b || this == &q)
throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
- /*std::cout << "((( divideWithRemainder\n[ Dumps:\n*this:\n";
- dump();
- std::cout << "b:\n";
- b.dump();
- std::cout << "q:\n";
- q.dump();
- std::cout << "]\n";*/
-
/*
* 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.
* 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; */
-
/*
- * 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.
+ * 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:
+ * 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.
+ *
+ * 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).
- * */
+ * 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.
+ */
// 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.
- * A shifted subtraction (for example, subtracting 1 << 2 from 4)
- * might stick into this block.
*
- * In earlier versions, `len' was not increased. But then Milan Tomic
- * found out-of-bounds memory accesses. In investigating the problem,
- * I got tons of warnings in this routine, which I should have expected.
- * I decided to make the extra block logically part of the number so it
- * would not cause confusion in the future.
+ * 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 `work2' for exactly the same reason.
+ *
+ * See below `divideWithRemainder' for the interesting and
+ * amusing story of this section of code.
*/
- Index origLen = len; // original length
- len++; // increased to avoid memory management worries
- allocateAndCopy(len);
- blk[origLen] = 0;
+ Index origLen = len; // Save real length.
+ len++; // Increase the length.
+ allocateAndCopy(len); // Get the space.
+ blk[origLen] = 0; // Zero the extra block.
- // 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[origLen];
+ // work2 holds part of the result of a subtraction; see above.
+ Blk *work2 = new Blk[len];
// Set preliminary length for quotient and make room
q.len = origLen - b.len + 1;
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.
+ * Subtract b, shifted left i blocks and i2 bits, from *this,
+ * and store the answer in work2. In the for loop, `k == i + j'.
*
* Compare this to the middle section of `multiply'. They
- * are in many ways analogous.
+ * are in many ways analogous. See especially the discussion
+ * of `getShiftedBlock'.
*/
- bHigh = 0;
- for (j = 0, k = i, borrowIn = false; j < b.len; j++, k++) {
- temp = blk[k] - ((b.blk[j] << i2) | bHigh);
+ 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 `work2' directly match those of `blk', so use `k'.
+ work2[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 < origLen && 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;
+ work2[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 work2 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).
+ */
if (!borrowIn) {
q.blk[i] |= (1 << i2);
- while (j > 0) {
- j--;
+ while (k > i) {
k--;
- blk[k] = work2[j];
+ blk[k] = work2[k];
}
}
}
// (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;
-
- std::cout << "[ Dumps:\n*this:\n";
- dump();
- std::cout << "b:\n";
- b.dump();
- std::cout << "q:\n";
- q.dump();
- std::cout << "]\ndivideWithRemainder )))\n"; */
}
+/*
+* 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
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
Matt McCutchen's Web Site / bigint / bigint.git / blobdiff