2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
6 #include "BigUnsigned.hh"
8 // The "management" routines that used to be here are now in NumberlikeArray.hh.
11 * The steps for construction of a BigUnsigned
12 * from an integral value x are as follows:
13 * 1. If x is zero, create an empty BigUnsigned and stop.
14 * 2. If x is negative, throw an exception.
15 * 3. Allocate a one-block number array.
16 * 4. If x is of a signed type, convert x to the unsigned
17 * type of the same length.
18 * 5. Expand x to a Blk, and store it in the number array.
20 * Since 2005.01.06, NumberlikeArray uses `NULL' rather
21 * than a real array if one of zero length is needed.
22 * These constructors implicitly call NumberlikeArray's
23 * default constructor, which sets `blk = NULL, cap = len = 0'.
24 * So if the input number is zero, they can just return.
25 * See remarks in `NumberlikeArray.hh'.
28 BigUnsigned::BigUnsigned(unsigned long x) {
30 ; // NumberlikeArray already did all the work
39 BigUnsigned::BigUnsigned(long x) {
48 throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
51 BigUnsigned::BigUnsigned(unsigned int x) {
62 BigUnsigned::BigUnsigned(int x) {
71 throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
74 BigUnsigned::BigUnsigned(unsigned short x) {
85 BigUnsigned::BigUnsigned(short x) {
94 throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
99 * The steps for conversion of a BigUnsigned to an
100 * integral type are as follows:
101 * 1. If the BigUnsigned is zero, return zero.
102 * 2. If it is more than one block long or its lowest
103 * block has bits set out of the range of the target
104 * type, throw an exception.
105 * 3. Otherwise, convert the lowest block to the
106 * target type and return it.
110 // These masks are used to test whether a Blk has bits
111 // set out of the range of a smaller integral type. Note
112 // that this range is not considered to include the sign bit.
113 const BigUnsigned::Blk lMask = ~0 >> 1;
114 const BigUnsigned::Blk uiMask = (unsigned int)(~0);
115 const BigUnsigned::Blk iMask = uiMask >> 1;
116 const BigUnsigned::Blk usMask = (unsigned short)(~0);
117 const BigUnsigned::Blk sMask = usMask >> 1;
120 BigUnsigned::operator unsigned long() const {
124 return (unsigned long) blk[0];
126 throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
129 BigUnsigned::operator long() const {
132 else if (len == 1 && (blk[0] & lMask) == blk[0])
133 return (long) blk[0];
135 throw "BigUnsigned::operator long: Value is too big for a long";
138 BigUnsigned::operator unsigned int() const {
141 else if (len == 1 && (blk[0] & uiMask) == blk[0])
142 return (unsigned int) blk[0];
144 throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
147 BigUnsigned::operator int() const {
150 else if (len == 1 && (blk[0] & iMask) == blk[0])
153 throw "BigUnsigned::operator int: Value is too big for an int";
156 BigUnsigned::operator unsigned short() const {
159 else if (len == 1 && (blk[0] & usMask) == blk[0])
160 return (unsigned short) blk[0];
162 throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
165 BigUnsigned::operator short() const {
168 else if (len == 1 && (blk[0] & sMask) == blk[0])
169 return (short) blk[0];
171 throw "BigUnsigned::operator short: Value is too big for a short";
175 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
176 // A bigger length implies a bigger number.
179 else if (len > x.len)
182 // Compare blocks one by one from left to right.
186 if (blk[i] == x.blk[i])
188 else if (blk[i] > x.blk[i])
193 // If no blocks differed, the numbers are equal.
198 // PUT-HERE OPERATIONS
201 void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
202 // Block unsafe calls
203 if (this == &a || this == &b)
204 throw "BigUnsigned::add: One of the arguments is the invoked object";
205 // If one argument is zero, copy the other.
209 } else if (b.len == 0) {
213 // Carries in and out of an addition stage
214 bool carryIn, carryOut;
217 // a2 points to the longer input, b2 points to the shorter
218 const BigUnsigned *a2, *b2;
219 if (a.len >= b.len) {
226 // Set prelimiary length and make room in this BigUnsigned
229 // For each block index that is present in both inputs...
230 for (i = 0, carryIn = false; i < b2->len; i++) {
232 temp = a2->blk[i] + b2->blk[i];
233 // If a rollover occurred, the result is less than either input.
234 // This test is used many times in the BigUnsigned code.
235 carryOut = (temp < a2->blk[i]);
236 // If a carry was input, handle it
239 carryOut |= (temp == 0);
241 blk[i] = temp; // Save the addition result
242 carryIn = carryOut; // Pass the carry along
244 // If there is a carry left over, increase blocks until
245 // one does not roll over.
246 for (; i < a2->len && carryIn; i++) {
247 temp = a2->blk[i] + 1;
248 carryIn = (temp == 0);
251 // If the carry was resolved but the larger number
252 // still has blocks, copy them over.
253 for (; i < a2->len; i++)
255 // Set the extra block if there's still a carry, decrease length otherwise
263 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
264 // Block unsafe calls
265 if (this == &a || this == &b)
266 throw "BigUnsigned::subtract: One of the arguments is the invoked object";
267 // If b is zero, copy a. If a is shorter than b, the result is negative.
271 } else if (a.len < b.len)
272 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
273 bool borrowIn, borrowOut;
276 // Set preliminary length and make room
279 // For each block index that is present in both inputs...
280 for (i = 0, borrowIn = false; i < b.len; i++) {
281 temp = a.blk[i] - b.blk[i];
282 // If a reverse rollover occurred, the result is greater than the block from a.
283 borrowOut = (temp > a.blk[i]);
284 // Handle an incoming borrow
286 borrowOut |= (temp == 0);
289 blk[i] = temp; // Save the subtraction result
290 borrowIn = borrowOut; // Pass the borrow along
292 // If there is a borrow left over, decrease blocks until
293 // one does not reverse rollover.
294 for (; i < a.len && borrowIn; i++) {
295 borrowIn = (a.blk[i] == 0);
296 blk[i] = a.blk[i] - 1;
298 // If there's still a borrow, the result is negative.
299 // Throw an exception, but zero out this object first just in case.
302 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
303 } else // Copy over the rest of the blocks
304 for (; i < a.len; i++)
311 void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
312 // Block unsafe calls
313 if (this == &a || this == &b)
314 throw "BigUnsigned::multiply: One of the arguments is the invoked object";
315 // If either a or b is zero, set to zero.
316 if (a.len == 0 || b.len == 0) {
320 // Overall method: this = 0, then for each 1-bit of a, add b
321 // to this shifted the appropriate amount.
322 // Variables for the calculation
325 Blk aBlk, bHigh, temp;
326 bool carryIn, carryOut;
327 // Set preliminary length and make room
330 // Zero out this object
331 for (i = 0; i < len; i++)
333 // For each block of the first number...
334 for (i = 0; i < a.len; i++) {
335 // For each 1-bit of that block...
336 for (i2 = 0, aBlk = a.blk[i]; aBlk != 0; i2++, aBlk >>= 1) {
339 /* Add b to this, shifted left i blocks and i2 bits.
340 * j is the index in b, and k = i + j is the index in this.
341 * The low bits of b.blk[j] are shifted and added to blk[k].
342 * bHigh is used to carry the high bits to the next addition. */
344 for (j = 0, k = i, carryIn = false; j < b.len; j++, k++) {
345 temp = blk[k] + ((b.blk[j] << i2) | bHigh);
346 carryOut = (temp < blk[k]);
349 carryOut |= (temp == 0);
353 bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
355 temp = blk[k] + bHigh;
356 carryOut = (temp < blk[k]);
359 carryOut |= (temp == 0);
363 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.
364 for (; carryIn; k++) {
366 carryIn = (blk[k] == 0);
370 // Zap possible leading zero
371 if (blk[len - 1] == 0)
376 * DIVISION WITH REMAINDER
377 * The functionality of divide, modulo, and %= is included in this one monstrous call,
378 * which deserves some explanation.
380 * The division *this / b is performed.
381 * Afterwards, q has the quotient, and *this has the remainder.
382 * Thus, a call is like q = *this / b, *this %= b.
384 * This seemingly bizarre pattern of inputs and outputs has a justification. The
385 * ``put-here operations'' are supposed to be fast. Therefore, they accept inputs
386 * and provide outputs in the most convenient places so that no value ever needs
387 * to be copied in its entirety. That way, the client can perform exactly the
388 * copying it needs depending on where the inputs are and where it wants the output.
390 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
391 // Block unsafe calls
392 if (this == &b || &q == &b || this == &q)
393 throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
396 * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
397 * different from the way the normal C++ % operator behaves in the case of division by 0.
398 * This function does it Knuth's way.
400 * We let a / 0 == 0 (it doesn't matter) and a % 0 == a, no exceptions thrown.
401 * This allows us to preserve both Knuth's demand that a mod 0 == a
402 * and the useful property that (a / b) * b + (a % b) == a.
410 * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
411 * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone).
419 * At this point we know *this > b > 0. (Whew!)
423 std::cout << "divideWithRemainder starting\n"
424 << "length of dividend: " << len
425 << "\nlast block of dividend: " << getBlock(0)
426 << "\nlength of divisor: " << b.len
427 << "\nlast block of divisor: " << b.getBlock(0)
431 * Overall method: Subtract b, shifted varying amounts to
432 * the left, from this, setting the bit in the quotient q
433 * whenever the subtraction succeeds. Eventually q will contain the entire
434 * quotient, and this will be left with the remainder.
436 * We use work2 to temporarily store the result of a subtraction.
437 * But we don't even compute the i lowest blocks of the result,
438 * because they are unaffected (we shift left i places).
440 // Variables for the calculation
444 bool borrowIn, borrowOut;
446 // Make sure we have an extra zero block just past the value,
447 // but don't increase the logical length. A shifted subtraction
448 // (for example, subtracting 1 << 2 from 4) might stick into
450 allocateAndCopy(len + 1);
453 // work2 holds part of the result of a subtraction.
454 // (There's no work1. The name work2 is from a previous version.)
455 Blk *work2 = new Blk[len];
457 // Set preliminary length for quotient and make room
458 q.len = len - b.len + 1;
460 // Zero out the quotient
461 for (i = 0; i < q.len; i++)
464 // For each possible left-shift of b in blocks...
468 // For each possible left-shift of b in bits...
470 i2 = 8 * sizeof(Blk);
474 * Subtract b, shifted left i blocks and i2 bits, from this.
475 * and store the answer in work2.
477 * Compare this to the middle section of `multiply'. They
478 * are in many ways analogous.
481 for (j = 0, k = i, borrowIn = false; j < b.len; j++, k++) {
482 temp = blk[k] - ((b.blk[j] << i2) | bHigh);
483 borrowOut = (temp > blk[k]);
485 borrowOut |= (temp == 0);
489 borrowIn = borrowOut;
490 bHigh = (i2 == 0) ? 0 : b.blk[j] >> (8 * sizeof(Blk) - i2);
492 temp = blk[k] - bHigh;
493 borrowOut = (temp > blk[k]);
495 borrowOut |= (temp == 0);
499 borrowIn = borrowOut;
502 for (; k < len && borrowIn; j++, k++) {
503 borrowIn = (blk[k] == 0);
504 work2[j] = blk[k] - 1;
506 /* If the subtraction was performed successfully (!borrowIn), set bit i2
507 * in block i of the quotient, and copy the changed portion of
508 * work2 back to this. Otherwise, reset that bit and move on. */
510 q.blk[i] |= (1 << i2);
519 // Zap possible leading zero in quotient
520 if (q.blk[q.len - 1] == 0)
522 // Zap any/all leading zeros in remainder
524 // Deallocate temporary array.
525 // (Thanks to Brad Spencer for noticing my accidental omission of this!)
529 std::cout << "divideWithRemainder complete\n"
530 << "length of quotient: " << q.len
531 << "\nlast block of quotient: " << q.getBlock(0)
532 << "\nlength of remainder: " << len
533 << "\nlast block of remainder: " << getBlock(0)
538 void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
539 // Block unsafe calls
540 if (this == &a || this == &b)
541 throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
542 len = (a.len >= b.len) ? b.len : a.len;
545 for (i = 0; i < len; i++)
546 blk[i] = a.blk[i] & b.blk[i];
551 void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
552 // Block unsafe calls
553 if (this == &a || this == &b)
554 throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
556 const BigUnsigned *a2, *b2;
557 if (a.len >= b.len) {
565 for (i = 0; i < b2->len; i++)
566 blk[i] = a2->blk[i] | b2->blk[i];
567 for (; i < a2->len; i++)
573 void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
574 // Block unsafe calls
575 if (this == &a || this == &b)
576 throw "BigUnsigned::bitXor: One of the arguments is the invoked object";
578 const BigUnsigned *a2, *b2;
579 if (a.len >= b.len) {
587 for (i = 0; i < b2->len; i++)
588 blk[i] = a2->blk[i] ^ b2->blk[i];
589 for (; i < a2->len; i++)
595 // INCREMENT/DECREMENT OPERATORS
598 void BigUnsigned::operator ++() {
601 for (i = 0; i < len && carry; i++) {
603 carry = (blk[i] == 0);
606 // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
608 allocateAndCopy(len);
613 // Postfix increment: same as prefix
614 void BigUnsigned::operator ++(int) {
619 void BigUnsigned::operator --() {
621 throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
624 for (i = 0; borrow; i++) {
625 borrow = (blk[i] == 0);
628 // Zap possible leading zero (there can only be one)
629 if (blk[len - 1] == 0)
633 // Postfix decrement: same as prefix
634 void BigUnsigned::operator --(int) {