BigUnsigned Class Reference

#include <BigUnsigned.hh>

Inheritance diagram for BigUnsigned:

Collaboration diagram for BigUnsigned:

Public Types
enum	CmpRes { less = -1, equal = 0, greater = 1 }
typedef unsigned long	Blk
typedef NumberlikeArray< Blk > ::Index	Index

Public Member Functions
	BigUnsigned ()
	BigUnsigned (const BigUnsigned &x)
void	operator= (const BigUnsigned &x)
	BigUnsigned (const Blk *b, Index blen)
	~BigUnsigned ()
	BigUnsigned (unsigned long x)
	BigUnsigned (long x)
	BigUnsigned (unsigned int x)
	BigUnsigned (int x)
	BigUnsigned (unsigned short x)
	BigUnsigned (short x)
unsigned long	toUnsignedLong () const
long	toLong () const
unsigned int	toUnsignedInt () const
int	toInt () const
unsigned short	toUnsignedShort () const
short	toShort () const
Blk	getBlock (Index i) const
void	setBlock (Index i, Blk newBlock)
bool	isZero () const
Index	bitLength () const
bool	getBit (Index bi) const
void	setBit (Index bi, bool newBit)
CmpRes	compareTo (const BigUnsigned &x) const
bool	operator== (const BigUnsigned &x) const
bool	operator!= (const BigUnsigned &x) const
bool	operator< (const BigUnsigned &x) const
bool	operator<= (const BigUnsigned &x) const
bool	operator>= (const BigUnsigned &x) const
bool	operator> (const BigUnsigned &x) const
void	add (const BigUnsigned &a, const BigUnsigned &b)
void	subtract (const BigUnsigned &a, const BigUnsigned &b)
void	multiply (const BigUnsigned &a, const BigUnsigned &b)
void	bitAnd (const BigUnsigned &a, const BigUnsigned &b)
void	bitOr (const BigUnsigned &a, const BigUnsigned &b)
void	bitXor (const BigUnsigned &a, const BigUnsigned &b)
void	bitShiftLeft (const BigUnsigned &a, int b)
void	bitShiftRight (const BigUnsigned &a, int b)
void	divideWithRemainder (const BigUnsigned &b, BigUnsigned &q)
BigUnsigned	operator+ (const BigUnsigned &x) const
BigUnsigned	operator- (const BigUnsigned &x) const
BigUnsigned	operator* (const BigUnsigned &x) const
BigUnsigned	operator/ (const BigUnsigned &x) const
BigUnsigned	operator% (const BigUnsigned &x) const
BigUnsigned	operator& (const BigUnsigned &x) const
BigUnsigned	operator| (const BigUnsigned &x) const
BigUnsigned	operator^ (const BigUnsigned &x) const
BigUnsigned	operator<< (int b) const
BigUnsigned	operator>> (int b) const
void	operator+= (const BigUnsigned &x)
void	operator-= (const BigUnsigned &x)
void	operator*= (const BigUnsigned &x)
void	operator/= (const BigUnsigned &x)
void	operator%= (const BigUnsigned &x)
void	operator&= (const BigUnsigned &x)
void	operator|= (const BigUnsigned &x)
void	operator^= (const BigUnsigned &x)
void	operator<<= (int b)
void	operator>>= (int b)
void	operator++ ()
void	operator++ (int)
void	operator-- ()
void	operator-- (int)

Protected Member Functions
	BigUnsigned (int, Index c)
void	zapLeadingZeros ()
template<class X >
void	initFromPrimitive (X x)
template<class X >
void	initFromSignedPrimitive (X x)
template<class X >
X	convertToSignedPrimitive () const
template<class X >
X	convertToPrimitive () const
void	allocate (Index c)
void	allocateAndCopy (Index c)
Index	getCapacity () const
Index	getLength () const
bool	isEmpty () const
bool	operator== (const NumberlikeArray< unsigned long > &x) const
bool	operator!= (const NumberlikeArray< unsigned long > &x) const

Protected Attributes
Index	cap
Index	len
unsigned long *	blk

Static Protected Attributes
static const unsigned int	N

Friends
Blk	getShiftedBlock (const BigUnsigned &num, Index x, unsigned int y)
template<class X >
X	convertBigUnsignedToPrimitiveAccess (const BigUnsigned &a)

Detailed Description

Definition at line 13 of file BigUnsigned.hh.

Member Typedef Documentation

typedef unsigned long BigUnsigned::Blk

Definition at line 20 of file BigUnsigned.hh.

typedef NumberlikeArray<Blk>::Index BigUnsigned::Index

