Integer.h

Go to the documentation of this file.

#ifndef _Integer_h
#define _Integer_h


#include <iostream>

using namespace std;


struct IntRep                    // internal Integer representations
{
        IntRep( ) { }
        IntRep( unsigned short l, unsigned short  s1, short s2, unsigned short  s3      ) : len( l ), sz( s1 ), sgn( s2 ) { s[0] = s3; }

        unsigned short  len;          // current length
        unsigned short  sz;           // allocated space (0 means static).
        short           sgn;          // 1 means >= 0; 0 means < 0 
        unsigned short  s[1];         // represented as ushort array starting here
};


// True if REP is staticly (or manually) allocated,
// and should not be deleted by an Integer destructor.
#define STATIC_IntRep(rep) ((rep)->sz==0)

IntRep*  Ialloc(IntRep*, const unsigned short *, int, int, int);
IntRep*  Icalloc(IntRep*, int);
IntRep*  Icopy_ulong(IntRep*, unsigned long);
IntRep*  Icopy_long(IntRep*, long);
IntRep*  Icopy(IntRep*, const IntRep*);
IntRep*  Iresize(IntRep*, int);
IntRep*  add(const IntRep*, int, const IntRep*, int, IntRep*);
IntRep*  add(const IntRep*, int, long, IntRep*);
IntRep*  multiply(const IntRep*, const IntRep*, IntRep*);
IntRep*  multiply(const IntRep*, long, IntRep*);
IntRep*  lshift(const IntRep*, long, IntRep*);
IntRep*  lshift(const IntRep*, const IntRep*, int, IntRep*);
IntRep*  bitop(const IntRep*, const IntRep*, IntRep*, char);
IntRep*  bitop(const IntRep*, long, IntRep*, char);
IntRep*  power(const IntRep*, long, IntRep*);
IntRep*  div(const IntRep*, const IntRep*, IntRep*);
IntRep*  mod(const IntRep*, const IntRep*, IntRep*);
IntRep*  div(const IntRep*, long, IntRep*);
IntRep*  mod(const IntRep*, long, IntRep*);
IntRep*  _compl(const IntRep*, IntRep*); // @au
IntRep*  abs(const IntRep*, IntRep*);
IntRep*  negate1(const IntRep*, IntRep*);
IntRep*  pow(const IntRep*, long);
IntRep*  gcd(const IntRep*, const IntRep* y);
int      compare(const IntRep*, const IntRep*);
int      compare(const IntRep*, long);
int      ucompare(const IntRep*, const IntRep*);
int      ucompare(const IntRep*, long);
char*    Itoa(const IntRep* x, int base = 10, int width = 0);
char*    cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base,
                                          int showbase, int width, int align_right, 
                                          char fillchar, char Xcase, int showpos);
IntRep*  atoIntRep(const char* s, int base = 10);
long     Itolong(const IntRep*);
int      Iislong(const IntRep*);
long     lg(const IntRep*);



static struct ZeroRep : public IntRep
{
public:
        ZeroRep( ) : IntRep( 1, 0, 1, 0 ) { }

        // operator IntRep( ) { return *this; } // @au
} _ZeroRep;


static struct OneRep : public IntRep
{
public:
        OneRep( ) : IntRep( 1, 0, 1, 1 ) { }
        // operator IntRep( ) { return *this; } // @au
} _OneRep;

static struct MinusOneRep : public IntRep
{
public:
        MinusOneRep( ) : IntRep( 1, 0, 0, 1 ) { }
        // operator IntRep( ) { return *this; } // @au
} _MinusOneRep;


IntRep* Icopy_zero(IntRep* old);


class Integer
{
protected:
        IntRep*         rep;
public:
        Integer();
        Integer(int);
        Integer(long);
        Integer(unsigned long);
        Integer(IntRep*);
        Integer(const Integer&);
        
        ~Integer();
        Integer&        operator =  (const Integer&);
        Integer&        operator =  (long);
        
        // unary operations to self
        
        Integer&        operator ++ ();
        Integer&        operator -- ();
        void            negate1();          // negate in-place
        void            abs();             // absolute-value in-place
        void            complement();      // bitwise complement in-place
        
