LSST Applications  21.0.0-172-gfb10e10a+18fedfabac,22.0.0+297cba6710,22.0.0+80564b0ff1,22.0.0+8d77f4f51a,22.0.0+a28f4c53b1,22.0.0+dcf3732eb2,22.0.1-1-g7d6de66+2a20fdde0d,22.0.1-1-g8e32f31+297cba6710,22.0.1-1-geca5380+7fa3b7d9b6,22.0.1-12-g44dc1dc+2a20fdde0d,22.0.1-15-g6a90155+515f58c32b,22.0.1-16-g9282f48+790f5f2caa,22.0.1-2-g92698f7+dcf3732eb2,22.0.1-2-ga9b0f51+7fa3b7d9b6,22.0.1-2-gd1925c9+bf4f0e694f,22.0.1-24-g1ad7a390+a9625a72a8,22.0.1-25-g5bf6245+3ad8ecd50b,22.0.1-25-gb120d7b+8b5510f75f,22.0.1-27-g97737f7+2a20fdde0d,22.0.1-32-gf62ce7b1+aa4237961e,22.0.1-4-g0b3f228+2a20fdde0d,22.0.1-4-g243d05b+871c1b8305,22.0.1-4-g3a563be+32dcf1063f,22.0.1-4-g44f2e3d+9e4ab0f4fa,22.0.1-42-gca6935d93+ba5e5ca3eb,22.0.1-5-g15c806e+85460ae5f3,22.0.1-5-g58711c4+611d128589,22.0.1-5-g75bb458+99c117b92f,22.0.1-6-g1c63a23+7fa3b7d9b6,22.0.1-6-g50866e6+84ff5a128b,22.0.1-6-g8d3140d+720564cf76,22.0.1-6-gd805d02+cc5644f571,22.0.1-8-ge5750ce+85460ae5f3,master-g6e05de7fdc+babf819c66,master-g99da0e417a+8d77f4f51a,w.2021.48
LSST Data Management Base Package
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. More...
 
BigIntegeroperator= (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...
 
BigIntegeradd (BigInteger const &b)
 add adds b to this integer. More...
 
BigIntegersubtract (BigInteger const &b)
 subtract subtracts b from this integer. More...
 
BigIntegermultiplyPow2 (unsigned n)
 multiplyPow2 multiplies this integer by 2ⁿ. More...
 
BigIntegermultiply (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.

49  :
50  _digits(digits),
51  _capacity(capacity),
52  _size(0),
53  _sign(0)
54  {}

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.

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

75 { 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.

78 { 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.

68 { 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.

71 { 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.

249  {
250  _sign *= b._sign;
251  if (_sign == 0) {
252  _size = 0;
253  return *this;
254  }
255  _checkCapacity(_size + b._size);
256  if (_size >= b._size) {
257  _size = _mul(_digits, _digits, b._digits, _size, b._size);
258  } else {
259  _size = _mul(_digits, b._digits, _digits, b._size, _size);
260  }
261  return *this;
262 }

◆ multiplyPow2()

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

multiplyPow2 multiplies this integer by 2ⁿ.

Definition at line 214 of file BigInteger.cc.

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

◆ negate()

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

negate multiplies this integer by -1.

Definition at line 103 of file BigInteger.h.

103 { _sign = -_sign; }

◆ operator=()

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

Definition at line 56 of file BigInteger.h.

56  {
57  if (this != &b) {
58  _checkCapacity(b._size);
59  _sign = b._sign;
60  _size = b._size;
61  std::memcpy(_digits, b._digits, sizeof(uint32_t) * b._size);
62  }
63  return *this;
64  }
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 84 of file BigInteger.h.

84  {
85  if (x < 0) {
86  setTo(static_cast<uint64_t>(-x));
87  _sign = -1;
88  } else {
89  setTo(static_cast<uint64_t>(x));
90  }
91  }
double x
void setTo(int64_t x)
setTo sets this integer to the given signed 64 bit integer value.
Definition: BigInteger.h:84

◆ 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.

94  {
95  _checkCapacity(2);
96  _digits[0] = static_cast<uint32_t>(x);
97  _digits[1] = static_cast<uint32_t>(x >> 32);
98  _size = (_digits[1] == 0) ? (_digits[0] != 0) : 2;
99  _sign = (_size != 0);
100  }

◆ setToZero()

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

setToZero sets this integer to zero.

Definition at line 81 of file BigInteger.h.

81 { _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.

201  {
202  if (this != &b) {
203  // Avoid code duplication by computing a - b = -(-a + b).
204  // This only works if a and b are distinct.
205  negate();
206  add(b);
207  negate();
208  } else {
209  setToZero();
210  }
211  return *this;
212 }
void negate()
negate multiplies this integer by -1.
Definition: BigInteger.h:103
BigInteger & add(BigInteger const &b)
add adds b to this integer.
Definition: BigInteger.cc:156

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