BigInteger Class Reference

#include <BigInteger.hh>

Collaboration diagram for BigInteger:

Public Types
enum	Sign { negative = -1, zero = 0, positive = 1 }
typedef BigUnsigned::Blk	Blk
typedef BigUnsigned::Index	Index
typedef BigUnsigned::CmpRes	CmpRes

Public Member Functions
	BigInteger ()
	BigInteger (const BigInteger &x)
void	operator= (const BigInteger &x)
	BigInteger (const Blk *b, Index blen, Sign s)
	BigInteger (const Blk *b, Index blen)
	BigInteger (const BigUnsigned &x, Sign s)
	BigInteger (const BigUnsigned &x)
	BigInteger (unsigned long x)
	BigInteger (long x)
	BigInteger (unsigned int x)
	BigInteger (int x)
	BigInteger (unsigned short x)
	BigInteger (short x)
unsigned long	toUnsignedLong () const
long	toLong () const
unsigned int	toUnsignedInt () const
int	toInt () const
unsigned short	toUnsignedShort () const
short	toShort () const
Sign	getSign () const
const BigUnsigned &	getMagnitude () const
Index	getLength () const
Index	getCapacity () const
Blk	getBlock (Index i) const
bool	isZero () const
CmpRes	compareTo (const BigInteger &x) const
bool	operator== (const BigInteger &x) const
bool	operator!= (const BigInteger &x) const
bool	operator< (const BigInteger &x) const
bool	operator<= (const BigInteger &x) const
bool	operator>= (const BigInteger &x) const
bool	operator> (const BigInteger &x) const
void	add (const BigInteger &a, const BigInteger &b)
void	subtract (const BigInteger &a, const BigInteger &b)
void	multiply (const BigInteger &a, const BigInteger &b)
void	divideWithRemainder (const BigInteger &b, BigInteger &q)
void	negate (const BigInteger &a)
BigInteger	operator+ (const BigInteger &x) const
BigInteger	operator- (const BigInteger &x) const
BigInteger	operator* (const BigInteger &x) const
BigInteger	operator/ (const BigInteger &x) const
BigInteger	operator% (const BigInteger &x) const
BigInteger	operator- () const
void	operator+= (const BigInteger &x)
void	operator-= (const BigInteger &x)
void	operator*= (const BigInteger &x)
void	operator/= (const BigInteger &x)
void	operator%= (const BigInteger &x)
void	flipSign ()
void	operator++ ()
void	operator++ (int)
void	operator-- ()
void	operator-- (int)

Static Public Attributes
static const CmpRes	less = BigUnsigned::less
static const CmpRes	equal = BigUnsigned::equal
static const CmpRes	greater = BigUnsigned::greater

Protected Member Functions
template<class X >
X	convertToUnsignedPrimitive () const
template<class X , class UX >
X	convertToSignedPrimitive () const

Protected Attributes
Sign	sign
BigUnsigned	mag

Detailed Description

Definition at line 13 of file BigInteger.hh.

Member Typedef Documentation

typedef BigUnsigned::Blk BigInteger::Blk

Definition at line 16 of file BigInteger.hh.

typedef BigUnsigned::CmpRes BigInteger::CmpRes

Definition at line 18 of file BigInteger.hh.

typedef BigUnsigned::Index BigInteger::Index

Definition at line 17 of file BigInteger.hh.

Member Enumeration Documentation

enum BigInteger::Sign

Enumerator
negative
zero
positive

Definition at line 24 of file BigInteger.hh.

{ negative = -1, zero = 0, positive = 1 };

Constructor & Destructor Documentation

BigInteger::BigInteger ( )

inline

Definition at line 32 of file BigInteger.hh.

: sign(zero), mag() {}

BigInteger::BigInteger ( const BigInteger &  x )

inline

Definition at line 35 of file BigInteger.hh.

: sign(x.sign), mag(x.mag) {};