        // assignment-based operations
        
        Integer&        operator += (const Integer&);
        Integer&        operator -= (const Integer&);
        Integer&        operator *= (const Integer&);
        Integer&        operator /= (const Integer&);
        Integer&        operator %= (const Integer&);
        Integer&        operator <<=(const Integer&);
        Integer&        operator >>=(const Integer&);
        Integer&        operator &= (const Integer&);
        Integer&        operator |= (const Integer&);
        Integer&        operator ^= (const Integer&);
        
        Integer&        operator += (long);
        Integer&        operator -= (long);
        Integer&        operator *= (long);
        Integer&        operator /= (long);
        Integer&        operator %= (long);
        Integer&        operator <<=(long);
        Integer&        operator >>=(long);
        Integer&        operator &= (long);
        Integer&        operator |= (long);
        Integer&        operator ^= (long);
        
        // (constructive binary operations are inlined below)
        
#if defined (__GNUG__) && ! defined (__STRICT_ANSI__)
        friend Integer operator <? (const Integer& x, const Integer& y); // min
        friend Integer operator >? (const Integer& x, const Integer& y); // max
#endif
        
        // builtin Integer functions that must be friends
        
        friend long     lg (const Integer&); // floor log base 2 of abs(x)
        friend double   ratio(const Integer& x, const Integer& y);
        // return x/y as a double
        
        friend Integer  gcd(const Integer&, const Integer&);
        friend int      even(const Integer&); // true if even
        friend int      odd(const Integer&); // true if odd
        friend int      sign(const Integer&); // returns -1, 0, +1
        
        friend void     (setbit)(Integer& x, long b);   // set b'th bit of x
        friend void     clearbit(Integer& x, long b); // clear b'th bit
        friend int      testbit(const Integer& x, long b);  // return b'th bit
        
        // procedural versions of operators
        
        friend void     abs(const Integer& x, Integer& dest);
        friend void     negate1(const Integer& x, Integer& dest);
        friend void     complement(const Integer& x, Integer& dest);
        
        friend int      compare(const Integer&, const Integer&);  
        friend int      ucompare(const Integer&, const Integer&); 
        friend void     add(const Integer& x, const Integer& y, Integer& dest);
        friend void     sub(const Integer& x, const Integer& y, Integer& dest);
        friend void     mul(const Integer& x, const Integer& y, Integer& dest);
        friend void     div(const Integer& x, const Integer& y, Integer& dest);
        friend void     mod(const Integer& x, const Integer& y, Integer& dest);
        friend void     divide(const Integer& x, const Integer& y, Integer& q, Integer& r);
        friend void     _and(const Integer& x, const Integer& y, Integer& dest); // @au
        friend void     _or(const Integer& x, const Integer& y, Integer& dest);  // @au
        friend void     _xor(const Integer& x, const Integer& y, Integer& dest); // @au
        friend void     lshift(const Integer& x, const Integer& y, Integer& dest);
        friend void     rshift(const Integer& x, const Integer& y, Integer& dest);
        friend void     pow(const Integer& x, const Integer& y, Integer& dest);
        
        friend int      compare(const Integer&, long);  
        friend int      ucompare(const Integer&, long); 
        friend void     add(const Integer& x, long y, Integer& dest);
        friend void     sub(const Integer& x, long y, Integer& dest);
        friend void     mul(const Integer& x, long y, Integer& dest);
        friend void     div(const Integer& x, long y, Integer& dest);
        friend void     mod(const Integer& x, long y, Integer& dest);
        friend void     divide(const Integer& x, long y, Integer& q, long& r);
        friend void     _and(const Integer& x, long y, Integer& dest);          // @au
        friend void     _or(const Integer& x, long y, Integer& dest);           // @au
        friend void     _xor(const Integer& x, long y, Integer& dest);          // @au
        friend void     lshift(const Integer& x, long y, Integer& dest);
        friend void     rshift(const Integer& x, long y, Integer& dest);
        friend void     pow(const Integer& x, long y, Integer& dest);
        