Definition at line 22 of file BigUnsigned.hh.

Member Enumeration Documentation

enum BigUnsigned::CmpRes

Enumerator
less
equal
greater

Definition at line 17 of file BigUnsigned.hh.

{ less = -1, equal = 0, greater = 1 };

Constructor & Destructor Documentation

BigUnsigned::BigUnsigned ( int  , Index  c  )

inlineprotected

Definition at line 27 of file BigUnsigned.hh.

: NumberlikeArray<Blk>(0, c) {}

BigUnsigned::BigUnsigned ( )

inline

Definition at line 37 of file BigUnsigned.hh.

: NumberlikeArray<Blk>() {}

BigUnsigned::BigUnsigned ( const BigUnsigned &  x )

inline

Definition at line 40 of file BigUnsigned.hh.

: NumberlikeArray<Blk>(x) {}

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

inline

Definition at line 48 of file BigUnsigned.hh.

                                          : NumberlikeArray<Blk>(b, blen) {
        // Eliminate any leading zeros we may have been passed.
        zapLeadingZeros();
    }

Here is the call graph for this function:

BigUnsigned::~BigUnsigned ( )

inline

Definition at line 54 of file BigUnsigned.hh.

{}

BigUnsigned::BigUnsigned

(

unsigned long

x

)

Definition at line 8 of file BigUnsigned.cc.

{ initFromPrimitive      (x); }

Here is the call graph for this function:

BigUnsigned::BigUnsigned

(

long

x

)

Definition at line 11 of file BigUnsigned.cc.

{ initFromSignedPrimitive(x); }

Here is the call graph for this function:

BigUnsigned::BigUnsigned

(

unsigned int

x

)

Definition at line 9 of file BigUnsigned.cc.

{ initFromPrimitive      (x); }

Here is the call graph for this function:

BigUnsigned::BigUnsigned

(

int

x

)

Definition at line 12 of file BigUnsigned.cc.

{ initFromSignedPrimitive(x); }

Here is the call graph for this function:

BigUnsigned::BigUnsigned

(

unsigned short

x

)

Definition at line 10 of file BigUnsigned.cc.

{ initFromPrimitive      (x); }

Here is the call graph for this function:

BigUnsigned::BigUnsigned

(

short

x

)

Definition at line 13 of file BigUnsigned.cc.

{ initFromSignedPrimitive(x); }

Here is the call graph for this function:

Member Function Documentation

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