BigInteger::BigInteger	(	const Blk *	b,
		Index	blen,
		Sign	s
	)

Definition at line 13 of file BigInteger.cc.

                                                       : mag(b, blen) {
    switch (s) {
    case zero:
        if (!mag.isZero())
            throw "BigInteger::BigInteger(const Blk *, Index, Sign): Cannot use a sign of zero with a nonzero magnitude";
        sign = zero;
        break;
    case positive:
    case negative:
        // If the magnitude is zero, force the sign to zero.
        sign = mag.isZero() ? zero : s;
        break;
    default:
        /* g++ seems to be optimizing out this case on the assumption
         * that the sign is a valid member of the enumeration.  Oh well. */
        throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid sign";
    }
}

Here is the call graph for this function:

BigInteger::BigInteger ( const Blk *  b, Index  blen  )

inline

Definition at line 44 of file BigInteger.hh.

                                         : mag(b, blen) {
        sign = mag.isZero() ? zero : positive;
    }

Here is the call graph for this function:

BigInteger::BigInteger	(	const BigUnsigned &	x,
		Sign	s
	)

Definition at line 32 of file BigInteger.cc.

                                                   : mag(x) {
    switch (s) {
    case zero:
        if (!mag.isZero())
            throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Cannot use a sign of zero with a nonzero magnitude";
        sign = zero;
        break;
    case positive:
    case negative:
        // If the magnitude is zero, force the sign to zero.
        sign = mag.isZero() ? zero : s;
        break;
    default:
        /* g++ seems to be optimizing out this case on the assumption
         * that the sign is a valid member of the enumeration.  Oh well. */
        throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Invalid sign";
    }
}

Here is the call graph for this function:

BigInteger::BigInteger ( const BigUnsigned &  x )

inline

Definition at line 52 of file BigInteger.hh.

                                     : mag(x) {
        sign = mag.isZero() ? zero : positive;
    }

Here is the call graph for this function:

BigInteger::BigInteger

(

unsigned long

x

)

Definition at line 56 of file BigInteger.cc.

: mag(x) { sign = mag.isZero() ? zero : positive; }

Here is the call graph for this function:

BigInteger::BigInteger

(

long

x

)

Definition at line 77 of file BigInteger.cc.

: sign(signOf(x)), mag(magOf<long , unsigned long >(x)) {}

BigInteger::BigInteger

(

unsigned int

x

)

Definition at line 57 of file BigInteger.cc.

: mag(x) { sign = mag.isZero() ? zero : positive; }

Here is the call graph for this function:

BigInteger::BigInteger

(

int

x

)

Definition at line 78 of file BigInteger.cc.

: sign(signOf(x)), mag(magOf<int  , unsigned int  >(x)) {}

BigInteger::BigInteger

(

unsigned short

x

)

Definition at line 58 of file BigInteger.cc.

: mag(x) { sign = mag.isZero() ? zero : positive; }

Here is the call graph for this function:

BigInteger::BigInteger

(

short

x

)

Definition at line 79 of file BigInteger.cc.

: sign(signOf(x)), mag(magOf<short, unsigned short>(x)) {}

Member Function Documentation

void BigInteger::add	(	const BigInteger &	a,
		const BigInteger &	b
	)