        friend int      compare(long, const Integer&);  
        friend int      ucompare(long, const Integer&); 
        friend void     add(long x, const Integer& y, Integer& dest);
        friend void     sub(long x, const Integer& y, Integer& dest);
        friend void     mul(long x, const Integer& y, Integer& dest);
        friend void     _and(long x, const Integer& y, Integer& dest); // @au
        friend void     _or(long x, const Integer& y, Integer& dest);  // @au
        friend void     _xor(long x, const Integer& y, Integer& dest); // @au
        
        // coercion & conversion
        
        int             fits_in_long() const { return Iislong(rep); }
        int             fits_in_double() const;
        
        long              as_long() const { return Itolong(rep); }
        double    as_double() const;
        
        friend char*    Itoa(const Integer& x, int base = 10, int width = 0);
        friend Integer  atoI(const char* s, int base = 10);
        void              printon( ostream& s, int base = 10, int width = 0) const;
        
        friend ostream& operator << (ostream& s, const Integer& y);
        friend istream& operator >> (istream& stream, Integer& val)
        {
                // if (!stream.ipfx( )) // @au
                //      return stream;
                int sign = ' ';
                register streambuf* sb = stream.rdbuf();
                int base = 10;
                int ndigits = 0;
                register int ch = sb->sbumpc();
                while (ch != EOF && isspace(ch))
                        ch = sb->sbumpc();
                if (ch == '+' || ch == '-')
                {
                        sign = ch;
                        ch = sb->sbumpc();
                        while (ch != EOF && isspace(ch))
                                ch = sb->sbumpc();
                }
                if (ch == EOF) goto eof_fail;
                if (!(stream.flags() & ios::basefield))
                {
                        if (ch == '0')
                        {
                                ch = sb->sbumpc();
                                if (ch == EOF) { }
                                else if (ch == 'x' || ch == 'X')
                                {
                                        base = 16;
                                        ch = sb->sbumpc();
                                        if (ch == EOF) goto eof_fail;
                                }
                                else
                                {
                                        sb->sputbackc(ch);
                                        base = 8;
                                        ch = '0';
                                }
                        }
                }
                else if ((stream.flags() & ios::basefield) == ios::hex)
                        base = 16;
                else if ((stream.flags() & ios::basefield) == ios::oct)
                        base = 8;
                
                val.rep = Icopy_zero( val.rep );
                
                for (;;)
                {
                        if (ch == EOF)
                                break;
                        int digit;
                        if (ch >= '0' && ch <= '9')
                                digit = ch - '0';
                        else if (ch >= 'A' && ch <= 'F')
                                digit = ch - 'A' + 10;
                        else if (ch >= 'a' && ch <= 'f')
                                digit = ch - 'a' + 10;
                        else
                                digit = 999;
                        if (digit >= base)
                        {
                                sb->sputbackc(ch);
                                if (ndigits == 0)
                                        goto fail;
                                else
                                        goto done;
                        }
                        ndigits++;
                        switch (base)
                        {
                        case 8:
                                val <<= 3;
                                break;
                        case 16:
                                val <<= 4;
                                break;
                        default:
                                val *= base;
                                break;
                        }
                        val += digit;
                        ch = sb->sbumpc();
                }
fail:
                //@au
                // stream.set(ios::failbit);
done:
                if (sign == '-')
                        val.negate1();
                return stream;
eof_fail:
                //@au
                // stream.set(ios::failbit|ios::eofbit);
                return stream;
        }
        
        // error detection
        
        int             initialized() const;
        void   error(const char* msg) const;
        int             OK( ) const;  
};


//  (These are declared inline)

