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