lsst::sphgeom::BigInteger Class Reference

BigInteger is an arbitrary precision signed integer class. More...

#include <BigInteger.h>

Public Member Functions
	BigInteger (uint32_t *digits, unsigned capacity)
	This constructor creates a zero-valued integer with the given digit array. More...
BigInteger &	operator= (BigInteger const &b)
int	getSign () const
	getSign returns -1, 0 or 1 if this integer is negative, zero or positive. More...
unsigned	getSize () const
	getSize returns the number of digits in the value of this integer. More...
unsigned	getCapacity () const
	getCapacity returns the number of digits in the underlying digit array. More...
uint32_t const *	getDigits () const
	getDigits returns the underlying digit array. More...
void	setToZero ()
	setToZero sets this integer to zero. More...
void	setTo (int64_t x)
	setTo sets this integer to the given signed 64 bit integer value. More...
void	setTo (uint64_t x)
	setTo sets this integer to the given unsigned 64 bit integer value. More...
void	negate ()
	negate multiplies this integer by -1. More...
BigInteger &	add (BigInteger const &b)
	add adds b to this integer. More...
BigInteger &	subtract (BigInteger const &b)
	subtract subtracts b from this integer. More...
BigInteger &	multiplyPow2 (unsigned n)
	multiplyPow2 multiplies this integer by 2ⁿ. More...
BigInteger &	multiply (BigInteger const &b)
	multiply multiplies this integer by b. More...

Detailed Description

BigInteger is an arbitrary precision signed integer class.

It is intended to be used in applications which need relatively small integers, and only supports addition, subtraction and multiplication.

Internally, a BigInteger consists of a sign and an unsigned magnitude. The magnitude is represented by an array of 32 bit digits, stored from least to most significant. All non-zero integers have at least one digit, the most significant of which is non-zero. Zero is defined to have no digits.

Definition at line 45 of file BigInteger.h.

Constructor & Destructor Documentation

BigInteger()

lsst::sphgeom::BigInteger::BigInteger ( uint32_t *  digits, unsigned  capacity  )

inline

This constructor creates a zero-valued integer with the given digit array.

Definition at line 49 of file BigInteger.h.

                                                     :
        _digits(digits),
        _capacity(capacity),
        _size(0),
        _sign(0)
    {}

Member Function Documentation

add()

BigInteger & lsst::sphgeom::BigInteger::add

(

BigInteger const &

b

)

add adds b to this integer.

Definition at line 156 of file BigInteger.cc.

                                                 {
    if (b._sign == 0) {
        return *this;
    }
    if (_sign == 0) {
        *this = b;
        return *this;
    }
    if (this == &b) {
        return multiplyPow2(1);
    }
    // When adding two magnitudes, the maximum number of bits in the result is
    // one greater than the number of bits B in the larger input. When
    // subtracting them, the maximum result size is B.
    _checkCapacity(std::max(_size, b._size) + 1);
    if (_sign == b._sign) {
        // If the signs of both integers match, add their magnitudes.
        _size = _add(_digits, _digits, b._digits, _size, b._size);
        return *this;
    }
    // Otherwise, subtract the smaller magnitude from the larger. The sign of
    // the result is the sign of the input with the larger magnitude.
    if (_size > b._size) {
        _size = _sub(_digits, _digits, b._digits, _size, b._size);
    } else if (_size < b._size) {
        _size = _sub(_digits, b._digits, _digits, b._size, _size);
        _sign = b._sign;
    } else {
        // Both magnitudes have the same number of digits. Compare and discard
        // leading common digits until we find a digit position where the
        // magnitudes differ, or we determine that they are identical.
        int i = _size;
        for (; i > 0 && _digits[i - 1] == b._digits[i - 1]; --i) {}
        if (i == 0) {
            setToZero();
        } else if (_digits[i - 1] > b._digits[i - 1]) {
            _size = _sub(_digits, _digits, b._digits, i, i);
        } else {
            _size = _sub(_digits, b._digits, _digits, i, i);
            _sign = b._sign;
        }
    }
    return *this;
}

getCapacity()

unsigned lsst::sphgeom::BigInteger::getCapacity ( ) const

inline

getCapacity returns the number of digits in the underlying digit array.

Definition at line 75 of file BigInteger.h.

{ return _capacity; }

getDigits()

uint32_t const* lsst::sphgeom::BigInteger::getDigits ( ) const

inline

getDigits returns the underlying digit array.

Definition at line 78 of file BigInteger.h.

{ return _digits; }

getSign()

int lsst::sphgeom::BigInteger::getSign ( ) const

inline

getSign returns -1, 0 or 1 if this integer is negative, zero or positive.

Definition at line 68 of file BigInteger.h.