int      operator == (const Integer&, const Integer&);
int      operator == (const Integer&, long);
int      operator != (const Integer&, const Integer&);
int      operator != (const Integer&, long);
int      operator <  (const Integer&, const Integer&);
int      operator <  (const Integer&, long);
int      operator <= (const Integer&, const Integer&);
int      operator <= (const Integer&, long);
int      operator >  (const Integer&, const Integer&);
int      operator >  (const Integer&, long);
int      operator >= (const Integer&, const Integer&);
int      operator >= (const Integer&, long);
Integer  operator -  (const Integer&);
Integer  operator ~  (const Integer&);
Integer  operator +  (const Integer&, const Integer&);
Integer  operator +  (const Integer&, long);
Integer  operator +  (long, const Integer&);
Integer  operator -  (const Integer&, const Integer&);
Integer  operator -  (const Integer&, long);
Integer  operator -  (long, const Integer&);
Integer  operator *  (const Integer&, const Integer&);
Integer  operator *  (const Integer&, long);
Integer  operator *  (long, const Integer&);
Integer  operator /  (const Integer&, const Integer&);
Integer  operator /  (const Integer&, long);
Integer  operator %  (const Integer&, const Integer&);
Integer  operator %  (const Integer&, long);
Integer  operator << (const Integer&, const Integer&);
Integer  operator << (const Integer&, long);
Integer  operator >> (const Integer&, const Integer&);
Integer  operator >> (const Integer&, long);
Integer  operator &  (const Integer&, const Integer&);
Integer  operator &  (const Integer&, long);
Integer  operator &  (long, const Integer&);
Integer  operator |  (const Integer&, const Integer&);
Integer  operator |  (const Integer&, long);
Integer  operator |  (long, const Integer&);
Integer  operator ^  (const Integer&, const Integer&);
Integer  operator ^  (const Integer&, long);
Integer  operator ^  (long, const Integer&);

Integer  abs(const Integer&); // absolute value
Integer  sqr(const Integer&); // square

Integer  pow(const Integer& x, const Integer& y);
Integer  pow(const Integer& x, long y);
Integer  Ipow(long x, long y); // x to the y as Integer 


char*    dec(const Integer& x, int width = 0);
char*    oct(const Integer& x, int width = 0);
char*    hex(const Integer& x, int width = 0);
Integer  sqrt(const Integer&); // floor of square root
Integer  lcm(const Integer& x, const Integer& y); // least common mult


typedef Integer IntTmp; // for backward compatibility

inline Integer::Integer() :rep(&_ZeroRep) {}

inline Integer::Integer(IntRep* r) :rep(r) {}

inline Integer::Integer(int y) :rep(Icopy_long(0, (long)y)) {}

inline Integer::Integer(long y) :rep(Icopy_long(0, y)) {}

inline Integer::Integer(unsigned long y) :rep(Icopy_ulong(0, y)) {}

inline Integer::Integer(const Integer&  y) :rep(Icopy(0, y.rep)) {}

inline Integer::~Integer() { if (rep && !STATIC_IntRep(rep)) delete rep; }

inline Integer&  Integer::operator = (const Integer&  y)
{
        rep = Icopy(rep, y.rep);
        return *this;
}

inline Integer& Integer::operator = (long y)
{
        rep = Icopy_long(rep, y);
        return *this;
}

inline int Integer::initialized() const
{
        return rep != 0;
}

// procedural versions

inline int compare(const Integer& x, const Integer& y)
{
        return compare(x.rep, y.rep);
}

inline int ucompare(const Integer& x, const Integer& y)
{
        return ucompare(x.rep, y.rep);
}

inline int compare(const Integer& x, long y)
{
        return compare(x.rep, y);
}

inline int ucompare(const Integer& x, long y)
{
        return ucompare(x.rep, y);
}

inline int compare(long x, const Integer& y)
{
        return -compare(y.rep, x);
}

inline int ucompare(long x, const Integer& y)
{
        return -ucompare(y.rep, x);
}

inline void  add(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = add(x.rep, 0, y.rep, 0, dest.rep);
}

inline void  sub(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = add(x.rep, 0, y.rep, 1, dest.rep);
}

inline void  mul(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = multiply(x.rep, y.rep, dest.rep);
}

inline void  div(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = div(x.rep, y.rep, dest.rep);
}

inline void  mod(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = mod(x.rep, y.rep, dest.rep);
}

inline void  _and(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(x.rep, y.rep, dest.rep, '&');
}

inline void  _or(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(x.rep, y.rep, dest.rep, '|');
}

inline void  _xor(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(x.rep, y.rep, dest.rep, '^');
}

inline void  lshift(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = lshift(x.rep, y.rep, 0, dest.rep);
}

inline void  rshift(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = lshift(x.rep, y.rep, 1, dest.rep);
}

