include/AD/numeric/bigint.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef variable_precision_integer_h
  26 #define variable_precision_integer_h
  27
  28 //////////////////////////////////////////////////////////////////////
  29 //  Class BigInt is a variable precision integer type.
  30 //////////////////////////////////////////////////////////////////////
  31
  32 #include <iostream>
  33 #include <new.h>
  34 #include <AD/generic/generic.h>  // Generic definitions
  35
  36 class BigInt {
  37 public:
  38
  39    //////////////////////////////////////////////////////////////////////
  40    //  BigInt is represented in a sign/magnitude format.
  41    //  For stupid reasons, we'll have to export this definition to
  42    //  the client.
  43    //////////////////////////////////////////////////////////////////////
  44    struct a_BigInt {
  45
  46       typedef unsigned short Digit;  // 16 bits per digit
  47       typedef unsigned long  Unit;   // 32 bits for computation
  48
  49       int   sign;      // sign of the number: 0, +1, or -1.
  50       int   len;       // number of digits currently used
  51       int   capacity;  // number of digits available in array
  52       Digit digits[1]; // array of digits; the least significant is at index 0
  53
  54       //////////////////////////////////////////////////////////////////////
  55       // Internal memory manager
  56       //////////////////////////////////////////////////////////////////////
  57       void * operator new    (size_t, int);
  58       void   operator delete (void *);
  59
  60       //////////////////////////////////////////////////////////////////////
  61       // These procedures work on the internal representation and
  62       // are the ones actually doing the dirty work.
  63       //////////////////////////////////////////////////////////////////////
  64       friend a_BigInt * copy(a_BigInt *, const a_BigInt *);
  65       friend a_BigInt * copy(a_BigInt *, long, int = 1);
  66       friend a_BigInt * neg(a_BigInt *, const a_BigInt *);
  67       friend a_BigInt * addsub(a_BigInt *, const a_BigInt *, const a_BigInt *, Bool);
  68       friend a_BigInt * addsub(a_BigInt *, const a_BigInt *, long, Bool);
  69       friend a_BigInt * addsub(a_BigInt *, long, const a_BigInt *, Bool);
  70       friend a_BigInt * mul(a_BigInt *, const a_BigInt *, const a_BigInt *);
  71       friend a_BigInt * mul(a_BigInt *, const a_BigInt *, long);
  72       friend a_BigInt * div(a_BigInt *, const a_BigInt *, const a_BigInt *);
  73       friend a_BigInt * div(a_BigInt *, const a_BigInt *, long);
  74       friend a_BigInt * div(a_BigInt *, long, const a_BigInt *);
  75       friend a_BigInt * mod(a_BigInt *, const a_BigInt *, const a_BigInt *);
  76       friend a_BigInt * mod(a_BigInt *, const a_BigInt *, long);
  77       friend a_BigInt * mod(a_BigInt *, long, const a_BigInt *);
  78       friend a_BigInt * andor(a_BigInt *, const a_BigInt *, const a_BigInt *,char);
  79       friend a_BigInt * andor(a_BigInt *, const a_BigInt *, long, char);
  80       friend a_BigInt * bitnot(a_BigInt *, const a_BigInt *);
  81       friend a_BigInt * shift(a_BigInt *, const a_BigInt *, const a_BigInt *, int);
  82       friend a_BigInt * shift(a_BigInt *, const a_BigInt *, long, int);
  83       friend a_BigInt * shift(a_BigInt *, long, const a_BigInt *, int);
  84       friend int       cmp(const a_BigInt *, const a_BigInt *);
  85       friend int       cmp(const a_BigInt *, long);
  86    };
  87
  88 private:
  89
  90    //////////////////////////////////////////////////////////////////////
  91    //  A BigInt is just a pointer to its representation.
  92    //  Since zero is a common value and used for initialization
  93    //  a special zero value is provided.   This is hidden for
  94    //  your protection!
  95    //////////////////////////////////////////////////////////////////////
  96    static a_BigInt * zero;
  97
  98
  99 public:
 100    a_BigInt * D;
 101    BigInt(a_BigInt * d) : D(d) {}  // for internal use only
 102
 103    ////////////////////////////////////////////////////////////////////////
 104    //  Error handler
 105    ////////////////////////////////////////////////////////////////////////
 106    static void (*error_handler)(const char []);
 107
 108    ////////////////////////////////////////////////////////////////////////
 109    // Constructors and destructors
 110    ////////////////////////////////////////////////////////////////////////
 111
 112    inline  BigInt() : D(zero)      { }                   // i.e. BigInt n;
 113    inline  BigInt(const BigInt& n) { D = copy(0,n); }    // i.e. BigInt n = m;
 114    inline  BigInt(int n)           { D = copy(0,n); }    // i.e. BigInt n = 1;
 115            BigInt(const char *);          // i.e. BigInt n = "12345";
 116    inline ~BigInt()                { delete D; }
 117
 118    ////////////////////////////////////////////////////////////////////////
 119    // Conversions: double() converts a BigInt to a double
 120    // Conversions: long() converts a BigInt to a long with truncation
 121    ////////////////////////////////////////////////////////////////////////
 122    operator double () const;
 123
 124    ////////////////////////////////////////////////////////////////////////
 125    // Assignments
 126    ////////////////////////////////////////////////////////////////////////
 127    inline BigInt& operator = (const BigInt& n)
 128       { D = copy(D,n.D); return *this; }
 129    inline BigInt& operator = (const int n)
 130       { D = copy(D,n); return *this; }
 131           BigInt& operator = (const char *);
 132
 133    ////////////////////////////////////////////////////////////////////////
 134    // Attributes of a BigInt
 135    ////////////////////////////////////////////////////////////////////////
 136    inline int  sign   () const           { return D->sign; }
 137    inline Bool isEven () const           { return (D->digits[0] & 1) == 0; }
 138    inline Bool isOdd  () const           { return D->digits[0] & 1; }
 139    inline int  operator [] (int i) const { return D->digits[i/16] & (1 << (i & 15)); }
 140    inline int  radix  () const           { return 1 << (8 * sizeof(a_BigInt::Digit)); }
 141    inline int  length () const;
 142
 143    ////////////////////////////////////////////////////////////////////////
 144    // Arithmetic operators
 145    ////////////////////////////////////////////////////////////////////////
 146    friend BigInt abs         (const BigInt&);
 147    friend BigInt operator -  (const BigInt&);
 148    friend BigInt operator +  (const BigInt&, const BigInt&);
 149    friend BigInt operator +  (int, const BigInt&);
 150    friend BigInt operator +  (const BigInt&, int);
 151    friend BigInt operator -  (const BigInt&, const BigInt&);
 152    friend BigInt operator -  (int, const BigInt&);
 153    friend BigInt operator -  (const BigInt&, int);
 154    friend BigInt operator *  (const BigInt&, const BigInt&);
 155    friend BigInt operator *  (int, const BigInt&);
 156    friend BigInt operator *  (const BigInt&, int);
 157    friend BigInt operator /  (const BigInt&, const BigInt&);
 158    friend BigInt operator /  (int, const BigInt&);
 159    friend BigInt operator /  (const BigInt&, int);
 160    friend BigInt operator %  (const BigInt&, const BigInt&);
 161    friend BigInt operator %  (int, const BigInt&);
 162    friend BigInt operator %  (const BigInt&, int);
 163    friend void   div_mod     (const BigInt&, const BigInt&, BigInt&, BigInt&);
 164    friend BigInt operator << (const BigInt&, const BigInt&);
 165    friend BigInt operator << (int, const BigInt&);
 166    friend BigInt operator << (const BigInt&, int);
 167    friend BigInt operator >> (const BigInt&, const BigInt&);
 168    friend BigInt operator >> (int, const BigInt&);
 169    friend BigInt operator >> (const BigInt&, int);
 170    friend BigInt operator |  (const BigInt&, const BigInt&);
 171    friend BigInt operator |  (int, const BigInt&);
 172    friend BigInt operator |  (const BigInt&, int);
 173    friend BigInt operator &  (const BigInt&, const BigInt&);
 174    friend BigInt operator &  (int, const BigInt&);
 175    friend BigInt operator &  (const BigInt&, int);
 176    friend BigInt operator ^  (const BigInt&, const BigInt&);
 177    friend BigInt operator ^  (int, const BigInt&);
 178    friend BigInt operator ^  (const BigInt&, int);
 179    friend BigInt not         (const BigInt&);
 180    friend unsigned int hash  (const BigInt&);
 181
 182    ///////////////////////////////////////////////////////////
 183    // Single bit operations
 184    ///////////////////////////////////////////////////////////
 185    inline int nthBit(int nth) const { return D->digits[nth/16] & (1 << (nth & 15)); }
 186    inline void setBit(int nth)      { D->digits[nth/16] |= (1 << (nth & 15)); }
 187    inline void clearBit(int nth)    { D->digits[nth/16] &= ~(1 << (nth & 15)); }
 188
 189    ///////////////////////////////////////////////////////////
 190    // In place operations are inlined for efficiency
 191    ///////////////////////////////////////////////////////////
 192    inline void operator ++ (int) { D = addsub(D,D,1,false); }
 193    inline void operator -- (int) { D = addsub(D,D,1,true); }
 194    inline void operator ++  ()   { D = addsub(D,D,1,false); }
 195    inline void operator --  ()   { D = addsub(D,D,1,true); }
 196
 197    inline void abs ()      { if (D->sign == -1) D = neg(D,D); }
 198    inline void negate ()   { D = neg(D,D); }
 199    inline void not()       { D = bitnot(D,D); }
 200    inline void operator += (const BigInt& n) { D = addsub(D,D,n.D,false); }
 201    inline void operator -= (const BigInt& n) { D = addsub(D,D,n.D,true); }
 202    inline void operator *= (const BigInt& n) { D = mul(D,D,n.D); }
 203    inline void operator /= (const BigInt& n) { D = div(D,D,n.D); }
 204    inline void operator %= (const BigInt& n) { D = mod(D,D,n.D); }
 205    inline void operator <<=(const BigInt& n) { D = shift(D,D,n.D,1); }
 206    inline void operator >>=(const BigInt& n) { D = shift(D,D,n.D,-1); }
 207    inline void operator |= (const BigInt& n) { D = andor(D,D,n.D,'|'); }
 208    inline void operator &= (const BigInt& n) { D = andor(D,D,n.D,'&'); }
 209    inline void operator ^= (const BigInt& n) { D = andor(D,D,n.D,'^'); }
 210    inline void operator += (int n)          { D = addsub(D,D,n,false); }
 211    inline void operator -= (int n)          { D = addsub(D,D,n,true); }
 212    inline void operator *= (int n)          { D = mul(D,D,n); }
 213    inline void operator /= (int n)          { D = div(D,D,n); }
 214    inline void operator %= (int n)          { D = mod(D,D,n); }
 215    inline void operator <<=(int n)          { D = shift(D,D,n,1); }
 216    inline void operator >>=(int n)          { D = shift(D,D,n,-1); }
 217    inline void operator |= (int n)          { D = andor(D,D,n,'|'); }
 218    inline void operator &= (int n)          { D = andor(D,D,n,'&'); }
 219    inline void operator ^= (int n)          { D = andor(D,D,n,'^'); }
 220
 221    ///////////////////////////////////////////////////////////
 222    // Comparisons are inlined for efficiency
 223    ///////////////////////////////////////////////////////////
 224    inline friend Bool operator == (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) == 0; }
 225    inline friend Bool operator == (const BigInt& a, int b) { return cmp(a.D,b) == 0; }
 226    inline friend Bool operator == (int a, const BigInt& b) { return cmp(b.D,a) == 0; }
 227    inline friend Bool operator != (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) != 0; }
 228    inline friend Bool operator != (const BigInt& a, int b) { return cmp(a.D,b) != 0; }
 229    inline friend Bool operator != (int a, const BigInt& b) { return cmp(b.D,a) != 0; }
 230    inline friend Bool operator > (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) > 0; }
 231    inline friend Bool operator > (const BigInt& a, int b)  { return cmp(a.D,b) > 0; }
 232    inline friend Bool operator > (int a, const BigInt& b)  { return cmp(b.D,a) <= 0; }
 233    inline friend Bool operator < (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) < 0; }
 234    inline friend Bool operator < (const BigInt& a, int b)  { return cmp(a.D,b) < 0; }
 235    inline friend Bool operator < (int a, const BigInt& b)  { return cmp(b.D,a) >= 0; }
 236    inline friend Bool operator >= (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) >= 0; }
 237    inline friend Bool operator >= (const BigInt& a, int b) { return cmp(a.D,b) >= 0; }
 238    inline friend Bool operator >= (int a, const BigInt& b) { return cmp(b.D,a) < 0; }
 239    inline friend Bool operator <= (const BigInt& a, const BigInt& b) { return cmp(a.D,b.D) <= 0; }
 240    inline friend Bool operator <= (const BigInt& a, int b) { return cmp(a.D,b) <= 0; }
 241    inline friend Bool operator <= (int a, const BigInt& b) { return cmp(b.D,a) > 0; }
 242
 243    ///////////////////////////////////////////////////////////
 244    //  Miscellaneous arithmetic
 245    ///////////////////////////////////////////////////////////
 246    friend BigInt gcd         (BigInt, BigInt);
 247    friend BigInt sqrt        (const BigInt&);
 248    friend BigInt pow         (const BigInt&, const BigInt&);
 249    friend BigInt pow_mod     (const BigInt&, const BigInt&, const BigInt&);
 250    friend BigInt make_random (const BigInt& limit);
 251
 252    ///////////////////////////////////////////////////////////
 253    // I/O and string conversion
 254    ///////////////////////////////////////////////////////////
 255    char * makeString (char [], size_t length = 1024,
 256                       unsigned int base = 10) const;
 257    int parseString (const char *, unsigned int base = 10);
 258    friend std::ostream& operator << (std::ostream&, const BigInt&);
 259    friend std::istream& operator >> (std::istream&, BigInt&);
 260 };
 261
 262 ///////////////////////////////////////////////////////////////////////////
 263 //  Binary and unary operators are inlined for efficiency.
 264 //  G++ has a non-standard syntax for faster returning of inline values
 265 //  that eliminate unnecessary copying.  We'll provided a version with this
 266 //  special optimization and one without for non G++ compilers.
 267 ///////////////////////////////////////////////////////////////////////////
 268 // #if defined(__GNUG__) && ! defined(NO_NRV)
 269 #if 0
 270    inline BigInt abs         (const BigInt& a) return r
 271       { r.D = a.D->sign == -1 ? neg(r.D,a.D) : copy(r.D,a.D); }
 272    inline BigInt operator -  (const BigInt& a) return r
 273       { r.D = neg(r.D,a.D); }
 274    inline BigInt operator +  (const BigInt& a, const BigInt& b) return r
 275       { r.D = addsub(r.D,a.D,b.D,false); }
 276    inline BigInt operator +  (long a, const BigInt& b) return r
 277       { r.D = addsub(r.D,b.D,a,false); }
 278    inline BigInt operator +  (const BigInt& a, long b) return r
 279       { r.D = addsub(r.D,a.D,b,false); }
 280    inline BigInt operator -  (const BigInt& a, const BigInt& b) return r
 281       { r.D = addsub(r.D,a.D,b.D,true); }
 282    inline BigInt operator -  (long a, const BigInt& b) return r
 283       { r.D = addsub(r.D,a,b.D,true); }
 284    inline BigInt operator -  (const BigInt& a, long b) return r
 285       { r.D = addsub(r.D,a.D,b,true); }
 286    inline BigInt operator *  (const BigInt& a, const BigInt& b) return r
 287       { r.D = mul(r.D,a.D,b.D); }
 288    inline BigInt operator *  (long a, const BigInt& b) return r
 289       { r.D = mul(r.D,b.D,a); }
 290    inline BigInt operator *  (const BigInt& a, long b) return r
 291       { r.D = mul(r.D,a.D,b); }
 292    inline BigInt operator /  (const BigInt& a, const BigInt& b) return r
 293       { r.D = div(r.D,a.D,b.D); }
 294    inline BigInt operator /  (long a, const BigInt& b) return r
 295       { r.D = div(r.D,a,b.D); }
 296    inline BigInt operator /  (const BigInt& a, long b) return r
 297       { r.D = div(r.D,a.D,b); }
 298    inline BigInt operator %  (const BigInt& a, const BigInt& b) return r
 299       { r.D = mod(r.D,a.D,b.D); }
 300    inline BigInt operator %  (long a, const BigInt& b) return r
 301       { r.D = mod(r.D,a,b.D); }
 302    inline BigInt operator %  (const BigInt& a, long b) return r
 303       { r.D = mod(r.D,a.D,b); }
 304    inline BigInt operator << (const BigInt& a, const BigInt& b) return r
 305       { r.D = shift(r.D,a.D,b.D,1); }
 306    inline BigInt operator << (long a, const BigInt& b) return r
 307       { r.D = shift(r.D,a,b.D,1); }
 308    inline BigInt operator << (const BigInt& a, long b) return r
 309       { r.D = shift(r.D,a.D,b,1); }
 310    inline BigInt operator >> (const BigInt& a, const BigInt& b) return r
 311       { r.D = shift(r.D,a.D,b.D,-1); }
 312    inline BigInt operator >> (long a, const BigInt& b) return r
 313       { r.D = shift(r.D,a,b.D,-1); }
 314    inline BigInt operator >> (const BigInt& a, long b) return r
 315       { r.D = shift(r.D,a.D,b,-1); }
 316    inline BigInt operator |  (const BigInt& a, const BigInt& b) return r
 317       { r.D = andor(r.D,a.D,b.D,'|'); }
 318    inline BigInt operator |  (long a, const BigInt& b) return r
 319       { r.D = andor(r.D,b.D,a,'|'); }
 320    inline BigInt operator |  (const BigInt& a, long b) return r
 321       { r.D = andor(r.D,a.D,b,'|'); }
 322    inline BigInt operator &  (const BigInt& a, const BigInt& b) return r
 323       { r.D = andor(r.D,a.D,b.D,'&'); }
 324    inline BigInt operator &  (long a, const BigInt& b) return r
 325       { r.D = andor(r.D,b.D,a,'&'); }
 326    inline BigInt operator &  (const BigInt& a, long b) return r
 327       { r.D = andor(r.D,a.D,b,'&'); }
 328    inline BigInt operator ^  (const BigInt& a, const BigInt& b) return r
 329       { r.D = andor(r.D,a.D,b.D,'^'); }
 330    inline BigInt operator ^  (long a, const BigInt& b) return r
 331       { r.D = andor(r.D,b.D,a,'^'); }
 332    inline BigInt operator ^  (const BigInt& a, long b) return r
 333       { r.D = andor(r.D,a.D,b,'^'); }
 334    inline BigInt not         (const BigInt& a)  return r
 335       { r.D = bitnot(r.D,a.D); }
 336 #else
 337    inline BigInt abs         (const BigInt& a)
 338       { return BigInt(a.D->sign == -1 ? neg(0,a.D) : copy(0,a.D)); }
 339    inline BigInt operator -  (const BigInt& a)
 340       { return BigInt(neg(0,a.D)); }
 341    inline BigInt operator +  (const BigInt& a, const BigInt& b) { return BigInt(addsub(0,a.D,b.D,false)); }
 342    inline BigInt operator +  (long a, const BigInt& b)          { return BigInt(addsub(0,b.D,a,false)); }
 343    inline BigInt operator +  (const BigInt& a, long b)          { return BigInt(addsub(0,a.D,b,false)); }
 344    inline BigInt operator -  (const BigInt& a, const BigInt& b) { return BigInt(addsub(0,a.D,b.D,true)); }
 345    inline BigInt operator -  (int a, const BigInt& b)          { return BigInt(addsub(0,a,b.D,true)); }
 346    inline BigInt operator -  (const BigInt& a, int b)          { return BigInt(addsub(0,a.D,b,true)); }
 347    inline BigInt operator *  (const BigInt& a, const BigInt& b) { return BigInt(mul(0,a.D,b.D)); }
 348    inline BigInt operator *  (long a, const BigInt& b)          { return BigInt(mul(0,b.D,a)); }
 349    inline BigInt operator *  (const BigInt& a, int b)          { return BigInt(mul(0,a.D,b)); }
 350    inline BigInt operator /  (const BigInt& a, const BigInt& b) { return BigInt(div(0,a.D,b.D)); }
 351    inline BigInt operator /  (int a, const BigInt& b)          { return BigInt(div(0,a,b.D)); }
 352    inline BigInt operator /  (const BigInt& a, long b)          { return BigInt(div(0,a.D,b)); }
 353    inline BigInt operator %  (const BigInt& a, const BigInt& b) { return BigInt(mod(0,a.D,b.D)); }
 354    inline BigInt operator %  (int a, const BigInt& b)          { return BigInt(mod(0,a,b.D)); }
 355    inline BigInt operator %  (const BigInt& a, int b)          { return BigInt(mod(0,a.D,b)); }
 356    inline BigInt operator << (const BigInt& a, const BigInt& b) { return BigInt(shift(0,a.D,b.D,1)); }
 357    inline BigInt operator << (int a, const BigInt& b)          { return BigInt(shift(0,a,b.D,1)); }
 358    inline BigInt operator << (const BigInt& a, int b)          { return BigInt(shift(0,a.D,b,1)); }
 359    inline BigInt operator >> (const BigInt& a, const BigInt& b) { return BigInt(shift(0,a.D,b.D,-1)); }
 360    inline BigInt operator >> (int a, const BigInt& b)          { return BigInt(shift(0,a,b.D,-1)); }
 361    inline BigInt operator >> (const BigInt& a, int b)          { return BigInt(shift(0,a.D,b,-1)); }
 362    inline BigInt operator |  (const BigInt& a, const BigInt& b) { return BigInt(andor(0,a.D,b.D,'|')); }
 363    inline BigInt operator |  (long a, const BigInt& b)          { return BigInt(andor(0,b.D,a,'|')); }
 364    inline BigInt operator |  (const BigInt& a, long b)          { return BigInt(andor(0,a.D,b,'|')); }
 365    inline BigInt operator &  (const BigInt& a, const BigInt& b) { return BigInt(andor(0,a.D,b.D,'&')); }
 366    inline BigInt operator &  (long a, const BigInt& b)          { return BigInt(andor(0,b.D,a,'&')); }
 367    inline BigInt operator &  (const BigInt& a, long b)          { return BigInt(andor(0,a.D,b,'&')); }
 368    inline BigInt operator ^  (const BigInt& a, const BigInt& b) { return BigInt(andor(0,a.D,b.D,'^')); }
 369    inline BigInt operator ^  (long a, const BigInt& b)          { return BigInt(andor(0,b.D,a,'^')); }
 370    inline BigInt operator ^  (const BigInt& a, long b)          { return BigInt(andor(0,a.D,b,'^')); }
 371    inline BigInt not         (const BigInt& a)  { return BigInt(bitnot(0,a.D)); }
 372 #endif
 373
 374 #endif