LSST Applications g0265f82a02+c6dfa2ddaf,g1162b98a3f+ffe7eabc7e,g2079a07aa2+1b2e822518,g2bbee38e9b+c6dfa2ddaf,g337abbeb29+c6dfa2ddaf,g36da64cc00+ea84795170,g3ddfee87b4+955a963fd8,g50ff169b8f+2eb0e556e8,g52b1c1532d+90ebb246c7,g555ede804d+955a963fd8,g591dd9f2cf+bac198a2cb,g5ec818987f+420292cfeb,g858d7b2824+d6c9a0a3b8,g876c692160+aabc49a3c3,g8a8a8dda67+90ebb246c7,g8cdfe0ae6a+4fd9e222a8,g99cad8db69+e6cd765486,g9ddcbc5298+a1346535a5,ga1e77700b3+df8f93165b,ga8c6da7877+acd47f83f4,gae46bcf261+c6dfa2ddaf,gb0e22166c9+8634eb87fb,gb3f2274832+12c8382528,gba4ed39666+1ac82b564f,gbb8dafda3b+0574160a1f,gbeb006f7da+dea2fbb49f,gc28159a63d+c6dfa2ddaf,gc86a011abf+d6c9a0a3b8,gcf0d15dbbd+955a963fd8,gdaeeff99f8+1cafcb7cd4,gdc0c513512+d6c9a0a3b8,ge79ae78c31+c6dfa2ddaf,geb67518f79+ba1859f325,gee10cc3b42+90ebb246c7,gf1cff7945b+d6c9a0a3b8,w.2024.13
LSST Data Management Base Package
Loading...
Searching...
No Matches
Public Member Functions | List of all members
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.
 
BigIntegeroperator= (BigInteger const &b)
 
int getSign () const
 getSign returns -1, 0 or 1 if this integer is negative, zero or positive.
 
unsigned getSize () const
 getSize returns the number of digits in the value of this integer.
 
unsigned getCapacity () const
 getCapacity returns the number of digits in the underlying digit array.
 
uint32_t const * getDigits () const
 getDigits returns the underlying digit array.
 
void setToZero ()
 setToZero sets this integer to zero.
 
void setTo (int64_t x)
 setTo sets this integer to the given signed 64 bit integer value.
 
void setTo (uint64_t x)
 setTo sets this integer to the given unsigned 64 bit integer value.
 
void negate ()
 negate multiplies this integer by -1.
 
BigIntegeradd (BigInteger const &b)
 add adds b to this integer.
 
BigIntegersubtract (BigInteger const &b)
 subtract subtracts b from this integer.
 
BigIntegermultiplyPow2 (unsigned n)
 multiplyPow2 multiplies this integer by 2ⁿ.
 
BigIntegermultiply (BigInteger const &b)
 multiply multiplies this integer by b.
 

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 52 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 56 of file BigInteger.h.

56 :
57 _digits(digits),
58 _capacity(capacity),
59 _size(0),
60 _sign(0)
61 {}

Member Function Documentation

◆ add()

BigInteger & lsst::sphgeom::BigInteger::add ( BigInteger const & b)

add adds b to this integer.

Definition at line 163 of file BigInteger.cc.

163 {
164 if (b._sign == 0) {
165 return *this;
166 }
167 if (_sign == 0) {
168 *this = b;
169 return *this;
170 }
171 if (this == &b) {
172 return multiplyPow2(1);
173 }
174 // When adding two magnitudes, the maximum number of bits in the result is
175 // one greater than the number of bits B in the larger input. When
176 // subtracting them, the maximum result size is B.
177 _checkCapacity(std::max(_size, b._size) + 1);
178 if (_sign == b._sign) {
179 // If the signs of both integers match, add their magnitudes.
180 _size = _add(_digits, _digits, b._digits, _size, b._size);
181 return *this;
182 }
183 // Otherwise, subtract the smaller magnitude from the larger. The sign of
184 // the result is the sign of the input with the larger magnitude.
185 if (_size > b._size) {
186 _size = _sub(_digits, _digits, b._digits, _size, b._size);
187 } else if (_size < b._size) {
188 _size = _sub(_digits, b._digits, _digits, b._size, _size);
189 _sign = b._sign;
190 } else {
191 // Both magnitudes have the same number of digits. Compare and discard
192 // leading common digits until we find a digit position where the
193 // magnitudes differ, or we determine that they are identical.
194 int i = _size;
195 for (; i > 0 && _digits[i - 1] == b._digits[i - 1]; --i) {}
196 if (i == 0) {
197 setToZero();
198 } else if (_digits[i - 1] > b._digits[i - 1]) {
199 _size = _sub(_digits, _digits, b._digits, i, i);
200 } else {
201 _size = _sub(_digits, b._digits, _digits, i, i);
202 _sign = b._sign;
203 }
204 }
205 return *this;
206}
table::Key< int > b
BigInteger & multiplyPow2(unsigned n)
multiplyPow2 multiplies this integer by 2ⁿ.
void setToZero()
setToZero sets this integer to zero.
Definition BigInteger.h:88
T max(T... args)

