BigInteger.cc

   1 #include "BigInteger.hh"
   2
   3 void BigInteger::operator =(const BigInteger &x) {
   4         // Calls like a = a have no effect
   5         if (this == &x)
   6                 return;
   7         // Copy sign
   8         sign = x.sign;
   9         // Copy the rest
  10         mag = x.mag;
  11 }
  12
  13 BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) {
  14         switch (s) {
  15         case zero:
  16         case positive:
  17         case negative:
  18                 sign = mag.isZero() ? zero : s;
  19                 break;
  20         default:
  21                 throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid sign";
  22         }
  23 }
  24
  25 BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) {
  26         switch (s) {
  27         case zero:
  28         case positive:
  29         case negative:
  30                 sign = mag.isZero() ? zero : s;
  31                 break;
  32         default:
  33                 throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
  34         }
  35 }
  36
  37 /* CONSTRUCTION FROM PRIMITIVE INTEGERS
  38  * Same idea as in BigUnsigned.cc, except that negative input results in a
  39  * negative BigInteger instead of an exception. */
  40
  41 // Done longhand to let us use initialization.
  42 BigInteger::BigInteger(unsigned long x) : mag(x) {
  43         sign = mag.isZero() ? zero : positive;
  44 }
  45 BigInteger::BigInteger(unsigned int x) : mag(x) {
  46         sign = mag.isZero() ? zero : positive;
  47 }
  48 BigInteger::BigInteger(unsigned short x) : mag(x) {
  49         sign = mag.isZero() ? zero : positive;
  50 }
  51
  52 // For signed input, determine the desired magnitude and sign separately.
  53
  54 namespace {
  55         template <class X, class UX>
  56         BigInteger::Blk magOf(X x) {
  57                 /* UX(...) cast needed to stop short(-2^15), which negates to
  58                  * itself, from sign-extending in the conversion to Blk. */
  59                 return BigInteger::Blk(x < 0 ? UX(-x) : x);
  60         }
  61         template <class X>
  62         BigInteger::Sign signOf(X x) {
  63                 return (x == 0) ? BigInteger::zero
  64                         : (x > 0) ? BigInteger::positive
  65                         : BigInteger::negative;
  66         }
  67 }
  68
  69 BigInteger::BigInteger(long x) : sign(signOf(x)),
  70         mag(magOf<long, unsigned long>(x)) {}
  71 BigInteger::BigInteger(int x) : sign(signOf(x)),
  72         mag(magOf<int, unsigned int>(x)) {}
  73 BigInteger::BigInteger(short x) : sign(signOf(x)),
  74         mag(magOf<short, unsigned short>(x)) {}
  75
  76 // CONVERSION TO PRIMITIVE INTEGERS
  77
  78 /* Reuse BigUnsigned's conversion to an unsigned primitive integer.
  79  * The friend is a separate function rather than
  80  * BigInteger::convertToUnsignedPrimitive to avoid requiring BigUnsigned to
  81  * declare BigInteger. */
  82 template <class X>
  83 inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) {
  84         return a.convertToPrimitive<X>();
  85 }
  86
  87 template <class X>
  88 X BigInteger::convertToUnsignedPrimitive() const {
  89         if (sign == negative)
  90                 throw "BigInteger::to<Primitive>: "
  91                         "Cannot convert a negative integer to an unsigned type";
  92         else
  93                 return convertBigUnsignedToPrimitiveAccess<X>(mag);
  94 }
  95
  96 /* Similar to BigUnsigned::convertToPrimitive, but split into two cases for
  97  * nonnegative and negative numbers. */
  98 template <class X, class UX>
  99 X BigInteger::convertToSignedPrimitive() const {
 100         if (sign == zero)
 101                 return 0;
 102         else if (mag.getLength() == 1) {
 103                 // The single block might fit in an X.  Try the conversion.
 104                 Blk b = mag.getBlock(0);
 105                 if (sign == positive) {
 106                         X x = X(b);
 107                         if (x >= 0 && Blk(x) == b)
 108                                 return x;
 109                 } else {
 110                         X x = -X(b);
 111                         /* UX(...) needed to avoid rejecting conversion of
 112                          * -2^15 to a short. */
 113                         if (x < 0 && Blk(UX(-x)) == b)
 114                                 return x;
 115                 }
 116                 // Otherwise fall through.
 117         }
 118         throw "BigInteger::to<Primitive>: "
 119                 "Value is too big to fit in the requested type";
 120 }
 121
 122 unsigned long BigInteger::toUnsignedLong() const {
 123         return convertToUnsignedPrimitive<unsigned long>();
 124 }
 125 unsigned int BigInteger::toUnsignedInt() const {
 126         return convertToUnsignedPrimitive<unsigned int>();
 127 }
 128 unsigned short BigInteger::toUnsignedShort() const {
 129         return convertToUnsignedPrimitive<unsigned short>();
 130 }
 131 long BigInteger::toLong() const {
 132         return convertToSignedPrimitive<long, unsigned long>();
 133 }
 134 int BigInteger::toInt() const {
 135         return convertToSignedPrimitive<int, unsigned int>();
 136 }
 137 short BigInteger::toShort() const {
 138         return convertToSignedPrimitive<short, unsigned short>();
 139 }
 140
 141 // COMPARISON
 142 BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
 143         // A greater sign implies a greater number
 144         if (sign < x.sign)
 145                 return less;
 146         else if (sign > x.sign)
 147                 return greater;
 148         else switch (sign) {
 149                 // If the signs are the same...
 150         case zero:
 151                 return equal; // Two zeros are equal
 152         case positive:
 153                 // Compare the magnitudes
 154                 return mag.compareTo(x.mag);
 155         case negative:
 156                 // Compare the magnitudes, but return the opposite result
 157                 return CmpRes(-mag.compareTo(x.mag));
 158         default:
 159                 throw "BigInteger internal error";
 160         }
 161 }
 162
 163 /* COPY-LESS OPERATIONS
 164  * These do some messing around to determine the sign of the result,
 165  * then call one of BigUnsigned's copy-less operations. */
 166
 167 // See remarks about aliased calls in BigUnsigned.cc .
 168 #define DTRT_ALIASED(cond, op) \
 169         if (cond) { \
 170                 BigInteger tmpThis; \
 171                 tmpThis.op; \
 172                 *this = tmpThis; \
 173                 return; \
 174         }
 175
 176 void BigInteger::add(const BigInteger &a, const BigInteger &b) {
 177         DTRT_ALIASED(this == &a || this == &b, add(a, b));
 178         // If one argument is zero, copy the other.
 179         if (a.sign == zero)
 180                 operator =(b);
 181         else if (b.sign == zero)
 182                 operator =(a);
 183         // If the arguments have the same sign, take the
 184         // common sign and add their magnitudes.
 185         else if (a.sign == b.sign) {
 186                 sign = a.sign;
 187                 mag.add(a.mag, b.mag);
 188         } else {
 189                 // Otherwise, their magnitudes must be compared.
 190                 switch (a.mag.compareTo(b.mag)) {
 191                 case equal:
 192                         // If their magnitudes are the same, copy zero.
 193                         mag = 0;
 194                         sign = zero;
 195                         break;
 196                         // Otherwise, take the sign of the greater, and subtract
 197                         // the lesser magnitude from the greater magnitude.
 198                 case greater:
 199                         sign = a.sign;
 200                         mag.subtract(a.mag, b.mag);
 201                         break;
 202                 case less:
 203                         sign = b.sign;
 204                         mag.subtract(b.mag, a.mag);
 205                         break;
 206                 }
 207         }
 208 }
 209
 210 void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
 211         // Notice that this routine is identical to BigInteger::add,
 212         // if one replaces b.sign by its opposite.
 213         DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
 214         // If a is zero, copy b and flip its sign.  If b is zero, copy a.
 215         if (a.sign == zero) {
 216                 mag = b.mag;
 217                 // Take the negative of _b_'s, sign, not ours.
 218                 // Bug pointed out by Sam Larkin on 2005.03.30.
 219                 sign = Sign(-b.sign);
 220         } else if (b.sign == zero)
 221                 operator =(a);
 222         // If their signs differ, take a.sign and add the magnitudes.
 223         else if (a.sign != b.sign) {
 224                 sign = a.sign;
 225                 mag.add(a.mag, b.mag);
 226         } else {
 227                 // Otherwise, their magnitudes must be compared.
 228                 switch (a.mag.compareTo(b.mag)) {
 229                         // If their magnitudes are the same, copy zero.
 230                 case equal:
 231                         mag = 0;
 232                         sign = zero;
 233                         break;
 234                         // If a's magnitude is greater, take a.sign and
 235                         // subtract a from b.
 236                 case greater:
 237                         sign = a.sign;
 238                         mag.subtract(a.mag, b.mag);
 239                         break;
 240                         // If b's magnitude is greater, take the opposite
 241                         // of b.sign and subtract b from a.
 242                 case less:
 243                         sign = Sign(-b.sign);
 244                         mag.subtract(b.mag, a.mag);
 245                         break;
 246                 }
 247         }
 248 }
 249
 250 void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
 251         DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
 252         // If one object is zero, copy zero and return.
 253         if (a.sign == zero || b.sign == zero) {
 254                 sign = zero;
 255                 mag = 0;
 256                 return;
 257         }
 258         // If the signs of the arguments are the same, the result
 259         // is positive, otherwise it is negative.
 260         sign = (a.sign == b.sign) ? positive : negative;
 261         // Multiply the magnitudes.
 262         mag.multiply(a.mag, b.mag);
 263 }
 264
 265 /*
 266  * DIVISION WITH REMAINDER
 267  * Please read the comments before the definition of
 268  * `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
 269  * information you should know before reading this function.
 270  *
 271  * Following Knuth, I decree that x / y is to be
 272  * 0 if y==0 and floor(real-number x / y) if y!=0.
 273  * Then x % y shall be x - y*(integer x / y).
 274  *
 275  * Note that x = y * (x / y) + (x % y) always holds.
 276  * In addition, (x % y) is from 0 to y - 1 if y > 0,
 277  * and from -(|y| - 1) to 0 if y < 0.  (x % y) = x if y = 0.
 278  *
 279  * Examples: (q = a / b, r = a % b)
 280  *      a       b       q       r
 281  *      ===     ===     ===     ===
 282  *      4       3       1       1
 283  *      -4      3       -2      2
 284  *      4       -3      -2      -2
 285  *      -4      -3      1       -1
 286  */
 287 void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
 288         // Defend against aliased calls;
 289         // same idea as in BigUnsigned::divideWithRemainder .
 290         if (this == &q)
 291                 throw "BigInteger::divideWithRemainder: Cannot write quotient and remainder into the same variable";
 292         if (this == &b || &q == &b) {
 293                 BigInteger tmpB(b);
 294                 divideWithRemainder(tmpB, q);
 295                 return;
 296         }
 297
 298         // Division by zero gives quotient 0 and remainder *this
 299         if (b.sign == zero) {
 300                 q.mag = 0;
 301                 q.sign = zero;
 302                 return;
 303         }
 304         // 0 / b gives quotient 0 and remainder 0
 305         if (sign == zero) {
 306                 q.mag = 0;
 307                 q.sign = zero;
 308                 return;
 309         }
 310
 311         // Here *this != 0, b != 0.
 312
 313         // Do the operands have the same sign?
 314         if (sign == b.sign) {
 315                 // Yes: easy case.  Quotient is zero or positive.
 316                 q.sign = positive;
 317         } else {
 318                 // No: harder case.  Quotient is negative.
 319                 q.sign = negative;
 320                 // Decrease the magnitude of the dividend by one.
 321                 mag--;
 322                 /*
 323                  * We tinker with the dividend before and with the
 324                  * quotient and remainder after so that the result
 325                  * comes out right.  To see why it works, consider the following
 326                  * list of examples, where A is the magnitude-decreased
 327                  * a, Q and R are the results of BigUnsigned division
 328                  * with remainder on A and |b|, and q and r are the
 329                  * final results we want:
 330                  *
 331                  *      a       A       b       Q       R       q       r
 332                  *      -3      -2      3       0       2       -1      0
 333                  *      -4      -3      3       1       0       -2      2
 334                  *      -5      -4      3       1       1       -2      1
 335                  *      -6      -5      3       1       2       -2      0
 336                  *
 337                  * It appears that we need a total of 3 corrections:
 338                  * Decrease the magnitude of a to get A.  Increase the
 339                  * magnitude of Q to get q (and make it negative).
 340                  * Find r = (b - 1) - R and give it the desired sign.
 341                  */
 342         }
 343
 344         // Divide the magnitudes.
 345         mag.divideWithRemainder(b.mag, q.mag);
 346
 347         if (sign != b.sign) {
 348                 // More for the harder case (as described):
 349                 // Increase the magnitude of the quotient by one.
 350                 q.mag++;
 351                 // Modify the remainder.
 352                 mag.subtract(b.mag, mag);
 353                 mag--;
 354         }
 355
 356         // Sign of the remainder is always the sign of the divisor b.
 357         sign = b.sign;
 358
 359         // Set signs to zero as necessary.  (Thanks David Allen!)
 360         if (mag.isZero())
 361                 sign = zero;
 362         if (q.mag.isZero())
 363                 q.sign = zero;
 364
 365         // WHEW!!!
 366 }
 367
 368 // Negation
 369 void BigInteger::negate(const BigInteger &a) {
 370         DTRT_ALIASED(this == &a, negate(a));
 371         // Copy a's magnitude
 372         mag = a.mag;
 373         // Copy the opposite of a.sign
 374         sign = Sign(-a.sign);
 375 }
 376
 377 // INCREMENT/DECREMENT OPERATORS
 378
 379 // Prefix increment
 380 void BigInteger::operator ++() {
 381         if (sign == negative) {
 382                 mag--;
 383                 if (mag == 0)
 384                         sign = zero;
 385         } else {
 386                 mag++;
 387                 sign = positive; // if not already
 388         }
 389 }
 390
 391 // Postfix increment: same as prefix
 392 void BigInteger::operator ++(int) {
 393         operator ++();
 394 }
 395
 396 // Prefix decrement
 397 void BigInteger::operator --() {
 398         if (sign == positive) {
 399                 mag--;
 400                 if (mag == 0)
 401                         sign = zero;
 402         } else {
 403                 mag++;
 404                 sign = negative;
 405         }
 406 }
 407
 408 // Postfix decrement: same as prefix
 409 void BigInteger::operator --(int) {
 410         operator --();
 411 }
 412