inline void  pow(const Integer& x, const Integer& y, Integer& dest)
{
        dest.rep = power(x.rep, Itolong(y.rep), dest.rep); // not incorrect
}

inline void  add(const Integer& x, long y, Integer& dest)
{
        dest.rep = add(x.rep, 0, y, dest.rep);
}

inline void  sub(const Integer& x, long y, Integer& dest)
{
        dest.rep = add(x.rep, 0, -y, dest.rep);
}

inline void  mul(const Integer& x, long y, Integer& dest)
{
        dest.rep = multiply(x.rep, y, dest.rep);
}

inline void  div(const Integer& x, long y, Integer& dest)
{
        dest.rep = div(x.rep, y, dest.rep);
}

inline void  mod(const Integer& x, long y, Integer& dest)
{
        dest.rep = mod(x.rep, y, dest.rep);
}

inline void  _and(const Integer& x, long y, Integer& dest)
{
        dest.rep = bitop(x.rep, y, dest.rep, '&');
}

inline void  _or(const Integer& x, long y, Integer& dest)
{
        dest.rep = bitop(x.rep, y, dest.rep, '|');
}

inline void  _xor(const Integer& x, long y, Integer& dest)
{
        dest.rep = bitop(x.rep, y, dest.rep, '^');
}

inline void  lshift(const Integer& x, long y, Integer& dest)
{
        dest.rep = lshift(x.rep, y, dest.rep);
}

inline void  rshift(const Integer& x, long y, Integer& dest)
{
        dest.rep = lshift(x.rep, -y, dest.rep);
}

inline void  pow(const Integer& x, long y, Integer& dest)
{
        dest.rep = power(x.rep, y, dest.rep);
}

inline void abs(const Integer& x, Integer& dest)
{
        dest.rep = abs(x.rep, dest.rep);
}

inline void negate1(const Integer& x, Integer& dest)
{
        dest.rep = negate1(x.rep, dest.rep);
}

inline void complement(const Integer& x, Integer& dest)
{
        dest.rep = _compl(x.rep, dest.rep);
}

inline void  add(long x, const Integer& y, Integer& dest)
{
        dest.rep = add(y.rep, 0, x, dest.rep);
}

inline void  sub(long x, const Integer& y, Integer& dest)
{
        dest.rep = add(y.rep, 1, x, dest.rep);
}

inline void  mul(long x, const Integer& y, Integer& dest)
{
        dest.rep = multiply(y.rep, x, dest.rep);
}

inline void  _and(long x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(y.rep, x, dest.rep, '&');
}

inline void  _or(long x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(y.rep, x, dest.rep, '|');
}

inline void  _xor(long x, const Integer& y, Integer& dest)
{
        dest.rep = bitop(y.rep, x, dest.rep, '^');
}


// operator versions

inline int operator == (const Integer&  x, const Integer&  y)
{
        return compare(x, y) == 0; 
}

inline int operator == (const Integer&  x, long y)
{
        return compare(x, y) == 0; 
}

inline int operator != (const Integer&  x, const Integer&  y)
{
        return compare(x, y) != 0; 
}

inline int operator != (const Integer&  x, long y)
{
        return compare(x, y) != 0; 
}

inline int operator <  (const Integer&  x, const Integer&  y)
{
        return compare(x, y) <  0; 
}

inline int operator <  (const Integer&  x, long y)
{
        return compare(x, y) <  0; 
}

inline int operator <= (const Integer&  x, const Integer&  y)
{
        return compare(x, y) <= 0; 
}

inline int operator <= (const Integer&  x, long y)
{
        return compare(x, y) <= 0; 
}

inline int operator >  (const Integer&  x, const Integer&  y)
{
        return compare(x, y) >  0; 
}

inline int operator >  (const Integer&  x, long y)
{
        return compare(x, y) >  0; 
}

inline int operator >= (const Integer&  x, const Integer&  y)
{
        return compare(x, y) >= 0; 
}

inline int operator >= (const Integer&  x, long y)
{
        return compare(x, y) >= 0; 
}


inline Integer&  Integer::operator += (const Integer& y)
{
        add(*this, y, *this);