2 * Matt McCutchen's Big Integer Library
5 #include "BigUnsigned.hh"
7 // The "management" routines that used to be here are now in NumberlikeArray.hh.
10 * The steps for construction of a BigUnsigned
11 * from an integral value x are as follows:
12 * 1. If x is zero, create an empty BigUnsigned and stop.
13 * 2. If x is negative, throw an exception.
14 * 3. Allocate a one-block number array.
15 * 4. If x is of a signed type, convert x to the unsigned
16 * type of the same length.
17 * 5. Expand x to a Blk, and store it in the number array.
19 * Since 2005.01.06, NumberlikeArray uses `NULL' rather
20 * than a real array if one of zero length is needed.
21 * These constructors implicitly call NumberlikeArray's
22 * default constructor, which sets `blk = NULL, cap = len = 0'.
23 * So if the input number is zero, they can just return.
24 * See remarks in `NumberlikeArray.hh'.
27 BigUnsigned::BigUnsigned(unsigned long x) {
29 ; // NumberlikeArray already did all the work
38 BigUnsigned::BigUnsigned(long x) {
47 throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
50 BigUnsigned::BigUnsigned(unsigned int x) {
61 BigUnsigned::BigUnsigned(int x) {
70 throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
73 BigUnsigned::BigUnsigned(unsigned short x) {
84 BigUnsigned::BigUnsigned(short x) {
93 throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
98 * The steps for conversion of a BigUnsigned to an
99 * integral type are as follows:
100 * 1. If the BigUnsigned is zero, return zero.
101 * 2. If it is more than one block long or its lowest
102 * block has bits set out of the range of the target
103 * type, throw an exception.
104 * 3. Otherwise, convert the lowest block to the
105 * target type and return it.
109 // These masks are used to test whether a Blk has bits
110 // set out of the range of a smaller integral type. Note
111 // that this range is not considered to include the sign bit.
112 const BigUnsigned::Blk lMask = ~0 >> 1;
113 const BigUnsigned::Blk uiMask = (unsigned int)(~0);
114 const BigUnsigned::Blk iMask = uiMask >> 1;
115 const BigUnsigned::Blk usMask = (unsigned short)(~0);
116 const BigUnsigned::Blk sMask = usMask >> 1;
119 BigUnsigned::operator unsigned long() const {
123 return (unsigned long) blk[0];
125 throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
128 BigUnsigned::operator long() const {
131 else if (len == 1 && (blk[0] & lMask) == blk[0])
132 return (long) blk[0];
134 throw "BigUnsigned::operator long: Value is too big for a long";
137 BigUnsigned::operator unsigned int() const {
140 else if (len == 1 && (blk[0] & uiMask) == blk[0])
141 return (unsigned int) blk[0];
143 throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
146 BigUnsigned::operator int() const {
149 else if (len == 1 && (blk[0] & iMask) == blk[0])
152 throw "BigUnsigned::operator int: Value is too big for an int";
155 BigUnsigned::operator unsigned short() const {
158 else if (len == 1 && (blk[0] & usMask) == blk[0])
159 return (unsigned short) blk[0];
161 throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
164 BigUnsigned::operator short() const {
167 else if (len == 1 && (blk[0] & sMask) == blk[0])
168 return (short) blk[0];
170 throw "BigUnsigned::operator short: Value is too big for a short";
174 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
175 // A bigger length implies a bigger number.
178 else if (len > x.len)
181 // Compare blocks one by one from left to right.
185 if (blk[i] == x.blk[i])
187 else if (blk[i] > x.blk[i])
192 // If no blocks differed, the numbers are equal.
197 // PUT-HERE OPERATIONS
200 * Below are implementations of the four basic arithmetic operations
201 * for `BigUnsigned's. Their purpose is to use a mechanism that can
202 * calculate the sum, difference, product, and quotient/remainder of
203 * two individual blocks in order to calculate the sum, difference,
204 * product, and quotient/remainder of two multi-block BigUnsigned
207 * As alluded to in the comment before class `BigUnsigned',
208 * these algorithms bear a remarkable similarity (in purpose, if
209 * not in implementation) to the way humans operate on big numbers.
210 * The built-in `+', `-', `*', `/' and `%' operators are analogous
211 * to elementary-school ``math facts'' and ``times tables''; the
212 * four routines below are analogous to ``long division'' and its
213 * relatives. (Only a computer can ``memorize'' a times table with
214 * 18446744073709551616 entries! (For 32-bit blocks.))
216 * The discovery of these four algorithms, called the ``classical
217 * algorithms'', marked the beginning of the study of computer science.
218 * See Section 4.3.1 of Knuth's ``The Art of Computer Programming''.
222 void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
223 // Block unsafe calls
224 if (this == &a || this == &b)
225 throw "BigUnsigned::add: One of the arguments is the invoked object";
226 // If one argument is zero, copy the other.
230 } else if (b.len == 0) {
235 // Carries in and out of an addition stage
236 bool carryIn, carryOut;
239 // a2 points to the longer input, b2 points to the shorter
240 const BigUnsigned *a2, *b2;
241 if (a.len >= b.len) {
248 // Set prelimiary length and make room in this BigUnsigned
251 // For each block index that is present in both inputs...
252 for (i = 0, carryIn = false; i < b2->len; i++) {
254 temp = a2->blk[i] + b2->blk[i];
255 // If a rollover occurred, the result is less than either input.
256 // This test is used many times in the BigUnsigned code.
257 carryOut = (temp < a2->blk[i]);
258 // If a carry was input, handle it
261 carryOut |= (temp == 0);
263 blk[i] = temp; // Save the addition result
264 carryIn = carryOut; // Pass the carry along
266 // If there is a carry left over, increase blocks until
267 // one does not roll over.
268 for (; i < a2->len && carryIn; i++) {
269 temp = a2->blk[i] + 1;
270 carryIn = (temp == 0);
273 // If the carry was resolved but the larger number
274 // still has blocks, copy them over.
275 for (; i < a2->len; i++)
277 // Set the extra block if there's still a carry, decrease length otherwise
285 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
286 // Block unsafe calls
287 if (this == &a || this == &b)
288 throw "BigUnsigned::subtract: One of the arguments is the invoked object";
289 // If b is zero, copy a. If a is shorter than b, the result is negative.
293 } else if (a.len < b.len)
294 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
296 bool borrowIn, borrowOut;
299 // Set preliminary length and make room
302 // For each block index that is present in both inputs...
303 for (i = 0, borrowIn = false; i < b.len; i++) {
304 temp = a.blk[i] - b.blk[i];
305 // If a reverse rollover occurred, the result is greater than the block from a.
306 borrowOut = (temp > a.blk[i]);
307 // Handle an incoming borrow
309 borrowOut |= (temp == 0);
312 blk[i] = temp; // Save the subtraction result
313 borrowIn = borrowOut; // Pass the borrow along
315 // If there is a borrow left over, decrease blocks until
316 // one does not reverse rollover.
317 for (; i < a.len && borrowIn; i++) {
318 borrowIn = (a.blk[i] == 0);
319 blk[i] = a.blk[i] - 1;
321 // If there's still a borrow, the result is negative.
322 // Throw an exception, but zero out this object first just in case.
325 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
326 } else // Copy over the rest of the blocks
327 for (; i < a.len; i++)
334 * About the multiplication and division algorithms:
336 * I searched unsucessfully for fast built-in operations like the `b_0'
337 * and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
338 * Programming'' (replace `place' by `Blk'):
340 * ``b_0[:] multiplication of a one-place integer by another one-place
341 * integer, giving a two-place answer;
343 * ``c_0[:] division of a two-place integer by a one-place integer,
344 * provided that the quotient is a one-place integer, and yielding
345 * also a one-place remainder.''
347 * I also missed his note that ``[b]y adjusting the word size, if
348 * necessary, nearly all computers will have these three operations
349 * available'', so I gave up on trying to use algorithms similar to his.
350 * A future version of the library might include such algorithms; I
351 * would welcome contributions from others for this.
353 * I eventually decided to use bit-shifting algorithms. To multiply `a'
354 * and `b', we zero out the result. Then, for each `1' bit in `a', we
355 * shift `b' left the appropriate amount and add it to the result.
356 * Similarly, to divide `a' by `b', we shift `b' left varying amounts,
357 * repeatedly trying to subtract it from `a'. When we succeed, we note
358 * the fact by setting a bit in the quotient. While these algorithms
359 * have the same O(n^2) time complexity as Knuth's, the ``constant factor''
360 * is likely to be larger.
362 * Because I used these algorithms, which require single-block addition
363 * and subtraction rather than single-block multiplication and division,
364 * the innermost loops of all four routines are very similar. Study one
365 * of them and all will become clear.
369 * This is a little inline function used by both the multiplication
370 * routine and the division routine.
372 * `getShiftedBlock' returns the `x'th block of `num << y'.
373 * `y' may be anything from 0 to N - 1, and `x' may be anything from
376 * Two things contribute to this block:
378 * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
380 * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
382 * But we must be careful if `x == 0' or `x == num.len', in
383 * which case we should use 0 instead of (2) or (1), respectively.
385 * If `y == 0', then (2) contributes 0, as it should. However,
386 * in some computer environments, for a reason I cannot understand,
387 * `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
388 * will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
389 * the test `y == 0' handles this case specially.
391 inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
392 BigUnsigned::Index x, unsigned int y) {
393 BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
394 BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
395 return part1 | part2;
399 void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
400 // Block unsafe calls
401 if (this == &a || this == &b)
402 throw "BigUnsigned::multiply: One of the arguments is the invoked object";
403 // If either a or b is zero, set to zero.
404 if (a.len == 0 || b.len == 0) {
412 * For each 1-bit of `a' (say the `i2'th bit of block `i'):
413 * Add `b << (i blocks and i2 bits)' to *this.
415 // Variables for the calculation
419 bool carryIn, carryOut;
420 // Set preliminary length and make room
423 // Zero out this object
424 for (i = 0; i < len; i++)
426 // For each block of the first number...
427 for (i = 0; i < a.len; i++) {
428 // For each 1-bit of that block...
429 for (i2 = 0; i2 < N; i2++) {
430 if ((a.blk[i] & (Blk(1) << i2)) == 0)
433 * Add b to this, shifted left i blocks and i2 bits.
434 * j is the index in b, and k = i + j is the index in this.
436 * `getShiftedBlock', a short inline function defined above,
437 * is now used for the bit handling. It replaces the more
438 * complex `bHigh' code, in which each run of the loop dealt
439 * immediately with the low bits and saved the high bits to
440 * be picked up next time. The last run of the loop used to
441 * leave leftover high bits, which were handled separately.
442 * Instead, this loop runs an additional time with j == b.len.
443 * These changes were made on 2005.01.11.
445 for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
447 * The body of this loop is very similar to the body of the first loop
448 * in `add', except that this loop does a `+=' instead of a `+'.
450 temp = blk[k] + getShiftedBlock(b, j, i2);
451 carryOut = (temp < blk[k]);
454 carryOut |= (temp == 0);
459 // No more extra iteration to deal with `bHigh'.
460 // Roll-over a carry as necessary.
461 for (; carryIn; k++) {
463 carryIn = (blk[k] == 0);
467 // Zap possible leading zero
468 if (blk[len - 1] == 0)
473 * DIVISION WITH REMAINDER
474 * The functionality of divide, modulo, and %= is included in this one monstrous call,
475 * which deserves some explanation.
477 * The division *this / b is performed.
478 * Afterwards, q has the quotient, and *this has the remainder.
479 * Thus, a call is like q = *this / b, *this %= b.
481 * This seemingly bizarre pattern of inputs and outputs has a justification. The
482 * ``put-here operations'' are supposed to be fast. Therefore, they accept inputs
483 * and provide outputs in the most convenient places so that no value ever needs
484 * to be copied in its entirety. That way, the client can perform exactly the
485 * copying it needs depending on where the inputs are and where it wants the output.
487 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
488 // Block unsafe calls
489 if (this == &b || &q == &b || this == &q)
490 throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
493 * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
494 * different from the way the normal C++ % operator behaves in the case of division by 0.
495 * This function does it Knuth's way.
497 * We let a / 0 == 0 (it doesn't matter) and a % 0 == a, no exceptions thrown.
498 * This allows us to preserve both Knuth's demand that a mod 0 == a
499 * and the useful property that (a / b) * b + (a % b) == a.
507 * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
508 * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
516 * At this point we know *this > b > 0. (Whew!)
522 * For each appropriate i and i2, decreasing:
523 * Try to subtract (b << (i blocks and i2 bits)) from *this.
524 * (`work2' holds the result of this subtraction.)
525 * If the result is nonnegative:
526 * Turn on bit i2 of block i of the quotient q.
527 * Save the result of the subtraction back into *this.
529 * Bit i2 of block i remains off, and *this is unchanged.
531 * Eventually q will contain the entire quotient, and *this will
532 * be left with the remainder.
534 * We use work2 to temporarily store the result of a subtraction.
535 * work2[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
536 * If the subtraction is successful, we copy work2 back to blk.
537 * (There's no `work1'. In a previous version, when division was
538 * coded for a read-only dividend, `work1' played the role of
539 * the here-modifiable `*this' and got the remainder.)
541 * We never touch the i lowest blocks of either blk or work2 because
542 * they are unaffected by the subtraction: we are subtracting
543 * (b << (i blocks and i2 bits)), which ends in at least `i' zero blocks.
545 // Variables for the calculation
549 bool borrowIn, borrowOut;
552 * Make sure we have an extra zero block just past the value.
554 * When we attempt a subtraction, we might shift `b' so
555 * its first block begins a few bits left of the dividend,
556 * and then we'll try to compare these extra bits with
557 * a nonexistent block to the left of the dividend. The
558 * extra zero block ensures sensible behavior; we need
559 * an extra block in `work2' for exactly the same reason.
561 * See below `divideWithRemainder' for the interesting and
562 * amusing story of this section of code.
564 Index origLen = len; // Save real length.
565 // 2006.05.03: Copy the number and then change the length!
566 allocateAndCopy(len + 1); // Get the space.
567 len++; // Increase the length.
568 blk[origLen] = 0; // Zero the extra block.
570 // work2 holds part of the result of a subtraction; see above.
571 Blk *work2 = new Blk[len];
573 // Set preliminary length for quotient and make room
574 q.len = origLen - b.len + 1;
576 // Zero out the quotient
577 for (i = 0; i < q.len; i++)
580 // For each possible left-shift of b in blocks...
584 // For each possible left-shift of b in bits...
585 // (Remember, N is the number of bits in a Blk.)
591 * Subtract b, shifted left i blocks and i2 bits, from *this,
592 * and store the answer in work2. In the for loop, `k == i + j'.
594 * Compare this to the middle section of `multiply'. They
595 * are in many ways analogous. See especially the discussion
596 * of `getShiftedBlock'.
598 for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
599 temp = blk[k] - getShiftedBlock(b, j, i2);
600 borrowOut = (temp > blk[k]);
602 borrowOut |= (temp == 0);
605 // Since 2005.01.11, indices of `work2' directly match those of `blk', so use `k'.
607 borrowIn = borrowOut;
609 // No more extra iteration to deal with `bHigh'.
610 // Roll-over a borrow as necessary.
611 for (; k < origLen && borrowIn; k++) {
612 borrowIn = (blk[k] == 0);
613 work2[k] = blk[k] - 1;
616 * If the subtraction was performed successfully (!borrowIn),
617 * set bit i2 in block i of the quotient.
619 * Then, copy the portion of work2 filled by the subtraction
620 * back to *this. This portion starts with block i and ends--
621 * where? Not necessarily at block `i + b.len'! Well, we
622 * increased k every time we saved a block into work2, so
623 * the region of work2 we copy is just [i, k).
626 q.blk[i] |= (Blk(1) << i2);
634 // Zap possible leading zero in quotient
635 if (q.blk[q.len - 1] == 0)
637 // Zap any/all leading zeros in remainder
639 // Deallocate temporary array.
640 // (Thanks to Brad Spencer for noticing my accidental omission of this!)
645 * The out-of-bounds accesses story:
647 * On 2005.01.06 or 2005.01.07 (depending on your time zone),
648 * Milan Tomic reported out-of-bounds memory accesses in
649 * the Big Integer Library. To investigate the problem, I
650 * added code to bounds-check every access to the `blk' array
651 * of a `NumberlikeArray'.
653 * This gave me warnings that fell into two categories of false
654 * positives. The bounds checker was based on length, not
655 * capacity, and in two places I had accessed memory that I knew
656 * was inside the capacity but that wasn't inside the length:
658 * (1) The extra zero block at the left of `*this'. Earlier
659 * versions said `allocateAndCopy(len + 1); blk[len] = 0;'
660 * but did not increment `len'.
662 * (2) The entire digit array in the conversion constructor
663 * ``BigUnsignedInABase(BigUnsigned)''. It was allocated with
664 * a conservatively high capacity, but the length wasn't set
665 * until the end of the constructor.
667 * To simplify matters, I changed both sections of code so that
668 * all accesses occurred within the length. The messages went
669 * away, and I told Milan that I couldn't reproduce the problem,
670 * sending a development snapshot of the bounds-checked code.
672 * Then, on 2005.01.09-10, he told me his debugger still found
673 * problems, specifically at the line `delete [] work2'.
674 * It was `work2', not `blk', that was causing the problems;
675 * this possibility had not occurred to me at all. In fact,
676 * the problem was that `work2' needed an extra block just
677 * like `*this'. Go ahead and laugh at me for finding (1)
678 * without seeing what was actually causing the trouble. :-)
680 * The 2005.01.11 version fixes this problem. I hope this is
681 * the last of my memory-related bloopers. So this is what
682 * starts happening to your C++ code if you use Java too much!
686 void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
687 // Block unsafe calls
688 if (this == &a || this == &b)
689 throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
690 len = (a.len >= b.len) ? b.len : a.len;
693 for (i = 0; i < len; i++)
694 blk[i] = a.blk[i] & b.blk[i];
699 void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
700 // Block unsafe calls
701 if (this == &a || this == &b)
702 throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
704 const BigUnsigned *a2, *b2;
705 if (a.len >= b.len) {
713 for (i = 0; i < b2->len; i++)
714 blk[i] = a2->blk[i] | b2->blk[i];
715 for (; i < a2->len; i++)
721 void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
722 // Block unsafe calls
723 if (this == &a || this == &b)
724 throw "BigUnsigned::bitXor: One of the arguments is the invoked object";
726 const BigUnsigned *a2, *b2;
727 if (a.len >= b.len) {
735 for (i = 0; i < b2->len; i++)
736 blk[i] = a2->blk[i] ^ b2->blk[i];
737 for (; i < a2->len; i++)
743 // INCREMENT/DECREMENT OPERATORS
746 void BigUnsigned::operator ++() {
749 for (i = 0; i < len && carry; i++) {
751 carry = (blk[i] == 0);
754 // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
755 // Matt fixed another bug 2006.04.24:
756 // old number only has len blocks, so copy before increasing length
757 allocateAndCopy(len + 1);
763 // Postfix increment: same as prefix
764 void BigUnsigned::operator ++(int) {
769 void BigUnsigned::operator --() {
771 throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
774 for (i = 0; borrow; i++) {
775 borrow = (blk[i] == 0);
778 // Zap possible leading zero (there can only be one)
779 if (blk[len - 1] == 0)
783 // Postfix decrement: same as prefix
784 void BigUnsigned::operator --(int) {