1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#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