Click here to download p4/posint.hpp.

#ifndef POSINT_H
#define POSINT_H

#include <iostream>
#include <vector>

/* This class represents an arbitrarily large integer
 * that is at least 0. It is represented by a vector of
 * digits, starting from the least-significant digit, and
 * with each digit between 0 and B-1.
 */
class PosInt {
  private:
    // It must ALWAYS be the case that B = Bbase ^ Bpow.
    // B is really the one to be concerned about for arithmetic; 
    // Bbase just determines how the number looks for I/O operations.
    static int B;
    static int Bbase;
    static int Bpow;
   
    std::vector<int> digits;

    // Removes leading 0 digits
    void normalize();

    // Result is -1, 0, or 1 if a is <, =, or > than b,
    // up to the specified length.
    static int compareDigits (const int* a, int alen, const int* b, int blen);
    // Computes dest += x, digit-wise
    static void addArray (int* dest, const int* x, int len);
    // Computes dest -= x, digit-wise
    static void subArray (int* dest, const int* x, int len);
    // Computes dest = dest * x, digit-wise
    static void mulArray (int* dest, int x, int len);
    // Computes dest = dest / x, digit-wise, and returns dest % x
    static int divArray (int* dest, int x, int len);
    // Computes division with remainder, digit-wise.
    static void divremArray 
      (int* q, int* r, const int* x, int xlen, const int* y, int ylen);

    static void fastMulArray (int* dest, const int* x, const int* y, int len);

  public:
    // Computes division with remainder. After the call, we have
    // x = q*y + r, and 0 <= r < y.
    static void divrem (PosInt& q, PosInt& r, const PosInt& x, const PosInt& y);

    // Sets the base to base^pow.
    static void setBase(int base, int pow=1);

    PosInt() { }
    PosInt (int x) { set(x); }
    PosInt (const char* s) { read(s); }

    // I/O routines
    void print_array(std::ostream& out) const;
    void print(std::ostream& out) const;
    void read(std::istream& in);
    void read(const char* s);

    // Sets this PosInt to the given value
    void set (int x);
    void set (const PosInt& rhs);

    // Returns this PosInt as a regular int
    int convert () const;

    // Sets this PosInt to a random number between 0 and x-1
    void rand (const PosInt& x);

    // Common comparison tests
    bool isZero() const { return digits.empty(); }
    bool isOne() const
      { return digits.size() == 1 && digits[0] == 1; }
    bool isEven() const;

    // Result is -1, 0, or 1 if this is <, =, or > than rhs.
    int compare (const PosInt& x) const;

    // this = x + y
    PosInt& add (const PosInt& x, const PosInt& y);
    // this = this + x
    PosInt& add (const PosInt& x);

    // this = x - y
    PosInt& sub (const PosInt& x, const PosInt& y);
    // this = this - x
    PosInt& sub (const PosInt& x);

    // this = x * y
    PosInt& mul (const PosInt& x, const PosInt& y);
    // this = this * x
    PosInt& mul (const PosInt& x)
      { PosInt temp(*this); return mul(temp, x); }

    // this = x / y
    PosInt& div (const PosInt& x, const PosInt& y)
      { PosInt temp; divrem(*this, temp, x, y); return *this; }
    // this = this / y
    PosInt& div (const PosInt& x)
      { PosInt temp; divrem(*this, temp, *this, x); return *this; }

    // this = x % y
    PosInt& mod (const PosInt& x, const PosInt& y)
      { PosInt temp; divrem(temp, *this, x, y); return *this; }
    // this = this % y
    PosInt& mod (const PosInt& x)
      { PosInt temp; divrem(temp, *this, *this, x); return *this; }

    // this = x ^ y
    PosInt& pow (const PosInt& x, const PosInt& y);
    // this = this ^ x
    PosInt& pow (const PosInt& x) { return pow(*this, x); }

    // this = gcd(x,y)
    PosInt& gcd (const PosInt& x, const PosInt& y);

    // this = gcd(x,y) = s*x - t*y
    // NOTE THE MINUS SIGN! This is required so that both s and t are
    // always non-negative.
    PosInt& xgcd (PosInt& s, PosInt& t, const PosInt& x, const PosInt& y);

    // return true/false if this is PROBABLY prime
    bool MillerRabin () const;

    // Like "mul", only faster!
    PosInt& fasterMul (const PosInt& x, const PosInt& y);
};

std::ostream& operator<< (std::ostream& out, const PosInt& x);
std::istream& operator>> (std::istream& out, PosInt& x);

#endif // POSINT_H