BigInteger.cc

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   6 #include "BigInteger.hh"
   7
   8 // MANAGEMENT
   9
  10 // Assignment operator
  11 void BigInteger::operator =(const BigInteger &x) {
  12         // Calls like a = a have no effect
  13         if (this == &x)
  14                 return;
  15         // Copy sign
  16         sign = x.sign;
  17         // Copy the rest
  18         BigUnsigned::operator =(x);
  19 }
  20
  21 // Constructor from an array of blocks and a sign
  22 BigInteger::BigInteger(const Blk *b, Index l, Sign s) : BigUnsigned(b, l) {
  23         switch (s) {
  24                 case zero:
  25                 case positive:
  26                 case negative:
  27                 sign = (len == 0) ? zero : s;
  28                 break;
  29                 default:
  30                 throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
  31         }
  32 }
  33
  34 // Constructor from a BigUnsigned and a sign
  35 BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) {
  36         switch (s) {
  37                 case zero:
  38                 case positive:
  39                 case negative:
  40                 sign = (len == 0) ? zero : s;
  41                 break;
  42                 default:
  43                 throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
  44         }
  45 }
  46
  47 /*
  48 * The steps for construction of a BigInteger
  49 * from an integral value x are as follows:
  50 * 1. If x is zero, create an empty BigInteger and stop.
  51 * 2. Allocate a one-block number array.
  52 * 3. If x is positive (or of an unsigned type), set the
  53 *    sign of the BigInteger to positive.
  54 * 4. If x is of a signed type and is negative, set the
  55 *    sign of the BigInteger to negative.
  56 * 5. If x is of a signed type, convert x (or -x if x < 0)
  57 *    to the unsigned type of the same length.
  58 * 6. Expand x (or the result of step 5) to a Blk,
  59 *    and store it in the number array.
  60 *
  61 * See remarks in `BigUnsigned.cc' and `NumberlikeArray.hh'
  62 * about new handling of zero-length arrays.
  63 */
  64
  65 BigInteger::BigInteger(unsigned long x) {
  66         if (x == 0)
  67                 sign = zero; // NumberlikeArray did the rest
  68         else {
  69                 cap = 1;
  70                 blk = new Blk[1];
  71                 sign = positive;
  72                 len = 1;
  73                 blk[0] = Blk(x);
  74         }
  75 }
  76
  77 BigInteger::BigInteger(long x) {
  78         if (x > 0) {
  79                 cap = 1;
  80                 blk = new Blk[1];
  81                 sign = positive;
  82                 len = 1;
  83                 blk[0] = Blk(x);
  84         } else if (x < 0) {
  85                 cap = 1;
  86                 blk = new Blk[1];
  87                 sign = negative;
  88                 len = 1;
  89                 blk[0] = Blk(-x);
  90         } else
  91         sign = zero;
  92 }
  93
  94 BigInteger::BigInteger(unsigned int x) {
  95         if (x == 0)
  96                 sign = zero;
  97         else {
  98                 cap = 1;
  99                 blk = new Blk[1];
 100                 sign = positive;
 101                 len = 1;
 102                 blk[0] = Blk(x);
 103         }
 104 }
 105
 106 BigInteger::BigInteger(int x) {
 107         if (x > 0) {
 108                 cap = 1;
 109                 blk = new Blk[1];
 110                 sign = positive;
 111                 len = 1;
 112                 blk[0] = Blk(x);
 113         } else if (x < 0) {
 114                 cap = 1;
 115                 blk = new Blk[1];
 116                 sign = negative;
 117                 len = 1;
 118                 blk[0] = Blk(-x);
 119         } else
 120         sign = zero;
 121 }
 122
 123 BigInteger::BigInteger(unsigned short x) {
 124         if (x == 0)
 125                 sign = zero;
 126         else {
 127                 cap = 1;
 128                 blk = new Blk[1];
 129                 sign = positive;
 130                 len = 1;
 131                 blk[0] = Blk(x);
 132         }
 133 }
 134
 135 BigInteger::BigInteger(short x) {
 136         if (x > 0) {
 137                 cap = 1;
 138                 blk = new Blk[1];
 139                 sign = positive;
 140                 len = 1;
 141                 blk[0] = Blk(x);
 142         } else if (x < 0) {
 143                 cap = 1;
 144                 blk = new Blk[1];
 145                 sign = negative;
 146                 len = 1;
 147                 blk[0] = Blk(-x);
 148         } else
 149         sign = zero;
 150 }
 151
 152 // CONVERTERS
 153 /*
 154 * The steps for conversion of a BigInteger to an
 155 * integral type are as follows:
 156 * 1. If the BigInteger is zero, return zero.
 157 * 2. If the BigInteger is positive:
 158 *    3. If it is more than one block long or its lowest
 159 *       block has bits set out of the range of the target
 160 *       type, throw an exception.
 161 *    4. Otherwise, convert the lowest block to the
 162 *       target type and return it.
 163 * 5. If the BigInteger is negative:
 164 *    6. If the target type is unsigned, throw an exception.
 165 *    7. If it is more than one block long or its lowest
 166 *       block has bits set out of the range of the target
 167 *       type, throw an exception.
 168 *    8. Otherwise, convert the lowest block to the
 169 *       target type, negate it, and return it.
 170 */
 171
 172 namespace {
 173         // These masks are used to test whether a Blk has bits
 174         // set out of the range of a smaller integral type.  Note
 175         // that this range is not considered to include the sign bit.
 176         const BigUnsigned::Blk  lMask = ~0 >> 1;
 177         const BigUnsigned::Blk uiMask = (unsigned int)(~0);
 178         const BigUnsigned::Blk  iMask = uiMask >> 1;
 179         const BigUnsigned::Blk usMask = (unsigned short)(~0);
 180         const BigUnsigned::Blk  sMask = usMask >> 1;
 181 }
 182
 183 BigInteger::operator unsigned long() const {
 184         switch (sign) {
 185                 case zero:
 186                 return 0;
 187                 case positive:
 188                 if (len == 1)
 189                         return blk[0];
 190                 else
 191                         throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long";
 192                 case negative:
 193                 throw "BigInteger operator unsigned long() const: Cannot convert a negative integer to an unsigned type";
 194                 default:
 195                 throw "BigInteger: Internal error";
 196         }
 197 }
 198
 199 BigInteger::operator long() const {
 200         switch (sign) {
 201                 case zero:
 202                 return 0;
 203                 case positive:
 204                 if (len == 1 && (blk[0] & ~lMask) == 0)
 205                         return long(blk[0]);
 206                 else
 207                         throw "BigInteger operator long() const: Value is too big for a long";
 208                 case negative:
 209                 if (len == 1 && (blk[0] & ~lMask) == 0)
 210                         return -long(blk[0]);
 211                 else
 212                         throw "BigInteger operator long() const: Value is too big for a long";
 213                 default:
 214                 throw "BigInteger: Internal error";
 215         }
 216 }
 217
 218 BigInteger::operator unsigned int() const {
 219         switch (sign) {
 220                 case zero:
 221                 return 0;
 222                 case positive:
 223                 if (len == 1 && (blk[0] & ~uiMask) == 0)
 224                         return (unsigned int)(blk[0]);
 225                 else
 226                         throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int";
 227                 case negative:
 228                 throw "BigInteger operator unsigned int() const: Cannot convert a negative integer to an unsigned type";
 229                 default:
 230                 throw "BigInteger: Internal error";
 231         }
 232 }
 233
 234 BigInteger::operator int() const {
 235         switch (sign) {
 236                 case zero:
 237                 return 0;
 238                 case positive:
 239                 if (len == 1 && (blk[0] & ~iMask) == 0)
 240                         return int(blk[0]);
 241                 else
 242                         throw "BigInteger operator int() const: Value is too big for an int";
 243                 case negative:
 244                 if (len == 1 && (blk[0] & ~iMask) == 0)
 245                         return -int(blk[0]);
 246                 else
 247                         throw "BigInteger operator int() const: Value is too big for an int";
 248                 default:
 249                 throw "BigInteger: Internal error";
 250         }
 251 }
 252
 253 BigInteger::operator unsigned short() const {
 254         switch (sign) {
 255                 case zero:
 256                 return 0;
 257                 case positive:
 258                 if (len == 1 && (blk[0] & ~usMask) == 0)
 259                         return (unsigned short)(blk[0]);
 260                 else
 261                         throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short";
 262                 case negative:
 263                 throw "BigInteger operator unsigned short() const: Cannot convert a negative integer to an unsigned type";
 264                 default:
 265                 throw "BigInteger: Internal error";
 266         }
 267 }
 268
 269 BigInteger::operator short() const {
 270         switch (sign) {
 271                 case zero:
 272                 return 0;
 273                 case positive:
 274                 if (len == 1 && (blk[0] & ~sMask) == 0)
 275                         return short(blk[0]);
 276                 else
 277                         throw "BigInteger operator short() const: Value is too big for a short";
 278                 case negative:
 279                 if (len == 1 && (blk[0] & ~sMask) == 0)
 280                         return -short(blk[0]);
 281                 else
 282                         throw "BigInteger operator short() const: Value is too big for a short";
 283                 default:
 284                 throw "BigInteger: Internal error";
 285         }
 286 }
 287
 288 // COMPARISON
 289 BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
 290         // A greater sign implies a greater number
 291         if (sign < x.sign)
 292                 return less;
 293         else if (sign > x.sign)
 294                 return greater;
 295         else switch (sign) {
 296                 // If the signs are the same...
 297                 case zero:
 298                 return equal; // Two zeros are equal
 299                 case positive:
 300                 // Compare the magnitudes
 301                 return BigUnsigned::compareTo(x);
 302                 case negative:
 303                 // Compare the magnitudes, but return the opposite result
 304                 return CmpRes(-BigUnsigned::compareTo(x));
 305                 default:
 306                 throw "BigInteger: Internal error";
 307         }
 308 }
 309
 310 // PUT-HERE OPERATIONS
 311 // These do some messing around to determine the sign of the result,
 312 // then call one of BigUnsigned's put-heres.
 313
 314 // Addition
 315 void BigInteger::add(const BigInteger &a, const BigInteger &b) {
 316         // Block unsafe calls
 317         if (this == &a || this == &b)
 318                 throw "BigInteger::add: One of the arguments is the invoked object";
 319         // If one argument is zero, copy the other.
 320         if (a.sign == zero)
 321                 operator =(b);
 322         else if (b.sign == zero)
 323                 operator =(a);
 324         // If the arguments have the same sign, take the
 325         // common sign and add their magnitudes.
 326         else if (a.sign == b.sign) {
 327                 sign = a.sign;
 328                 BigUnsigned::add(a, b);
 329         } else {
 330                 // Otherwise, their magnitudes must be compared.
 331                 switch (a.BigUnsigned::compareTo(b)) {
 332                         // If their magnitudes are the same, copy zero.
 333                         case equal:
 334                         len = 0;
 335                         sign = zero;
 336                         break;
 337                         // Otherwise, take the sign of the greater, and subtract
 338                         // the lesser magnitude from the greater magnitude.
 339                         case greater:
 340                         sign = a.sign;
 341                         BigUnsigned::subtract(a, b);
 342                         break;
 343                         case less:
 344                         sign = b.sign;
 345                         BigUnsigned::subtract(b, a);
 346                         break;
 347                 }
 348         }
 349 }
 350
 351 // Subtraction
 352 void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
 353         // Notice that this routine is identical to BigInteger::add,
 354         // if one replaces b.sign by its opposite.
 355         // Block unsafe calls
 356         if (this == &a || this == &b)
 357                 throw "BigInteger::subtract: One of the arguments is the invoked object";
 358         // If a is zero, copy b and flip its sign.  If b is zero, copy a.
 359         if (a.sign == zero) {
 360                 BigUnsigned::operator =(b);
 361                 sign = Sign(-sign);
 362         } else if (b.sign == zero)
 363     operator =(a);
 364         // If their signs differ, take a.sign and add the magnitudes.
 365         else if (a.sign != b.sign) {
 366                 sign = a.sign;
 367                 BigUnsigned::add(a, b);
 368         } else {
 369                 // Otherwise, their magnitudes must be compared.
 370                 switch (a.BigUnsigned::compareTo(b)) {
 371                         // If their magnitudes are the same, copy zero.
 372                         case equal:
 373                         len = 0;
 374                         sign = zero;
 375                         break;
 376                         // If a's magnitude is greater, take a.sign and
 377                         // subtract a from b.
 378                         case greater:
 379                         sign = a.sign;
 380                         BigUnsigned::subtract(a, b);
 381                         break;
 382                         // If b's magnitude is greater, take the opposite
 383                         // of b.sign and subtract b from a.
 384                         case less:
 385                         sign = Sign(-b.sign);
 386                         BigUnsigned::subtract(b, a);
 387                         break;
 388                 }
 389         }
 390 }
 391
 392 // Multiplication
 393 void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
 394         // Block unsafe calls
 395         if (this == &a || this == &b)
 396                 throw "BigInteger::multiply: One of the arguments is the invoked object";
 397         // If one object is zero, copy zero and return.
 398         if (a.sign == zero || b.sign == zero) {
 399                 sign = zero;
 400                 len = 0;
 401                 return;
 402         }
 403         // If the signs of the arguments are the same, the result
 404         // is positive, otherwise it is negative.
 405         sign = (a.sign == b.sign) ? positive : negative;
 406         // Multiply the magnitudes.
 407         BigUnsigned::multiply(a, b);
 408 }
 409
 410 /*
 411 * DIVISION WITH REMAINDER
 412 * Please read the comments before the definition of
 413 * `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
 414 * information you should know before reading this function.
 415 *
 416 * Following Knuth, I decree that x / y is to be
 417 * 0 if y==0 and floor(real-number x / y) if y!=0.
 418 * Then x % y shall be x - y*(integer x / y).
 419 *
 420 * Note that x = y * (x / y) + (x % y) always holds.
 421 * In addition, (x % y) is from 0 to y - 1 if y > 0,
 422 * and from -(|y| - 1) to 0 if y < 0.  (x % y) = x if y = 0.
 423 *
 424 * Examples: (q = a / b, r = a % b)
 425 *       a       b       q       r
 426 *       ===     ===     ===     ===
 427 *       4       3       1       1
 428 *       -4      3       -2      2
 429 *       4       -3      -2      -2
 430 *       -4      -3      1       -1
 431 */
 432 void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
 433         // Block unsafe calls
 434         if (this == &b || this == &q || &b == &q)
 435                 throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object";
 436         // Division by zero gives quotient 0 and remainder *this
 437         if (b.sign == zero) {
 438                 q.len = 0;
 439                 q.sign = zero;
 440                 return;
 441         }
 442         // 0 / b gives quotient 0 and remainder 0
 443         if (sign == zero) {
 444                 q.len = 0;
 445                 q.sign = zero;
 446                 return;
 447         }
 448
 449         // Here *this != 0, b != 0.
 450
 451         // Do the operands have the same sign?
 452         if (sign == b.sign) {
 453                 // Yes: easy case.  Quotient is zero or positive.
 454                 q.sign = positive;
 455         } else {
 456                 // No: harder case.  Quotient is negative.
 457                 q.sign = negative;
 458                 // Decrease the magnitude of the dividend by one.
 459                 BigUnsigned::operator --();
 460                 /*
 461                 * We tinker with the dividend before and with the
 462                 * quotient and remainder after so that the result
 463                 * comes out right.  To see why it works, consider the following
 464                 * list of examples, where A is the magnitude-decreased
 465                 * a, Q and R are the results of BigUnsigned division
 466                 * with remainder on A and |b|, and q and r are the
 467                 * final results we want:
 468                 *
 469                 *       a       A       b       Q       R       q       r
 470                 *       -3      -2      3       0       2       -1      0
 471                 *       -4      -3      3       1       0       -2      2
 472                 *       -5      -4      3       1       1       -2      1
 473                 *       -6      -5      3       1       2       -2      0
 474                 *
 475                 * It appears that we need a total of 3 corrections:
 476                 * Decrease the magnitude of a to get A.  Increase the
 477                 * magnitude of Q to get q (and make it negative).
 478                 * Find r = (b - 1) - R and give it the desired sign.
 479                 */
 480         }
 481
 482         // Divide the magnitudes.
 483         BigUnsigned::divideWithRemainder(b, q);
 484
 485         if (sign != b.sign) {
 486                 // More for the harder case (as described):
 487                 // Increase the magnitude of the quotient by one.
 488                 q.BigUnsigned::operator ++();
 489                 // Modify the remainder.
 490                 BigUnsigned temp(*this);
 491                 BigUnsigned::subtract(b, temp);
 492                 BigUnsigned::operator --();
 493         }
 494
 495         // Sign of the remainder is always the sign of the divisor b.
 496         sign = b.sign;
 497
 498         // Set signs to zero as necessary.  (Thanks David Allen!)
 499         if (len == 0)
 500                 sign = zero;
 501         if (q.len == 0)
 502                 q.sign = zero;
 503
 504         // WHEW!!!
 505 }
 506
 507 // Negation
 508 void BigInteger::negate(const BigInteger &a) {
 509         // Block unsafe calls
 510         if (this == &a)
 511                 throw "BigInteger::negate: The argument is the invoked object";
 512         // Copy a's magnitude
 513         BigUnsigned::operator =(a);
 514         // Copy the opposite of a.sign
 515         sign = Sign(-a.sign);
 516 }
 517
 518 // INCREMENT/DECREMENT OPERATORS
 519
 520 // Prefix increment
 521 void BigInteger::operator ++() {
 522         switch (sign) {
 523                 case zero:
 524                 allocate(1);
 525                 sign = positive;
 526                 len = 1;
 527                 blk[0] = 1;
 528                 break;
 529                 case positive:
 530                 BigUnsigned::operator ++();
 531                 break;
 532                 case negative:
 533                 BigUnsigned::operator --();
 534                 if (len == 0)
 535                         sign = zero;
 536                 break;
 537         }
 538 }
 539
 540 // Postfix increment: same as prefix
 541 void BigInteger::operator ++(int) {
 542         operator ++();
 543 }
 544
 545 // Prefix decrement
 546 void BigInteger::operator --() {
 547         switch (sign) {
 548                 case zero:
 549                 allocate(1);
 550                 sign = negative;
 551                 len = 1;
 552                 blk[0] = 1;
 553                 break;
 554                 case negative:
 555                 BigUnsigned::operator ++();
 556                 break;
 557                 case positive:
 558                 BigUnsigned::operator --();
 559                 if (len == 0)
 560                         sign = zero;
 561                 break;
 562         }
 563 }
 564
 565 // Postfix decrement: same as prefix
 566 void BigInteger::operator --(int) {
 567         operator --();
 568 }
 569