Definition at line 124 of file BigUnsigned.cc.

                                                                {
    DTRT_ALIASED(this == &a || this == &b, add(a, b));
    // If one argument is zero, copy the other.
    if (a.len == 0) {
        operator =(b);
        return;
    } else if (b.len == 0) {
        operator =(a);
        return;
    }
    // Some variables...
    // Carries in and out of an addition stage
    bool carryIn, carryOut;
    Blk temp;
    Index i;
    // a2 points to the longer input, b2 points to the shorter
    const BigUnsigned *a2, *b2;
    if (a.len >= b.len) {
        a2 = &a;
        b2 = &b;
    } else {
        a2 = &b;
        b2 = &a;
    }
    // Set prelimiary length and make room in this BigUnsigned
    len = a2->len + 1;
    allocate(len);
    // For each block index that is present in both inputs...
    for (i = 0, carryIn = false; i < b2->len; i++) {
        // Add input blocks
        temp = a2->blk[i] + b2->blk[i];
        // If a rollover occurred, the result is less than either input.
        // This test is used many times in the BigUnsigned code.
        carryOut = (temp < a2->blk[i]);
        // If a carry was input, handle it
        if (carryIn) {
            temp++;
            carryOut |= (temp == 0);
        }
        blk[i] = temp; // Save the addition result
        carryIn = carryOut; // Pass the carry along
    }
    // If there is a carry left over, increase blocks until
    // one does not roll over.
    for (; i < a2->len && carryIn; i++) {
        temp = a2->blk[i] + 1;
        carryIn = (temp == 0);
        blk[i] = temp;
    }
    // If the carry was resolved but the larger number
    // still has blocks, copy them over.
    for (; i < a2->len; i++)
        blk[i] = a2->blk[i];
    // Set the extra block if there's still a carry, decrease length otherwise
    if (carryIn)
        blk[i] = 1;
    else
        len--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void NumberlikeArray< unsigned long >::allocate ( Index  c )

inherited

Here is the caller graph for this function:

void NumberlikeArray< unsigned long >::allocateAndCopy ( Index  c )

inherited

Here is the caller graph for this function:

void BigUnsigned::bitAnd	(	const BigUnsigned &	a,
		const BigUnsigned &	b
	)

Definition at line 544 of file BigUnsigned.cc.

                                                                   {
    DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
    // The bitwise & can't be longer than either operand.
    len = (a.len >= b.len) ? b.len : a.len;
    allocate(len);
    Index i;
    for (i = 0; i < len; i++)
        blk[i] = a.blk[i] & b.blk[i];
    zapLeadingZeros();
}

Here is the call graph for this function:

Here is the caller graph for this function:

BigUnsigned::Index BigUnsigned::bitLength

(

)

const

Definition at line 47 of file BigUnsigned.cc.

                                              {
    if (isZero())
        return 0;
    else {
        Blk leftmostBlock = getBlock(len - 1);
        Index leftmostBlockLen = 0;
        while (leftmostBlock != 0) {
            leftmostBlock >>= 1;
            leftmostBlockLen++;
        }
        return leftmostBlockLen + (len - 1) * N;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::bitOr	(	const BigUnsigned &	a,
		const BigUnsigned &	b
	)

Definition at line 555 of file BigUnsigned.cc.

                                                                  {
    DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
    Index i;
    const BigUnsigned *a2, *b2;
    if (a.len >= b.len) {
        a2 = &a;
        b2 = &b;
    } else {
        a2 = &b;
        b2 = &a;
    }
    allocate(a2->len);
    for (i = 0; i < b2->len; i++)
        blk[i] = a2->blk[i] | b2->blk[i];
    for (; i < a2->len; i++)
        blk[i] = a2->blk[i];
    len = a2->len;
    // Doesn't need zapLeadingZeros.
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::bitShiftLeft	(	const BigUnsigned &	a,
		int	b
	)

Definition at line 595 of file BigUnsigned.cc.

                                                          {
    DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
    if (b < 0) {
        if (b << 1 == 0)
            throw "BigUnsigned::bitShiftLeft: "
                "Pathological shift amount not implemented";
        else {
            bitShiftRight(a, -b);
            return;
        }
    }
    Index shiftBlocks = b / N;
    unsigned int shiftBits = b % N;
    // + 1: room for high bits nudged left into another block
    len = a.len + shiftBlocks + 1;
    allocate(len);
    Index i, j;
    for (i = 0; i < shiftBlocks; i++)
        blk[i] = 0;
    for (j = 0, i = shiftBlocks; j <= a.len; j++, i++)
        blk[i] = getShiftedBlock(a, j, shiftBits);
    // Zap possible leading zero
    if (blk[len - 1] == 0)
        len--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::bitShiftRight	(	const BigUnsigned &	a,
		int	b
	)

Definition at line 621 of file BigUnsigned.cc.

                                                           {
    DTRT_ALIASED(this == &a, bitShiftRight(a, b));
    if (b < 0) {
        if (b << 1 == 0)
            throw "BigUnsigned::bitShiftRight: "
                "Pathological shift amount not implemented";
        else {
            bitShiftLeft(a, -b);
            return;
        }
    }
    // This calculation is wacky, but expressing the shift as a left bit shift
    // within each block lets us use getShiftedBlock.
    Index rightShiftBlocks = (b + N - 1) / N;
    unsigned int leftShiftBits = N * rightShiftBlocks - b;
    // Now (N * rightShiftBlocks - leftShiftBits) == b
    // and 0 <= leftShiftBits < N.
    if (rightShiftBlocks >= a.len + 1) {
        // All of a is guaranteed to be shifted off, even considering the left
        // bit shift.
        len = 0;
        return;
    }
    // Now we're allocating a positive amount.
    // + 1: room for high bits nudged left into another block
    len = a.len + 1 - rightShiftBlocks;
    allocate(len);
    Index i, j;
    for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++)
        blk[i] = getShiftedBlock(a, j, leftShiftBits);
    // Zap possible leading zero
    if (blk[len - 1] == 0)
        len--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::bitXor	(	const BigUnsigned &	a,
		const BigUnsigned &	b
	)

Definition at line 575 of file BigUnsigned.cc.

                                                                   {
    DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
    Index i;
    const BigUnsigned *a2, *b2;
    if (a.len >= b.len) {
        a2 = &a;
        b2 = &b;
    } else {
        a2 = &b;
        b2 = &a;
    }
    allocate(a2->len);
    for (i = 0; i < b2->len; i++)
        blk[i] = a2->blk[i] ^ b2->blk[i];
    for (; i < a2->len; i++)
        blk[i] = a2->blk[i];
    len = a2->len;
    zapLeadingZeros();
}

Here is the call graph for this function:

Here is the caller graph for this function:

BigUnsigned::CmpRes BigUnsigned::compareTo

(

const BigUnsigned &

x

)

const

Definition at line 69 of file BigUnsigned.cc.

                                                                   {
    // A bigger length implies a bigger number.
    if (len < x.len)
        return less;
    else if (len > x.len)
        return greater;
    else {
        // Compare blocks one by one from left to right.
        Index i = len;
        while (i > 0) {
            i--;
            if (blk[i] == x.blk[i])
                continue;
            else if (blk[i] > x.blk[i])
                return greater;
            else
                return less;
        }
        // If no blocks differed, the numbers are equal.
        return equal;
    }
}

Here is the caller graph for this function:

template<class X >

X BigUnsigned::convertToPrimitive ( ) const

protected

Definition at line 387 of file BigUnsigned.hh.

                                        {
    if (len == 0)
        // The number is zero; return zero.
        return 0;
    else if (len == 1) {
        // The single block might fit in an X.  Try the conversion.
        X x = X(blk[0]);
        // Make sure the result accurately represents the block.
        if (Blk(x) == blk[0])
            // Successful conversion.
            return x;
        // Otherwise fall through.
    }
    throw "BigUnsigned::to<Primitive>: "
        "Value is too big to fit in the requested type";
}

Here is the caller graph for this function:

template<class X >

X BigUnsigned::convertToSignedPrimitive ( ) const

protected

Definition at line 409 of file BigUnsigned.hh.

                                              {
    X x = convertToPrimitive<X>();
    if (x >= 0)
        return x;
    else
        throw "BigUnsigned::to(Primitive): "
            "Value is too big to fit in the requested type";
}

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

Definition at line 382 of file BigUnsigned.cc.

                                                                          {
    /* Defending against aliased calls is more complex than usual because we
     * are writing to both *this and q.
     * 
     * It would be silly to try to write quotient and remainder to the
     * same variable.  Rule that out right away. */
    if (this == &q)
        throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable";
    /* Now *this and q are separate, so the only concern is that b might be
     * aliased to one of them.  If so, use a temporary copy of b. */
    if (this == &b || &q == &b) {
        BigUnsigned tmpB(b);
        divideWithRemainder(tmpB, q);
        return;
    }

    /*
     * Knuth's definition of mod (which this function uses) is somewhat
     * different from the C++ definition of % in case of division by 0.
     *
     * We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no
     * exceptions thrown.  This allows us to preserve both Knuth's demand
     * that a mod 0 == a and the useful property that
     * (a / b) * b + (a % b) == a.
     */
    if (b.len == 0) {
        q.len = 0;
        return;
    }

    /*
     * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
     * *this at all.  The quotient is 0 and *this is already the remainder (so leave it alone).
     */
    if (len < b.len) {
        q.len = 0;
        return;
    }

    // At this point we know (*this).len >= b.len > 0.  (Whew!)

    /*
     * Overall method:
     *
     * For each appropriate i and i2, decreasing:
     *    Subtract (b << (i blocks and i2 bits)) from *this, storing the
     *      result in subtractBuf.
     *    If the subtraction succeeds with a nonnegative result:
     *        Turn on bit i2 of block i of the quotient q.
     *        Copy subtractBuf back into *this.
     *    Otherwise bit i2 of block i remains off, and *this is unchanged.
     * 
     * Eventually q will contain the entire quotient, and *this will
     * be left with the remainder.
     *
     * subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
     * But on a single iteration, we don't touch the i lowest blocks of blk
     * (and don't use those of subtractBuf) because these blocks are
     * unaffected by the subtraction: we are subtracting
     * (b << (i blocks and i2 bits)), which ends in at least `i' zero
     * blocks. */
    // Variables for the calculation
    Index i, j, k;
    unsigned int i2;
    Blk temp;
    bool borrowIn, borrowOut;

    /*
     * Make sure we have an extra zero block just past the value.
     *
     * When we attempt a subtraction, we might shift `b' so
     * its first block begins a few bits left of the dividend,
     * and then we'll try to compare these extra bits with
     * a nonexistent block to the left of the dividend.  The
     * extra zero block ensures sensible behavior; we need
     * an extra block in `subtractBuf' for exactly the same reason.
     */
    Index origLen = len; // Save real length.
    /* To avoid an out-of-bounds access in case of reallocation, allocate
     * first and then increment the logical length. */
    allocateAndCopy(len + 1);
    len++;
    blk[origLen] = 0; // Zero the added block.

    // subtractBuf holds part of the result of a subtraction; see above.
    Blk *subtractBuf = new Blk[len];

    // Set preliminary length for quotient and make room
    q.len = origLen - b.len + 1;
    q.allocate(q.len);
    // Zero out the quotient
    for (i = 0; i < q.len; i++)
        q.blk[i] = 0;

    // For each possible left-shift of b in blocks...
    i = q.len;
    while (i > 0) {
        i--;
        // For each possible left-shift of b in bits...
        // (Remember, N is the number of bits in a Blk.)
        q.blk[i] = 0;
        i2 = N;
        while (i2 > 0) {
            i2--;
            /*
             * Subtract b, shifted left i blocks and i2 bits, from *this,
             * and store the answer in subtractBuf.  In the for loop, `k == i + j'.
             *
             * Compare this to the middle section of `multiply'.  They
             * are in many ways analogous.  See especially the discussion
             * of `getShiftedBlock'.
             */
            for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
                temp = blk[k] - getShiftedBlock(b, j, i2);
                borrowOut = (temp > blk[k]);
                if (borrowIn) {
                    borrowOut |= (temp == 0);
                    temp--;
                }
                // Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'.
                subtractBuf[k] = temp; 
                borrowIn = borrowOut;
            }
            // No more extra iteration to deal with `bHigh'.
            // Roll-over a borrow as necessary.
            for (; k < origLen && borrowIn; k++) {
                borrowIn = (blk[k] == 0);
                subtractBuf[k] = blk[k] - 1;
            }
            /*
             * If the subtraction was performed successfully (!borrowIn),
             * set bit i2 in block i of the quotient.
             *
             * Then, copy the portion of subtractBuf filled by the subtraction
             * back to *this.  This portion starts with block i and ends--
             * where?  Not necessarily at block `i + b.len'!  Well, we
             * increased k every time we saved a block into subtractBuf, so
             * the region of subtractBuf we copy is just [i, k).
             */
            if (!borrowIn) {
                q.blk[i] |= (Blk(1) << i2);
                while (k > i) {
                    k--;
                    blk[k] = subtractBuf[k];
                }
            } 
        }
    }
    // Zap possible leading zero in quotient
    if (q.blk[q.len - 1] == 0)
        q.len--;
    // Zap any/all leading zeros in remainder
    zapLeadingZeros();
    // Deallocate subtractBuf.
    // (Thanks to Brad Spencer for noticing my accidental omission of this!)
    delete [] subtractBuf;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool BigUnsigned::getBit ( Index  bi ) const

inline

Definition at line 105 of file BigUnsigned.hh.

                                {
        return (getBlock(bi / N) & (Blk(1) << (bi % N))) != 0;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

Blk BigUnsigned::getBlock ( Index  i ) const

inline

Definition at line 92 of file BigUnsigned.hh.

{ return i >= len ? 0 : blk[i]; }

Here is the caller graph for this function:

Index NumberlikeArray< unsigned long >::getCapacity ( ) const

inlineinherited

Definition at line 72 of file NumberlikeArray.hh.

{ return cap;      }

Index NumberlikeArray< unsigned long >::getLength ( ) const

inlineinherited

Definition at line 73 of file NumberlikeArray.hh.

{ return len;      }

template<class X >

void BigUnsigned::initFromPrimitive ( X  x )

protected

Definition at line 356 of file BigUnsigned.hh.

                                       {
    if (x == 0)
        ; // NumberlikeArray already initialized us to zero.
    else {
        // Create a single block.  blk is NULL; no need to delete it.
        cap = 1;
        blk = new Blk[1];
        len = 1;
        blk[0] = Blk(x);
    }
}

Here is the caller graph for this function:

template<class X >

void BigUnsigned::initFromSignedPrimitive ( X  x )

protected

Definition at line 373 of file BigUnsigned.hh.

                                             {
    if (x < 0)
        throw "BigUnsigned constructor: "
            "Cannot construct a BigUnsigned from a negative number";
    else
        initFromPrimitive(x);
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool NumberlikeArray< unsigned long >::isEmpty ( ) const

inlineinherited

Definition at line 75 of file NumberlikeArray.hh.

{ return len == 0; }

bool BigUnsigned::isZero ( ) const

inline

Definition at line 97 of file BigUnsigned.hh.

{ return NumberlikeArray<Blk>::isEmpty(); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 300 of file BigUnsigned.cc.

                                                                     {
    DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
    // If either a or b is zero, set to zero.
    if (a.len == 0 || b.len == 0) {
        len = 0;
        return;
    }
    /*
     * Overall method:
     *
     * Set this = 0.
     * For each 1-bit of `a' (say the `i2'th bit of block `i'):
     *    Add `b << (i blocks and i2 bits)' to *this.
     */
    // Variables for the calculation
    Index i, j, k;
    unsigned int i2;
    Blk temp;
    bool carryIn, carryOut;
    // Set preliminary length and make room
    len = a.len + b.len;
    allocate(len);
    // Zero out this object
    for (i = 0; i < len; i++)
        blk[i] = 0;
    // For each block of the first number...
    for (i = 0; i < a.len; i++) {
        // For each 1-bit of that block...
        for (i2 = 0; i2 < N; i2++) {
            if ((a.blk[i] & (Blk(1) << i2)) == 0)
                continue;
            /*
             * Add b to this, shifted left i blocks and i2 bits.
             * j is the index in b, and k = i + j is the index in this.
             *
             * `getShiftedBlock', a short inline function defined above,
             * is now used for the bit handling.  It replaces the more
             * complex `bHigh' code, in which each run of the loop dealt
             * immediately with the low bits and saved the high bits to
             * be picked up next time.  The last run of the loop used to
             * leave leftover high bits, which were handled separately.
             * Instead, this loop runs an additional time with j == b.len.
             * These changes were made on 2005.01.11.
             */
            for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
                /*
                 * The body of this loop is very similar to the body of the first loop
                 * in `add', except that this loop does a `+=' instead of a `+'.
                 */
                temp = blk[k] + getShiftedBlock(b, j, i2);
                carryOut = (temp < blk[k]);
                if (carryIn) {
                    temp++;
                    carryOut |= (temp == 0);
                }
                blk[k] = temp;
                carryIn = carryOut;
            }
            // No more extra iteration to deal with `bHigh'.
            // Roll-over a carry as necessary.
            for (; carryIn; k++) {
                blk[k]++;
                carryIn = (blk[k] == 0);
            }
        }
    }
    // Zap possible leading zero
    if (blk[len - 1] == 0)
        len--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool NumberlikeArray< unsigned long >::operator!= ( const NumberlikeArray< unsigned long > &  x ) const

inlineinherited

Definition at line 82 of file NumberlikeArray.hh.

                                                          {
        return !operator ==(x);
    }

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

inline

Definition at line 121 of file BigUnsigned.hh.

                                                 {
        return NumberlikeArray<Blk>::operator !=(x);
    }

Here is the call graph for this function:

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

inline

Definition at line 269 of file BigUnsigned.hh.

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

Here is the call graph for this function:

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

inline

Definition at line 320 of file BigUnsigned.hh.

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

Here is the call graph for this function:

BigUnsigned BigUnsigned::operator& ( const BigUnsigned &  x ) const

inline

Definition at line 276 of file BigUnsigned.hh.

                                                                     {
    BigUnsigned ans;
    ans.bitAnd(*this, x);
    return ans;
}

Here is the call graph for this function:

void BigUnsigned::operator&= ( const BigUnsigned &  x )

inline

Definition at line 326 of file BigUnsigned.hh.

                                                         {
    bitAnd(*this, x);
}

Here is the call graph for this function:

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

inline

Definition at line 257 of file BigUnsigned.hh.

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

Here is the call graph for this function:

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

inline

Definition at line 308 of file BigUnsigned.hh.

                                                         {
    multiply(*this, x);
}

Here is the call graph for this function:

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

inline

Definition at line 247 of file BigUnsigned.hh.

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

Here is the call graph for this function:

void BigUnsigned::operator++

(

)

Definition at line 659 of file BigUnsigned.cc.

                              {
    Index i;
    bool carry = true;
    for (i = 0; i < len && carry; i++) {
        blk[i]++;
        carry = (blk[i] == 0);
    }
    if (carry) {
        // Allocate and then increase length, as in divideWithRemainder
        allocateAndCopy(len + 1);
        len++;
        blk[i] = 1;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::operator++

(

int

)

Definition at line 675 of file BigUnsigned.cc.

                                 {
    operator ++();
}

Here is the call graph for this function:

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

inline

Definition at line 302 of file BigUnsigned.hh.

                                                         {
    add(*this, x);
}

Here is the call graph for this function:

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

inline

Definition at line 252 of file BigUnsigned.hh.

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

Here is the call graph for this function:

void BigUnsigned::operator--

(

)

Definition at line 680 of file BigUnsigned.cc.

                              {
    if (len == 0)
        throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
    Index i;
    bool borrow = true;
    for (i = 0; borrow; i++) {
        borrow = (blk[i] == 0);
        blk[i]--;
    }
    // Zap possible leading zero (there can only be one)
    if (blk[len - 1] == 0)
        len--;
}

Here is the caller graph for this function:

void BigUnsigned::operator--

(

int

)

Definition at line 695 of file BigUnsigned.cc.

                                 {
    operator --();
}

Here is the call graph for this function:

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

inline

Definition at line 305 of file BigUnsigned.hh.

                                                         {
    subtract(*this, x);
}

Here is the call graph for this function:

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

inline

Definition at line 262 of file BigUnsigned.hh.

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

Here is the call graph for this function:

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

inline

Definition at line 311 of file BigUnsigned.hh.

                                                         {
    if (x.isZero()) throw "BigUnsigned::operator /=: division by zero";
    /* The following technique is slightly faster than copying *this first
     * when x is large. */
    BigUnsigned 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 BigUnsigned::operator< ( const BigUnsigned &  x ) const

inline

Definition at line 124 of file BigUnsigned.hh.

{ return compareTo(x) == less   ; }

Here is the call graph for this function:

BigUnsigned BigUnsigned::operator<< ( int  b ) const

inline

Definition at line 291 of file BigUnsigned.hh.

                                                       {
    BigUnsigned ans;
    ans.bitShiftLeft(*this, b);
    return ans;
}

Here is the call graph for this function:

void BigUnsigned::operator<<= ( int  b )

inline

Definition at line 335 of file BigUnsigned.hh.

                                           {
    bitShiftLeft(*this, b);
}

Here is the call graph for this function:

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

inline

Definition at line 125 of file BigUnsigned.hh.

{ return compareTo(x) != greater; }

Here is the call graph for this function:

void BigUnsigned::operator= ( const BigUnsigned &  x )

inline

Definition at line 43 of file BigUnsigned.hh.

                                         {
        NumberlikeArray<Blk>::operator =(x);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

bool NumberlikeArray< unsigned long >::operator== ( const NumberlikeArray< unsigned long > &  x ) const

inherited

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

inline

Definition at line 118 of file BigUnsigned.hh.

                                                 {
        return NumberlikeArray<Blk>::operator ==(x);
    }

Here is the call graph for this function:

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

inline

Definition at line 127 of file BigUnsigned.hh.

{ return compareTo(x) == greater; }

Here is the call graph for this function:

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

inline

Definition at line 126 of file BigUnsigned.hh.

{ return compareTo(x) != less   ; }

Here is the call graph for this function:

BigUnsigned BigUnsigned::operator>> ( int  b ) const

inline

Definition at line 296 of file BigUnsigned.hh.

                                                       {
    BigUnsigned ans;
    ans.bitShiftRight(*this, b);
    return ans;
}

Here is the call graph for this function:

void BigUnsigned::operator>>= ( int  b )

inline

Definition at line 338 of file BigUnsigned.hh.

                                           {
    bitShiftRight(*this, b);
}

Here is the call graph for this function:

BigUnsigned BigUnsigned::operator^ ( const BigUnsigned &  x ) const

inline

Definition at line 286 of file BigUnsigned.hh.

                                                                     {
    BigUnsigned ans;
    ans.bitXor(*this, x);
    return ans;
}

Here is the call graph for this function:

void BigUnsigned::operator^= ( const BigUnsigned &  x )

inline

Definition at line 332 of file BigUnsigned.hh.

                                                         {
    bitXor(*this, x);
}

Here is the call graph for this function:

BigUnsigned BigUnsigned::operator| ( const BigUnsigned &  x ) const

inline

Definition at line 281 of file BigUnsigned.hh.

                                                                     {
    BigUnsigned ans;
    ans.bitOr(*this, x);
    return ans;
}

Here is the call graph for this function:

void BigUnsigned::operator|= ( const BigUnsigned &  x )

inline

Definition at line 329 of file BigUnsigned.hh.

                                                         {
    bitOr(*this, x);
}

Here is the call graph for this function:

void BigUnsigned::setBit	(	Index	bi,
		bool	newBit
	)

Definition at line 61 of file BigUnsigned.cc.

                                              {
    Index blockI = bi / N;
    Blk block = getBlock(blockI), mask = Blk(1) << (bi % N);
    block = newBit ? (block | mask) : (block & ~mask);
    setBlock(blockI, block);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BigUnsigned::setBlock	(	Index	i,
		Blk	newBlock
	)

Definition at line 24 of file BigUnsigned.cc.

                                                {
    if (newBlock == 0) {
        if (i < len) {
            blk[i] = 0;
            zapLeadingZeros();
        }
        // If i >= len, no effect.
    } else {
        if (i >= len) {
            // The nonzero block extends the number.
            allocateAndCopy(i+1);
            // Zero any added blocks that we aren't setting.
            for (Index j = len; j < i; j++)
                blk[j] = 0;
            len = i+1;
        }
        blk[i] = newBlock;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 184 of file BigUnsigned.cc.

                                                                     {
    DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
    if (b.len == 0) {
        // If b is zero, copy a.
        operator =(a);
        return;
    } else if (a.len < b.len)
        // If a is shorter than b, the result is negative.
        throw "BigUnsigned::subtract: "
            "Negative result in unsigned calculation";
    // Some variables...
    bool borrowIn, borrowOut;
    Blk temp;
    Index i;
    // Set preliminary length and make room
    len = a.len;
    allocate(len);
    // For each block index that is present in both inputs...
    for (i = 0, borrowIn = false; i < b.len; i++) {
        temp = a.blk[i] - b.blk[i];
        // If a reverse rollover occurred,
        // the result is greater than the block from a.
        borrowOut = (temp > a.blk[i]);
        // Handle an incoming borrow
        if (borrowIn) {
            borrowOut |= (temp == 0);
            temp--;
        }
        blk[i] = temp; // Save the subtraction result
        borrowIn = borrowOut; // Pass the borrow along
    }
    // If there is a borrow left over, decrease blocks until
    // one does not reverse rollover.
    for (; i < a.len && borrowIn; i++) {
        borrowIn = (a.blk[i] == 0);
        blk[i] = a.blk[i] - 1;
    }
    /* If there's still a borrow, the result is negative.
     * Throw an exception, but zero out this object so as to leave it in a
     * predictable state. */
    if (borrowIn) {
        len = 0;
        throw "BigUnsigned::subtract: Negative result in unsigned calculation";
    } else
        // Copy over the rest of the blocks
        for (; i < a.len; i++)
            blk[i] = a.blk[i];
    // Zap leading zeros
    zapLeadingZeros();
}

Here is the call graph for this function:

Here is the caller graph for this function:

int BigUnsigned::toInt

(

)

const

Definition at line 19 of file BigUnsigned.cc.

{ return convertToSignedPrimitive<         int  >(); }

long BigUnsigned::toLong

(

)

const

Definition at line 18 of file BigUnsigned.cc.

{ return convertToSignedPrimitive<         long >(); }

short BigUnsigned::toShort

(

)

const

Definition at line 20 of file BigUnsigned.cc.

{ return convertToSignedPrimitive<         short>(); }

unsigned int BigUnsigned::toUnsignedInt

(

)

const

Definition at line 16 of file BigUnsigned.cc.

{ return convertToPrimitive      <unsigned int  >(); }

unsigned long BigUnsigned::toUnsignedLong

(

)

const

Definition at line 15 of file BigUnsigned.cc.

{ return convertToPrimitive      <unsigned long >(); }

unsigned short BigUnsigned::toUnsignedShort

(

)

const

Definition at line 17 of file BigUnsigned.cc.

{ return convertToPrimitive      <unsigned short>(); }

Here is the caller graph for this function:

void BigUnsigned::zapLeadingZeros ( )

inlineprotected

Definition at line 30 of file BigUnsigned.hh.

                           { 
        while (len > 0 && blk[len - 1] == 0)
            len--;
    }

Here is the caller graph for this function:

Friends And Related Function Documentation

template<class X >

X convertBigUnsignedToPrimitiveAccess ( const BigUnsigned &  a )

friend

Definition at line 88 of file BigInteger.cc.

                                                                   {
    return a.convertToPrimitive<X>();
}

Blk getShiftedBlock ( const BigUnsigned &  num, BigUnsigned::Index  x, unsigned int  y  )

friend

Definition at line 293 of file BigUnsigned.cc.

                                        {
    BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
    BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
    return part1 | part2;
}

Field Documentation

unsigned long * NumberlikeArray< unsigned long >::blk

inherited

Definition at line 34 of file NumberlikeArray.hh.

Index NumberlikeArray< unsigned long >::cap

inherited

Definition at line 30 of file NumberlikeArray.hh.

Index NumberlikeArray< unsigned long >::len

inherited

Definition at line 32 of file NumberlikeArray.hh.

const unsigned int NumberlikeArray< unsigned long >::N

staticinherited

Definition at line 27 of file NumberlikeArray.hh.

---

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

• BigUnsigned.hh
• BigUnsigned.cc