◆ getCapacity()

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

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

Definition at line 82 of file BigInteger.h.

82{ return _capacity; }

◆ getDigits()

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

getDigits returns the underlying digit array.

Definition at line 85 of file BigInteger.h.

85{ 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 75 of file BigInteger.h.

75{ 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 78 of file BigInteger.h.

78{ return _size; }

◆ multiply()

BigInteger & lsst::sphgeom::BigInteger::multiply ( BigInteger const & b)

multiply multiplies this integer by b.

Definition at line 256 of file BigInteger.cc.

256 {
257 _sign *= b._sign;
258 if (_sign == 0) {
259 _size = 0;
260 return *this;
261 }
262 _checkCapacity(_size + b._size);
263 if (_size >= b._size) {
264 _size = _mul(_digits, _digits, b._digits, _size, b._size);
265 } else {
266 _size = _mul(_digits, b._digits, _digits, b._size, _size);
267 }
268 return *this;
269}

◆ multiplyPow2()

BigInteger & lsst::sphgeom::BigInteger::multiplyPow2 ( unsigned n)

multiplyPow2 multiplies this integer by 2ⁿ.

Definition at line 221 of file BigInteger.cc.

221 {
222 if (_sign == 0 || n == 0) {
223 return *this;
224 }
225 // Decompose n into (s, z), where s is a shift by less than 32 bits, and
226 // z is the number of trailing zero digits introduced by the shift.
227 unsigned const z = (n >> 5);
228 unsigned const s = (n & 0x1f);
229 unsigned const size = _size + z;
230 _checkCapacity(size + 1);
231 if (s == 0) {
232 // Right-shifting an unsigned 32 bit integer by 32 bits is undefined
233 // behavior. Avoid that using this special case code.
234 for (unsigned i = _size; i != 0; --i) {
235 _digits[i + z - 1] = _digits[i - 1];
236 }
237 for (unsigned i = z; i != 0; --i) {
238 _digits[i - 1] = 0;
239 }
240 _size = size;
241 } else {
242 uint32_t low, high = 0;
243 for (unsigned i = _size; i != 0; --i, high = low) {
244 low = _digits[i - 1];
245 _digits[i + z] = (high << s) | (low >> (32 - s));
246 }
247 _digits[z] = high << s;
248 for (unsigned i = z; i != 0; --i) {
249 _digits[i] = 0;
250 }
251 _size = (_digits[size] == 0) ? size: size + 1;
252 }
253 return *this;
254}
double z
Definition Match.cc:44

◆ negate()

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

negate multiplies this integer by -1.

Definition at line 110 of file BigInteger.h.

110{ _sign = -_sign; }

◆ operator=()

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

Definition at line 63 of file BigInteger.h.

63 {
64 if (this != &b) {
65 _checkCapacity(b._size);
66 _sign = b._sign;
67 _size = b._size;
68 std::memcpy(_digits, b._digits, sizeof(uint32_t) * b._size);
69 }
70 return *this;
71 }
T memcpy(T... args)

◆ 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 91 of file BigInteger.h.

91 {
92 if (x < 0) {
93 setTo(static_cast<uint64_t>(-x));
94 _sign = -1;
95 } else {
96 setTo(static_cast<uint64_t>(x));
97 }
98 }
void setTo(int64_t x)
setTo sets this integer to the given signed 64 bit integer value.
Definition BigInteger.h:91

◆ 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 101 of file BigInteger.h.

101 {
102 _checkCapacity(2);
103 _digits[0] = static_cast<uint32_t>(x);
104 _digits[1] = static_cast<uint32_t>(x >> 32);
105 _size = (_digits[1] == 0) ? (_digits[0] != 0) : 2;
106 _sign = (_size != 0);
107 }

◆ setToZero()

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

setToZero sets this integer to zero.

Definition at line 88 of file BigInteger.h.

88{ _sign = 0; _size = 0; }

◆ subtract()

BigInteger & lsst::sphgeom::BigInteger::subtract ( BigInteger const & b)

subtract subtracts b from this integer.

Definition at line 208 of file BigInteger.cc.

208 {
209 if (this != &b) {
210 // Avoid code duplication by computing a - b = -(-a + b).
211 // This only works if a and b are distinct.
212 negate();
213 add(b);
214 negate();
215 } else {
216 setToZero();
217 }
218 return *this;
219}
void negate()
negate multiplies this integer by -1.
Definition BigInteger.h:110
BigInteger & add(BigInteger const &b)
add adds b to this integer.

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