{ return _sign; }

getSize()

unsigned lsst::sphgeom::BigInteger::getSize ( ) const

inline

getSize returns the number of digits in the value of this integer.

Definition at line 71 of file BigInteger.h.

{ return _size; }

multiply()

BigInteger & lsst::sphgeom::BigInteger::multiply

(

BigInteger const &

b

)

multiply multiplies this integer by b.

Definition at line 249 of file BigInteger.cc.

                                                      {
    _sign *= b._sign;
    if (_sign == 0) {
        _size = 0;
        return *this;
    }
    _checkCapacity(_size + b._size);
    if (_size >= b._size) {
        _size = _mul(_digits, _digits, b._digits, _size, b._size);
    } else {
        _size = _mul(_digits, b._digits, _digits, b._size, _size);
    }
    return *this;
}

multiplyPow2()

BigInteger & lsst::sphgeom::BigInteger::multiplyPow2

(

unsigned

n

)

multiplyPow2 multiplies this integer by 2ⁿ.

Definition at line 214 of file BigInteger.cc.

                                                {
    if (_sign == 0 || n == 0) {
        return *this;
    }
    // Decompose n into (s, z), where s is a shift by less than 32 bits, and
    // z is the number of trailing zero digits introduced by the shift.
    unsigned const z = (n >> 5);
    unsigned const s = (n & 0x1f);
    unsigned const size = _size + z;
    _checkCapacity(size + 1);
    if (s == 0) {
        // Right-shifting an unsigned 32 bit integer by 32 bits is undefined
        // behavior. Avoid that using this special case code.
        for (unsigned i = _size; i != 0; --i) {
            _digits[i + z - 1] = _digits[i - 1];
        }
        for (unsigned i = z; i != 0; --i) {
            _digits[i - 1] = 0;
        }
        _size = size;
    } else {
        uint32_t low, high = 0;
        for (unsigned i = _size; i != 0; --i, high = low) {
            low = _digits[i - 1];
            _digits[i + z] = (high << s) | (low >> (32 - s));
        }
        _digits[z] = high << s;
        for (unsigned i = z; i != 0; --i) {
            _digits[i] = 0;
        }
        _size = (_digits[size] == 0) ? size: size + 1;
    }
    return *this;
}

negate()

void lsst::sphgeom::BigInteger::negate ( )

inline

negate multiplies this integer by -1.

Definition at line 103 of file BigInteger.h.

{ _sign = -_sign; }

operator=()

BigInteger& lsst::sphgeom::BigInteger::operator= ( BigInteger const &  b )

inline

Definition at line 56 of file BigInteger.h.

                                                 {
        if (this != &b) {
            _checkCapacity(b._size);
            _sign = b._sign;
            _size = b._size;
            std::memcpy(_digits, b._digits, sizeof(uint32_t) * b._size);
        }
        return *this;
    }

setTo() [1/2]

void lsst::sphgeom::BigInteger::setTo ( int64_t  x )

inline

setTo sets this integer to the given signed 64 bit integer value.

Definition at line 84 of file BigInteger.h.

                          {
        if (x < 0) {
            setTo(static_cast<uint64_t>(-x));
            _sign = -1;
        } else {
            setTo(static_cast<uint64_t>(x));
        }
    }

setTo() [2/2]

void lsst::sphgeom::BigInteger::setTo ( uint64_t  x )

inline

setTo sets this integer to the given unsigned 64 bit integer value.

Definition at line 94 of file BigInteger.h.

                           {
        _checkCapacity(2);
        _digits[0] = static_cast<uint32_t>(x);
        _digits[1] = static_cast<uint32_t>(x >> 32);
        _size = (_digits[1] == 0) ? (_digits[0] != 0) : 2;
        _sign = (_size != 0);
    }

setToZero()

void lsst::sphgeom::BigInteger::setToZero ( )

inline

setToZero sets this integer to zero.

Definition at line 81 of file BigInteger.h.

{ _sign = 0; _size = 0; }

subtract()

BigInteger & lsst::sphgeom::BigInteger::subtract

(

BigInteger const &

b

)

subtract subtracts b from this integer.

Definition at line 201 of file BigInteger.cc.

                                                      {
    if (this != &b) {
        // Avoid code duplication by computing a - b = -(-a + b).
        // This only works if a and b are distinct.
        negate();
        add(b);
        negate();
    } else {
        setToZero();
    }
    return *this;
}

---

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

• /j/snowflake/release/lsstsw/stack/Linux64/sphgeom/16.0-4-g5f3a788+20/include/lsst/sphgeom/BigInteger.h
• /j/snowflake/release/lsstsw/stack/Linux64/sphgeom/16.0-4-g5f3a788+20/src/BigInteger.cc