Definition at line 169 of file BigInteger.cc.

                                                             {
    DTRT_ALIASED(this == &a || this == &b, add(a, b));
    // If one argument is zero, copy the other.
    if (a.sign == zero)
        operator =(b);
    else if (b.sign == zero)
        operator =(a);
    // If the arguments have the same sign, take the
    // common sign and add their magnitudes.
    else if (a.sign == b.sign) {
        sign = a.sign;
        mag.add(a.mag, b.mag);
    } else {
        // Otherwise, their magnitudes must be compared.
        switch (a.mag.compareTo(b.mag)) {
        case equal:
            // If their magnitudes are the same, copy zero.
            mag = 0;
            sign = zero;
            break;
            // Otherwise, take the sign of the greater, and subtract
            // the lesser magnitude from the greater magnitude.
        case greater:
            sign = a.sign;
            mag.subtract(a.mag, b.mag);
            break;
        case less:
            sign = b.sign;
            mag.subtract(b.mag, a.mag);
            break;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

BigInteger::CmpRes BigInteger::compareTo

(

const BigInteger &

x

)

const

Definition at line 135 of file BigInteger.cc.

                                                                {
    // A greater sign implies a greater number
    if (sign < x.sign)
        return less;
    else if (sign > x.sign)
        return greater;
    else switch (sign) {
        // If the signs are the same...
    case zero:
        return equal; // Two zeros are equal
    case positive:
        // Compare the magnitudes
        return mag.compareTo(x.mag);
    case negative:
        // Compare the magnitudes, but return the opposite result
        return CmpRes(-mag.compareTo(x.mag));
    default:
        throw "BigInteger internal error";
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class X , class UX >

X BigInteger::convertToSignedPrimitive ( ) const

protected

Definition at line 104 of file BigInteger.cc.

                                             {
    if (sign == zero)
        return 0;
    else if (mag.getLength() == 1) {
        // The single block might fit in an X.  Try the conversion.
        Blk b = mag.getBlock(0);
        if (sign == positive) {
            X x = X(b);
            if (x >= 0 && Blk(x) == b)
                return x;
        } else {
            X x = -X(b);
            /* UX(...) needed to avoid rejecting conversion of
             * -2^15 to a short. */
            if (x < 0 && Blk(UX(-x)) == b)
                return x;
        }
        // Otherwise fall through.
    }
    throw "BigInteger::to<Primitive>: "
        "Value is too big to fit in the requested type";
}

Here is the call graph for this function:

template<class X >

X BigInteger::convertToUnsignedPrimitive ( ) const

protected

Definition at line 93 of file BigInteger.cc.

                                               {
    if (sign == negative)
        throw "BigInteger::to<Primitive>: "
            "Cannot convert a negative integer to an unsigned type";
    else
        return convertBigUnsignedToPrimitiveAccess<X>(mag);
}

void BigInteger::divideWithRemainder	(	const BigInteger &	b,
		BigInteger &	q
	)

Definition at line 280 of file BigInteger.cc.

                                                                       {
    // Defend against aliased calls;
    // same idea as in BigUnsigned::divideWithRemainder .
    if (this == &q)
        throw "BigInteger::divideWithRemainder: Cannot write quotient and remainder into the same variable";
    if (this == &b || &q == &b) {
        BigInteger tmpB(b);
        divideWithRemainder(tmpB, q);
        return;
    }

    // Division by zero gives quotient 0 and remainder *this
    if (b.sign == zero) {
        q.mag = 0;
        q.sign = zero;
        return;
    }
    // 0 / b gives quotient 0 and remainder 0
    if (sign == zero) {
        q.mag = 0;
        q.sign = zero;
        return;
    }

    // Here *this != 0, b != 0.

    // Do the operands have the same sign?
    if (sign == b.sign) {
        // Yes: easy case.  Quotient is zero or positive.
        q.sign = positive;
    } else {
        // No: harder case.  Quotient is negative.
        q.sign = negative;
        // Decrease the magnitude of the dividend by one.
        mag--;
        /*
         * We tinker with the dividend before and with the
         * quotient and remainder after so that the result
         * comes out right.  To see why it works, consider the following
         * list of examples, where A is the magnitude-decreased
         * a, Q and R are the results of BigUnsigned division
         * with remainder on A and |b|, and q and r are the
         * final results we want:
         *
         *  a   A   b   Q   R   q   r
         *  -3  -2  3   0   2   -1  0
         *  -4  -3  3   1   0   -2  2
         *  -5  -4  3   1   1   -2  1
         *  -6  -5  3   1   2   -2  0
         *
         * It appears that we need a total of 3 corrections:
         * Decrease the magnitude of a to get A.  Increase the
         * magnitude of Q to get q (and make it negative).
         * Find r = (b - 1) - R and give it the desired sign.
         */
    }

    // Divide the magnitudes.
    mag.divideWithRemainder(b.mag, q.mag);

    if (sign != b.sign) {
        // More for the harder case (as described):
        // Increase the magnitude of the quotient by one.
        q.mag++;
        // Modify the remainder.
        mag.subtract(b.mag, mag);
        mag--;
    }

    // Sign of the remainder is always the sign of the divisor b.
    sign = b.sign;

    // Set signs to zero as necessary.  (Thanks David Allen!)
    if (mag.isZero())
        sign = zero;
    if (q.mag.isZero())
        q.sign = zero;

    // WHEW!!!
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigInteger::flipSign ( )

inline

Definition at line 211 of file BigInteger.hh.

                                 {
    sign = Sign(-sign);
}

Blk BigInteger::getBlock ( Index  i ) const

inline

Definition at line 88 of file BigInteger.hh.

{ return mag.getBlock(i); }

Here is the call graph for this function:

Index BigInteger::getCapacity ( ) const

inline

Definition at line 87 of file BigInteger.hh.

{ return mag.getCapacity(); }

Here is the call graph for this function:

Index BigInteger::getLength ( ) const

inline

Definition at line 86 of file BigInteger.hh.

{ return mag.getLength(); }

Here is the call graph for this function:

const BigUnsigned& BigInteger::getMagnitude ( ) const

inline

Definition at line 83 of file BigInteger.hh.

{ return mag; }

Here is the caller graph for this function:

Sign BigInteger::getSign ( ) const

inline

Definition at line 80 of file BigInteger.hh.

{ return sign; }

Here is the caller graph for this function:

bool BigInteger::isZero ( ) const

inline

Definition at line 89 of file BigInteger.hh.

{ return sign == zero; } // A bit special

Here is the caller graph for this function:

void BigInteger::multiply	(	const BigInteger &	a,
		const BigInteger &	b
	)

Definition at line 243 of file BigInteger.cc.

                                                                  {
    DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
    // If one object is zero, copy zero and return.
    if (a.sign == zero || b.sign == zero) {
        sign = zero;
        mag = 0;
        return;
    }
    // If the signs of the arguments are the same, the result
    // is positive, otherwise it is negative.
    sign = (a.sign == b.sign) ? positive : negative;
    // Multiply the magnitudes.
    mag.multiply(a.mag, b.mag);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigInteger::negate

(

const BigInteger &

a

)

Definition at line 362 of file BigInteger.cc.

                                           {
    DTRT_ALIASED(this == &a, negate(a));
    // Copy a's magnitude
    mag = a.mag;
    // Copy the opposite of a.sign
    sign = Sign(-a.sign);
}

Here is the caller graph for this function:

bool BigInteger::operator!= ( const BigInteger &  x ) const

inline

Definition at line 100 of file BigInteger.hh.

{ return !operator ==(x); };

Here is the call graph for this function:

BigInteger BigInteger::operator% ( const BigInteger &  x ) const

inline

Definition at line 166 of file BigInteger.hh.

                                                                  {
    if (x.isZero()) throw "BigInteger::operator %: division by zero";
    BigInteger q, r;
    r = *this;
    r.divideWithRemainder(x, q);
    return r;
}

Here is the call graph for this function:

void BigInteger::operator%= ( const BigInteger &  x )

inline

Definition at line 204 of file BigInteger.hh.

                                                       {
    if (x.isZero()) throw "BigInteger::operator %=: division by zero";
    BigInteger q;
    // Mods *this by x.  Don't care about quotient left in q.
    divideWithRemainder(x, q);
}

Here is the call graph for this function:

BigInteger BigInteger::operator* ( const BigInteger &  x ) const

inline

Definition at line 154 of file BigInteger.hh.

                                                                  {
    BigInteger ans;
    ans.multiply(*this, x);
    return ans;
}

Here is the call graph for this function:

void BigInteger::operator*= ( const BigInteger &  x )

inline

Definition at line 192 of file BigInteger.hh.

                                                       {
    multiply(*this, x);
}

Here is the call graph for this function:

BigInteger BigInteger::operator+ ( const BigInteger &  x ) const

inline

Definition at line 144 of file BigInteger.hh.

                                                                  {
    BigInteger ans;
    ans.add(*this, x);
    return ans;
}

Here is the call graph for this function:

void BigInteger::operator++

(

)

Definition at line 373 of file BigInteger.cc.

                             {
    if (sign == negative) {
        mag--;
        if (mag == 0)
            sign = zero;
    } else {
        mag++;
        sign = positive; // if not already
    }
}

Here is the caller graph for this function:

void BigInteger::operator++

(

int

)

Definition at line 385 of file BigInteger.cc.

                                {
    operator ++();
}

Here is the call graph for this function:

void BigInteger::operator+= ( const BigInteger &  x )

inline

Definition at line 186 of file BigInteger.hh.

                                                       {
    add(*this, x);
}

Here is the call graph for this function:

BigInteger BigInteger::operator- ( const BigInteger &  x ) const

inline

Definition at line 149 of file BigInteger.hh.

                                                                  {
    BigInteger ans;
    ans.subtract(*this, x);
    return ans;
}

Here is the call graph for this function:

BigInteger BigInteger::operator- ( ) const

inline

Definition at line 173 of file BigInteger.hh.

                                               {
    BigInteger ans;
    ans.negate(*this);
    return ans;
}

Here is the call graph for this function:

void BigInteger::operator--

(

)

Definition at line 390 of file BigInteger.cc.

                             {
    if (sign == positive) {
        mag--;
        if (mag == 0)
            sign = zero;
    } else {
        mag++;
        sign = negative;
    }
}

Here is the caller graph for this function:

void BigInteger::operator--

(

int

)

Definition at line 402 of file BigInteger.cc.

                                {
    operator --();
}

Here is the call graph for this function:

void BigInteger::operator-= ( const BigInteger &  x )

inline

Definition at line 189 of file BigInteger.hh.

                                                       {
    subtract(*this, x);
}

Here is the call graph for this function:

BigInteger BigInteger::operator/ ( const BigInteger &  x ) const

inline

Definition at line 159 of file BigInteger.hh.

                                                                  {
    if (x.isZero()) throw "BigInteger::operator /: division by zero";
    BigInteger q, r;
    r = *this;
    r.divideWithRemainder(x, q);
    return q;
}

Here is the call graph for this function:

void BigInteger::operator/= ( const BigInteger &  x )

inline

Definition at line 195 of file BigInteger.hh.

                                                       {
    if (x.isZero()) throw "BigInteger::operator /=: division by zero";
    /* The following technique is slightly faster than copying *this first
     * when x is large. */
    BigInteger q;
    divideWithRemainder(x, q);
    // *this contains the remainder, but we overwrite it with the quotient.
    *this = q;
}

Here is the call graph for this function:

bool BigInteger::operator< ( const BigInteger &  x ) const

inline

Definition at line 101 of file BigInteger.hh.

{ return compareTo(x) == less   ; }

Here is the call graph for this function:

bool BigInteger::operator<= ( const BigInteger &  x ) const

inline

Definition at line 102 of file BigInteger.hh.

{ return compareTo(x) != greater; }

Here is the call graph for this function:

void BigInteger::operator=

(

const BigInteger &

x

)

Definition at line 3 of file BigInteger.cc.

                                               {
    // Calls like a = a have no effect
    if (this == &x)
        return;
    // Copy sign
    sign = x.sign;
    // Copy the rest
    mag = x.mag;
}

Here is the caller graph for this function:

bool BigInteger::operator== ( const BigInteger &  x ) const

inline

Definition at line 97 of file BigInteger.hh.

                                                {
        return sign == x.sign && mag == x.mag;
    }

Here is the caller graph for this function:

bool BigInteger::operator> ( const BigInteger &  x ) const

inline

Definition at line 104 of file BigInteger.hh.

{ return compareTo(x) == greater; }

Here is the call graph for this function:

bool BigInteger::operator>= ( const BigInteger &  x ) const

inline

Definition at line 103 of file BigInteger.hh.

{ return compareTo(x) != less   ; }

Here is the call graph for this function:

void BigInteger::subtract	(	const BigInteger &	a,
		const BigInteger &	b
	)

Definition at line 203 of file BigInteger.cc.

                                                                  {
    // Notice that this routine is identical to BigInteger::add,
    // if one replaces b.sign by its opposite.
    DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
    // If a is zero, copy b and flip its sign.  If b is zero, copy a.
    if (a.sign == zero) {
        mag = b.mag;
        // Take the negative of _b_'s, sign, not ours.
        // Bug pointed out by Sam Larkin on 2005.03.30.
        sign = Sign(-b.sign);
    } else if (b.sign == zero)
        operator =(a);
    // If their signs differ, take a.sign and add the magnitudes.
    else if (a.sign != b.sign) {
        sign = a.sign;
        mag.add(a.mag, b.mag);
    } else {
        // Otherwise, their magnitudes must be compared.
        switch (a.mag.compareTo(b.mag)) {
            // If their magnitudes are the same, copy zero.
        case equal:
            mag = 0;
            sign = zero;
            break;
            // If a's magnitude is greater, take a.sign and
            // subtract a from b.
        case greater:
            sign = a.sign;
            mag.subtract(a.mag, b.mag);
            break;
            // If b's magnitude is greater, take the opposite
            // of b.sign and subtract b from a.
        case less:
            sign = Sign(-b.sign);
            mag.subtract(b.mag, a.mag);
            break;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int BigInteger::toInt

(

)

const

Definition at line 131 of file BigInteger.cc.

{ return convertToSignedPrimitive  <int  , unsigned int>  (); }

Here is the caller graph for this function:

long BigInteger::toLong

(

)

const

Definition at line 130 of file BigInteger.cc.

{ return convertToSignedPrimitive  <long , unsigned long> (); }

short BigInteger::toShort

(

)

const

Definition at line 132 of file BigInteger.cc.

{ return convertToSignedPrimitive  <short, unsigned short>(); }

unsigned int BigInteger::toUnsignedInt

(

)

const

Definition at line 128 of file BigInteger.cc.

{ return convertToUnsignedPrimitive<unsigned int  >       (); }

unsigned long BigInteger::toUnsignedLong

(

)

const

Definition at line 127 of file BigInteger.cc.

{ return convertToUnsignedPrimitive<unsigned long >       (); }

unsigned short BigInteger::toUnsignedShort

(

)

const

Definition at line 129 of file BigInteger.cc.

{ return convertToUnsignedPrimitive<unsigned short>       (); }

Field Documentation

const CmpRes BigInteger::equal = BigUnsigned::equal

static

Definition at line 21 of file BigInteger.hh.

const CmpRes BigInteger::greater = BigUnsigned::greater

static

Definition at line 22 of file BigInteger.hh.

const CmpRes BigInteger::less = BigUnsigned::less

static

Definition at line 20 of file BigInteger.hh.

BigUnsigned BigInteger::mag

protected

Definition at line 28 of file BigInteger.hh.

Sign BigInteger::sign

protected

Definition at line 27 of file BigInteger.hh.

---

The documentation for this class was generated from the following files:

• BigInteger.hh
• BigInteger.cc