1 #include "BigUnsigned.hh"
3 // Memory management definitions have moved to the bottom of NumberlikeArray.hh.
5 // CONSTRUCTION FROM PRIMITIVE INTEGERS
7 /* Initialize this BigUnsigned from the given primitive integer. The same
8 * pattern works for all primitive integer types, so I put it into a template to
9 * reduce code duplication. (Don't worry: this is protected and we instantiate
10 * it only with primitive integer types.) Type X could be signed, but x is
11 * known to be nonnegative. */
13 void BigUnsigned::initFromPrimitive(X x) {
15 ; // NumberlikeArray already initialized us to zero.
17 // Create a single block. blk is NULL; no need to delete it.
25 /* Ditto, but first check that x is nonnegative. I could have put the check in
26 * initFromPrimitive and let the compiler optimize it out for unsigned-type
27 * instantiations, but I wanted to avoid the warning stupidly issued by g++ for
28 * a condition that is constant in *any* instantiation, even if not in all. */
30 void BigUnsigned::initFromSignedPrimitive(X x) {
32 throw "BigUnsigned constructor: "
33 "Cannot construct a BigUnsigned from a negative number";
38 BigUnsigned::BigUnsigned(unsigned long x) { initFromPrimitive (x); }
39 BigUnsigned::BigUnsigned(unsigned int x) { initFromPrimitive (x); }
40 BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive (x); }
41 BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); }
42 BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); }
43 BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); }
45 // CONVERSION TO PRIMITIVE INTEGERS
47 /* Template with the same idea as initFromPrimitive. This might be slightly
48 * slower than the previous version with the masks, but it's much shorter and
49 * clearer, which is the library's stated goal. */
51 X BigUnsigned::convertToPrimitive() const {
53 // The number is zero; return zero.
56 // The single block might fit in an X. Try the conversion.
58 // Make sure the result accurately represents the block.
60 // Successful conversion.
62 // Otherwise fall through.
64 throw "BigUnsigned::to<Primitive>: "
65 "Value is too big to fit in the requested type";
68 /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result,
69 * not a negative one that happened to convert back into the correct nonnegative
70 * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again,
71 * separated to avoid a g++ warning. */
73 X BigUnsigned::convertToSignedPrimitive() const {
74 X x = convertToPrimitive<X>();
78 throw "BigUnsigned::to(Primitive): "
79 "Value is too big to fit in the requested type";
82 unsigned long BigUnsigned::toUnsignedLong() const {
83 return convertToPrimitive<unsigned long>();
85 unsigned int BigUnsigned::toUnsignedInt() const {
86 return convertToPrimitive<unsigned int>();
88 unsigned short BigUnsigned::toUnsignedShort() const {
89 return convertToPrimitive<unsigned short>();
91 long BigUnsigned::toLong() const {
92 return convertToSignedPrimitive<long>();
94 int BigUnsigned::toInt() const {
95 return convertToSignedPrimitive<int>();
97 short BigUnsigned::toShort() const {
98 return convertToSignedPrimitive<short>();
102 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
103 // A bigger length implies a bigger number.
106 else if (len > x.len)
109 // Compare blocks one by one from left to right.
113 if (blk[i] == x.blk[i])
115 else if (blk[i] > x.blk[i])
120 // If no blocks differed, the numbers are equal.
125 // COPY-LESS OPERATIONS
128 * On most calls to copy-less operations, it's safe to read the inputs little by
129 * little and write the outputs little by little. However, if one of the
130 * inputs is coming from the same variable into which the output is to be
131 * stored (an "aliased" call), we risk overwriting the input before we read it.
132 * In this case, we first compute the result into a temporary BigUnsigned
133 * variable and then copy it into the requested output variable *this.
134 * Each put-here operation uses the DTRT_ALIASED macro (Do The Right Thing on
135 * aliased calls) to generate code for this check.
137 * I adopted this approach on 2007.02.13 (see Assignment Operators in
138 * BigUnsigned.hh). Before then, put-here operations rejected aliased calls
139 * with an exception. I think doing the right thing is better.
141 * Some of the put-here operations can probably handle aliased calls safely
142 * without the extra copy because (for example) they process blocks strictly
143 * right-to-left. At some point I might determine which ones don't need the
144 * copy, but my reasoning would need to be verified very carefully. For now
145 * I'll leave in the copy.
147 #define DTRT_ALIASED(cond, op) \
149 BigUnsigned tmpThis; \
157 void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
158 DTRT_ALIASED(this == &a || this == &b, add(a, b));
159 // If one argument is zero, copy the other.
163 } else if (b.len == 0) {
168 // Carries in and out of an addition stage
169 bool carryIn, carryOut;
172 // a2 points to the longer input, b2 points to the shorter
173 const BigUnsigned *a2, *b2;
174 if (a.len >= b.len) {
181 // Set prelimiary length and make room in this BigUnsigned
184 // For each block index that is present in both inputs...
185 for (i = 0, carryIn = false; i < b2->len; i++) {
187 temp = a2->blk[i] + b2->blk[i];
188 // If a rollover occurred, the result is less than either input.
189 // This test is used many times in the BigUnsigned code.
190 carryOut = (temp < a2->blk[i]);
191 // If a carry was input, handle it
194 carryOut |= (temp == 0);
196 blk[i] = temp; // Save the addition result
197 carryIn = carryOut; // Pass the carry along
199 // If there is a carry left over, increase blocks until
200 // one does not roll over.
201 for (; i < a2->len && carryIn; i++) {
202 temp = a2->blk[i] + 1;
203 carryIn = (temp == 0);
206 // If the carry was resolved but the larger number
207 // still has blocks, copy them over.
208 for (; i < a2->len; i++)
210 // Set the extra block if there's still a carry, decrease length otherwise
217 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
218 DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
220 // If b is zero, copy a.
223 } else if (a.len < b.len)
224 // If a is shorter than b, the result is negative.
225 throw "BigUnsigned::subtract: "
226 "Negative result in unsigned calculation";
228 bool borrowIn, borrowOut;
231 // Set preliminary length and make room
234 // For each block index that is present in both inputs...
235 for (i = 0, borrowIn = false; i < b.len; i++) {
236 temp = a.blk[i] - b.blk[i];
237 // If a reverse rollover occurred,
238 // the result is greater than the block from a.
239 borrowOut = (temp > a.blk[i]);
240 // Handle an incoming borrow
242 borrowOut |= (temp == 0);
245 blk[i] = temp; // Save the subtraction result
246 borrowIn = borrowOut; // Pass the borrow along
248 // If there is a borrow left over, decrease blocks until
249 // one does not reverse rollover.
250 for (; i < a.len && borrowIn; i++) {
251 borrowIn = (a.blk[i] == 0);
252 blk[i] = a.blk[i] - 1;
254 /* If there's still a borrow, the result is negative.
255 * Throw an exception, but zero out this object so as to leave it in a
256 * predictable state. */
259 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
261 // Copy over the rest of the blocks
262 for (; i < a.len; i++)
269 * About the multiplication and division algorithms:
271 * I searched unsucessfully for fast C++ built-in operations like the `b_0'
272 * and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
273 * Programming'' (replace `place' by `Blk'):
275 * ``b_0[:] multiplication of a one-place integer by another one-place
276 * integer, giving a two-place answer;
278 * ``c_0[:] division of a two-place integer by a one-place integer,
279 * provided that the quotient is a one-place integer, and yielding
280 * also a one-place remainder.''
282 * I also missed his note that ``[b]y adjusting the word size, if
283 * necessary, nearly all computers will have these three operations
284 * available'', so I gave up on trying to use algorithms similar to his.
285 * A future version of the library might include such algorithms; I
286 * would welcome contributions from others for this.
288 * I eventually decided to use bit-shifting algorithms. To multiply `a'
289 * and `b', we zero out the result. Then, for each `1' bit in `a', we
290 * shift `b' left the appropriate amount and add it to the result.
291 * Similarly, to divide `a' by `b', we shift `b' left varying amounts,
292 * repeatedly trying to subtract it from `a'. When we succeed, we note
293 * the fact by setting a bit in the quotient. While these algorithms
294 * have the same O(n^2) time complexity as Knuth's, the ``constant factor''
295 * is likely to be larger.
297 * Because I used these algorithms, which require single-block addition
298 * and subtraction rather than single-block multiplication and division,
299 * the innermost loops of all four routines are very similar. Study one
300 * of them and all will become clear.
304 * This is a little inline function used by both the multiplication
305 * routine and the division routine.
307 * `getShiftedBlock' returns the `x'th block of `num << y'.
308 * `y' may be anything from 0 to N - 1, and `x' may be anything from
311 * Two things contribute to this block:
313 * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
315 * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
317 * But we must be careful if `x == 0' or `x == num.len', in
318 * which case we should use 0 instead of (2) or (1), respectively.
320 * If `y == 0', then (2) contributes 0, as it should. However,
321 * in some computer environments, for a reason I cannot understand,
322 * `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
323 * will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
324 * the test `y == 0' handles this case specially.
326 inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
327 BigUnsigned::Index x, unsigned int y) {
328 BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
329 BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
330 return part1 | part2;
333 void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
334 DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
335 // If either a or b is zero, set to zero.
336 if (a.len == 0 || b.len == 0) {
344 * For each 1-bit of `a' (say the `i2'th bit of block `i'):
345 * Add `b << (i blocks and i2 bits)' to *this.
347 // Variables for the calculation
351 bool carryIn, carryOut;
352 // Set preliminary length and make room
355 // Zero out this object
356 for (i = 0; i < len; i++)
358 // For each block of the first number...
359 for (i = 0; i < a.len; i++) {
360 // For each 1-bit of that block...
361 for (i2 = 0; i2 < N; i2++) {
362 if ((a.blk[i] & (Blk(1) << i2)) == 0)
365 * Add b to this, shifted left i blocks and i2 bits.
366 * j is the index in b, and k = i + j is the index in this.
368 * `getShiftedBlock', a short inline function defined above,
369 * is now used for the bit handling. It replaces the more
370 * complex `bHigh' code, in which each run of the loop dealt
371 * immediately with the low bits and saved the high bits to
372 * be picked up next time. The last run of the loop used to
373 * leave leftover high bits, which were handled separately.
374 * Instead, this loop runs an additional time with j == b.len.
375 * These changes were made on 2005.01.11.
377 for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
379 * The body of this loop is very similar to the body of the first loop
380 * in `add', except that this loop does a `+=' instead of a `+'.
382 temp = blk[k] + getShiftedBlock(b, j, i2);
383 carryOut = (temp < blk[k]);
386 carryOut |= (temp == 0);
391 // No more extra iteration to deal with `bHigh'.
392 // Roll-over a carry as necessary.
393 for (; carryIn; k++) {
395 carryIn = (blk[k] == 0);
399 // Zap possible leading zero
400 if (blk[len - 1] == 0)
405 * DIVISION WITH REMAINDER
406 * This monstrous function mods *this by the given divisor b while storing the
407 * quotient in the given object q; at the end, *this contains the remainder.
408 * The seemingly bizarre pattern of inputs and outputs was chosen so that the
409 * function copies as little as possible (since it is implemented by repeated
410 * subtraction of multiples of b from *this).
412 * "modWithQuotient" might be a better name for this function, but I would
413 * rather not change the name now.
415 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
416 /* Defending against aliased calls is more complex than usual because we
417 * are writing to both *this and q.
419 * It would be silly to try to write quotient and remainder to the
420 * same variable. Rule that out right away. */
422 throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable";
423 /* Now *this and q are separate, so the only concern is that b might be
424 * aliased to one of them. If so, use a temporary copy of b. */
425 if (this == &b || &q == &b) {
427 divideWithRemainder(tmpB, q);
432 * Knuth's definition of mod (which this function uses) is somewhat
433 * different from the C++ definition of % in case of division by 0.
435 * We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no
436 * exceptions thrown. This allows us to preserve both Knuth's demand
437 * that a mod 0 == a and the useful property that
438 * (a / b) * b + (a % b) == a.
446 * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
447 * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
454 // At this point we know (*this).len >= b.len > 0. (Whew!)
459 * For each appropriate i and i2, decreasing:
460 * Subtract (b << (i blocks and i2 bits)) from *this, storing the
461 * result in subtractBuf.
462 * If the subtraction succeeds with a nonnegative result:
463 * Turn on bit i2 of block i of the quotient q.
464 * Copy subtractBuf back into *this.
465 * Otherwise bit i2 of block i remains off, and *this is unchanged.
467 * Eventually q will contain the entire quotient, and *this will
468 * be left with the remainder.
470 * subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
471 * But on a single iteration, we don't touch the i lowest blocks of blk
472 * (and don't use those of subtractBuf) because these blocks are
473 * unaffected by the subtraction: we are subtracting
474 * (b << (i blocks and i2 bits)), which ends in at least `i' zero
476 // Variables for the calculation
480 bool borrowIn, borrowOut;
483 * Make sure we have an extra zero block just past the value.
485 * When we attempt a subtraction, we might shift `b' so
486 * its first block begins a few bits left of the dividend,
487 * and then we'll try to compare these extra bits with
488 * a nonexistent block to the left of the dividend. The
489 * extra zero block ensures sensible behavior; we need
490 * an extra block in `subtractBuf' for exactly the same reason.
492 Index origLen = len; // Save real length.
493 /* To avoid an out-of-bounds access in case of reallocation, allocate
494 * first and then increment the logical length. */
495 allocateAndCopy(len + 1);
497 blk[origLen] = 0; // Zero the added block.
499 // subtractBuf holds part of the result of a subtraction; see above.
500 Blk *subtractBuf = new Blk[len];
502 // Set preliminary length for quotient and make room
503 q.len = origLen - b.len + 1;
505 // Zero out the quotient
506 for (i = 0; i < q.len; i++)
509 // For each possible left-shift of b in blocks...
513 // For each possible left-shift of b in bits...
514 // (Remember, N is the number of bits in a Blk.)
520 * Subtract b, shifted left i blocks and i2 bits, from *this,
521 * and store the answer in subtractBuf. In the for loop, `k == i + j'.
523 * Compare this to the middle section of `multiply'. They
524 * are in many ways analogous. See especially the discussion
525 * of `getShiftedBlock'.
527 for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
528 temp = blk[k] - getShiftedBlock(b, j, i2);
529 borrowOut = (temp > blk[k]);
531 borrowOut |= (temp == 0);
534 // Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'.
535 subtractBuf[k] = temp;
536 borrowIn = borrowOut;
538 // No more extra iteration to deal with `bHigh'.
539 // Roll-over a borrow as necessary.
540 for (; k < origLen && borrowIn; k++) {
541 borrowIn = (blk[k] == 0);
542 subtractBuf[k] = blk[k] - 1;
545 * If the subtraction was performed successfully (!borrowIn),
546 * set bit i2 in block i of the quotient.
548 * Then, copy the portion of subtractBuf filled by the subtraction
549 * back to *this. This portion starts with block i and ends--
550 * where? Not necessarily at block `i + b.len'! Well, we
551 * increased k every time we saved a block into subtractBuf, so
552 * the region of subtractBuf we copy is just [i, k).
555 q.blk[i] |= (Blk(1) << i2);
558 blk[k] = subtractBuf[k];
563 // Zap possible leading zero in quotient
564 if (q.blk[q.len - 1] == 0)
566 // Zap any/all leading zeros in remainder
568 // Deallocate subtractBuf.
569 // (Thanks to Brad Spencer for noticing my accidental omission of this!)
570 delete [] subtractBuf;
574 * These are straightforward blockwise operations except that they differ in
575 * the output length and the necessity of zapLeadingZeros. */
577 void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
578 DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
579 // The bitwise & can't be longer than either operand.
580 len = (a.len >= b.len) ? b.len : a.len;
583 for (i = 0; i < len; i++)
584 blk[i] = a.blk[i] & b.blk[i];
588 void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
589 DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
591 const BigUnsigned *a2, *b2;
592 if (a.len >= b.len) {
600 for (i = 0; i < b2->len; i++)
601 blk[i] = a2->blk[i] | b2->blk[i];
602 for (; i < a2->len; i++)
605 // Doesn't need zapLeadingZeros.
608 void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
609 DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
611 const BigUnsigned *a2, *b2;
612 if (a.len >= b.len) {
620 for (i = 0; i < b2->len; i++)
621 blk[i] = a2->blk[i] ^ b2->blk[i];
622 for (; i < a2->len; i++)
628 void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) {
629 DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
632 throw "BigUnsigned::bitShiftLeft: "
633 "Pathological shift amount not implemented";
635 bitShiftRight(a, -b);
639 Index shiftBlocks = b / N;
640 unsigned int shiftBits = b % N;
641 // + 1: room for high bits nudged left into another block
642 len = a.len + shiftBlocks + 1;
645 for (i = 0; i < shiftBlocks; i++)
647 for (j = 0, i = shiftBlocks; j <= a.len; j++, i++)
648 blk[i] = getShiftedBlock(a, j, shiftBits);
649 // Zap possible leading zero
650 if (blk[len - 1] == 0)
654 void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) {
655 DTRT_ALIASED(this == &a, bitShiftRight(a, b));
658 throw "BigUnsigned::bitShiftRight: "
659 "Pathological shift amount not implemented";
665 // This calculation is wacky, but expressing the shift as a left bit shift
666 // within each block lets us use getShiftedBlock.
667 Index rightShiftBlocks = (b + N - 1) / N;
668 unsigned int leftShiftBits = N * rightShiftBlocks - b;
669 // Now (N * rightShiftBlocks - leftShiftBits) == b
670 // and 0 <= leftShiftBits < N.
671 if (rightShiftBlocks >= a.len + 1) {
672 // All of a is guaranteed to be shifted off, even considering the left
677 // Now we're allocating a positive amount.
678 // + 1: room for high bits nudged left into another block
679 len = a.len + 1 - rightShiftBlocks;
682 for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++)
683 blk[i] = getShiftedBlock(a, j, leftShiftBits);
684 // Zap possible leading zero
685 if (blk[len - 1] == 0)
689 // INCREMENT/DECREMENT OPERATORS
692 void BigUnsigned::operator ++() {
695 for (i = 0; i < len && carry; i++) {
697 carry = (blk[i] == 0);
700 // Allocate and then increase length, as in divideWithRemainder
701 allocateAndCopy(len + 1);
707 // Postfix increment: same as prefix
708 void BigUnsigned::operator ++(int) {
713 void BigUnsigned::operator --() {
715 throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
718 for (i = 0; borrow; i++) {
719 borrow = (blk[i] == 0);
722 // Zap possible leading zero (there can only be one)
723 if (blk[len - 1] == 0)
727 // Postfix decrement: same as prefix
728 void BigUnsigned::operator --(int) {