Files CCore/inc/math/Integer.h CCore/src/math/Integer.cpp
Integer is a class, which simulates integer numbers. It can represent numbers from a huge value range. This range is limited only by the available memory.
Internally an Integer value is represented using the array of units. A unit has an unsigned integral type — the unit type. The range of units is called the body. Any range of units can be regarded as a number. Let's N be the number of bits of the unit type and B be 2N. Then the range of units (U0,...,Un) can be regarded as an unsigned integer using the base-B positional integer representation, i.e. it has the value U0+U1*B+...+Un-1*Bn-1+Un*Bn. It also can be regarded as a signed integer, in this case the most significant unit (MSU) is treated especially. It regarded as a signed number with the value from the interval [-B/2,B/2). The value of the range then equals U0+U1*B+...+Un-1*Bn-1+signed(Un)*Bn. All units except the most significant (which is the last in the range) have values from the interval [0,B), and the MSU is regarded as a value from the interval [-B/2,B/2). The Integer itself uses the signed interpretation. But some low-level algorithms are working with the unsigned numbers.
An Integer value is stored in the normalized form, i.e. you cannot represent it with a less number of units. It means that the MSU is not a signed extension of the previous unit. The null value is represented by the empty array.
template <class Algo,
template <class T,class A> class ArrayType = RefArray ,
template <class T,class F=GetNoThrowFlags<T> > class ArrayAlgoType = ArrayAlgo >
class Integer
{
public:
using AlgoType = Algo ;
using Unit = typename Algo::Unit ;
static const unsigned UnitBits = Algo::UnitBits ;
using TempArrayType = DynArray<Unit,ArrayAlgoType<Unit> > ;
private:
ArrayType<Unit,ArrayAlgoType<Unit> > body;
Integer is a template. The first and most important template parameter is an Algorithm package. This parameter determines the unit type and the set of low-level functions to perform the integer operations. These functions cannot be implemented efficiently in general, so you should use some "fast" implementation for your particular target CPU. For example, you can use the GMP library for that purpose.
The second and third template parameters define the array to be used to store an integer body. The second must be either the RefArray(default) or the AtomicRefArray. The third should almost never be used with non-default value. You can use a non-default value for this parameter to employ, for example, custom memory allocation functions. See the Array page for more information about arrays and array algorithms.
AlgoType is the inner type, an alias of the first template parameter.
Unit is the unit type.
UnitBits is the number of unit bits.
TempArrayType is a Unit DynArray with the provided array algorithm package. This type is intended to be used as the temporary storage type. This type is used to implement some operations and can be used for similar purposes.
The body of the Integer is stored in the private field body. This field has the type RefArray or AtomicRefArray. It means it is efficiently copyable and multiple objects can share the same body.
public:
// generic constructor
template <class Builder>
Integer(DoBuildType,Builder builder) : body(DoBuild,builder) { normalize(); }
// constructors
Integer() noexcept;
Integer(StrLen str);
template <class UInt>
Integer(UInt val);
template <class SInt>
Integer(SInt val);
~Integer();
You can create an Integer using the generic constructor or using special constructors. The generic constructor uses the provided builder to fill the integer body and then performs the normalization.
The default constructor creates the null value. It doesn't throw.
You can create an Integer from a string (the usual decimal representation is assumed) or from any "short" integer, signed or unsigned. These constructors are implicit, so you can use them to silently cast operation arguments.
// methods
CmpResult sign() const;
bool operator ! () const;
struct BitsOf
{
ulen units;
unsigned msbits;
BitsOf(ulen units_,unsigned msbits_) : units(units_),msbits(msbits_) {}
template <class UInt>
void total(UInt &ret) const;
unsigned total() const;
};
BitsOf bitsOf() const;
Integer sq() const;
Integer pow(unsigned deg) const;
void modify() { body.modify(); }
void cloneTo(Integer &ret) const;
Integer & set_null();
PtrLen<const Unit> getBody() const;
PtrLenReverse<const Unit> getBodyReverse() const;
bool isOdd() const;
bool isEven() const;
sign() returns the sign of the number as the CmpResult.
operator ! returns true, if the number is zero.
bitsOf() returns the number of bits of the number. The value is returned as a structure with two fields. The fields units is the number of full unit bits. The field msbits is the number of bits of the MSU, the total bit count therefore is units*UnitBits + msbits. You can convert this result into a usual unsigned value using the method total(). The total() without arguments returns the unsigned value. The total() with argument returns the value of a desired type in the given argument. An exception is thrown in case of overflow. For negative numbers the leading 1 is not counted. I.e. is the number N is non-negative, then NBits is the minimum such that N<2NBits. But if the N is negative, then NBits is the minimum such that N>=-2NBits.
sq() returns the square of the number.
pow() returns the power of the number.
modify() "unshares" the body. After this method the number will have the separate body.
cloneTo() makes clone of the number at the given argument. The argument will have the separate body. This method is useful in multi-task situations.
set_null() sets the number to zero and returns the reference to self.
getBody() returns the range over the number body.
getBodyReverse() returns the reverse range over the number body.
isOdd() returns true, if the number is odd.
isEven() returns true, if the number is even.
// cast template <class UInt> UInt cast() const;
cast() does the cast to the given unsigned integral type. The reduction by module is performed to get the value. On bit patterns: extra bits are skipped.
CmpResult objCmp(const Integer &b) const;
objCmp() performs the 3-way comparision with the argument.
// operators
static Integer Neg(PtrLen<const Unit> a);
static Integer Add(PtrLen<const Unit> a,PtrLen<const Unit> b);
static Integer Sub(PtrLen<const Unit> a,PtrLen<const Unit> b);
static Integer Mul(PtrLen<const Unit> a,PtrLen<const Unit> b);
static Integer Sq(PtrLen<const Unit> a);
static Integer Div(PtrLen<const Unit> a,PtrLen<const Unit> b);
static Integer Mod(PtrLen<const Unit> a,PtrLen<const Unit> b);
static Integer LShift(PtrLen<const Unit> a,unsigned shift);
static Integer RShift(PtrLen<const Unit> a,unsigned shift);
struct DivMod
{
Integer div;
Integer mod;
DivMod(PtrLen<const Unit> a,PtrLen<const Unit> b);
};
This set of static functions makes the result of operation on numbers. The argument(s) is given not as an Integer value, but as the range over a number body.
Neg() calculates -a.
Add() calculates a+b.
Sub() calculates a-b.
Mul() calculates a*b.
Sq() calculates a2.
Div() calculates a/b. More precisely, the result is [a/b].
Mod() calculates a%b. Both division operations throw an exception if the divisor is zero. The following is true: a == (a/b)*b + (a%b). If the b is positive, the remainder is non-negative. Otherwise it is non-positive.
LShift() calculates a<<shift. In other words, it calculates a*2shift.
RShift() calculates the arithmetic a>>shift, i.e. the leading bit is preserved. In other words, it calculates a/2shift.
DivMod is a Class-function, it calculates the quotient (in the field div) and the remainder (in the field mod) simultaneously.
// operators Integer & neg(); Integer & revsub(const Integer &b); Integer & operator += (const Integer &b); Integer & operator -= (const Integer &b); Integer & operator *= (const Integer &b); Integer & operator /= (const Integer &b); Integer & operator %= (const Integer &b); Integer & operator <<= (unsigned shift); Integer & operator >>= (unsigned shift);
This set of methods and operators perform self-modifying operations. They return the reference to self.
neg() negates the number: obj = - obj.
revsub() does the "reversed subtraction", i.e. obj = b - obj.
operator X= does the usual obj = obj X b operation.
// operators
Integer operator - () const;
friend Integer operator + (const Integer &a,const Integer &b);
friend Integer operator - (const Integer &a,const Integer &b);
friend Integer operator * (const Integer &a,const Integer &b);
friend Integer operator / (const Integer &a,const Integer &b);
friend Integer operator % (const Integer &a,const Integer &b);
Integer operator << (unsigned shift) const;
Integer operator >> (unsigned shift) const;
DivMod divmod(const Integer &b) const;
friend bool operator == (const Integer &a,const Integer &b);
friend bool operator != (const Integer &a,const Integer &b);
friend bool operator < (const Integer &a,const Integer &b);
friend bool operator > (const Integer &a,const Integer &b);
friend bool operator <= (const Integer &a,const Integer &b);
friend bool operator >= (const Integer &a,const Integer &b);
The unary operator - returns the negated number: -obj.
The family of binary operators: +, -, *, /, %, perform the usual integer arithmetic operations.
The family of binary comparison operators: ==, !=, <, >, <=, >=, perform the usual integer comparison operations.
operator << returns the obj << shift.
operator >> returns the obj >> shift.
divmod() returns the the quotient and the remainder using the DivMod structure.
template <class SUInt> Integer & revsub(SUInt val); template <class SUInt> Integer & operator += (SUInt val); template <class SUInt> Integer & operator -= (SUInt val); template <class SUInt> Integer & operator *= (SUInt val); template <class SUInt> Integer & operator /= (SUInt val); template <class SUInt> Integer & operator %= (SUInt val); template <class SUInt> friend Integer operator + (const Integer &a,SUInt b); template <class SUInt> friend Integer operator + (SUInt a,const Integer &b); template <class SUInt> friend Integer operator - (const Integer &a,SUInt b); template <class SUInt> friend Integer operator - (SUInt a,const Integer &b); template <class SUInt> friend Integer operator * (const Integer &a,SUInt b); template <class SUInt> friend Integer operator * (SUInt a,const Integer &b); template <class SUInt> friend Integer operator / (const Integer &a,SUInt b); template <class SUInt> friend Integer operator / (SUInt a,const Integer &b); template <class SUInt> friend Integer operator % (const Integer &a,SUInt b); template <class SUInt> friend Integer operator % (SUInt a,const Integer &b); template <class SUInt> DivMod divmod(SUInt b) const; template <class SUInt> CmpResult cmp(SUInt b) const; template <class SUInt> friend bool operator == (const Integer &a,SUInt b); template <class SUInt> friend bool operator == (SUInt a,const Integer &b); template <class SUInt> friend bool operator != (const Integer &a,SUInt b); template <class SUInt> friend bool operator != (SUInt a,const Integer &b); template <class SUInt> friend bool operator < (const Integer &a,SUInt b); template <class SUInt> friend bool operator < (SUInt a,const Integer &b); template <class SUInt> friend bool operator > (const Integer &a,SUInt b); template <class SUInt> friend bool operator > (SUInt a,const Integer &b); template <class SUInt> friend bool operator <= (const Integer &a,SUInt b); template <class SUInt> friend bool operator <= (SUInt a,const Integer &b); template <class SUInt> friend bool operator >= (const Integer &a,SUInt b); template <class SUInt> friend bool operator >= (SUInt a,const Integer &b);
This set of operators and methods handles the mixed-type cases, when one of the argument is a simple signed or unsigned integral type. They are introduced for efficiency reason.
cmp() performs the comparison with one of simple signed or unsigned integral type.
// print object using PrintOptType = IntegerPrintOpt ; template <class P> void print(P &out,PrintOptType opt) const; // swap/move objects void objSwap(Integer &obj); explicit Integer(ToMoveCtor<Integer> obj); };
Integer is printable, swappable and movable type. Integer print options are: the output width and the show-sign flag. The output is always decimal.
struct IntegerPrintOpt
{
ulen width;
IntShowSign show_sign;
void setDefault();
IntegerPrintOpt() { setDefault(); }
IntegerPrintOpt(const char *ptr,const char *lim);
//
// [+][width=0]
//
};
RandomInteger is a random Integer.
template <class Integer>
class RandomInteger : public Integer
{
....
public:
template <class Random>
RandomInteger(ulen n,Random &random);
~RandomInteger();
};
Constructor takes two arguments. The first argument is the body length in units. The second is some Random object. An Integer is created with the given body length and randomly filled body units. So the value is uniformly distributed in the range [-Bn/2,Bn/2).
template <class Integer> Integer GCDiv(const Integer &a,const Integer &b); template <class Integer> int QSym(const Integer &a,const Integer &b);
GCDiv() calculates the GCD of the given arguments. The return value is non-negative.
QSym() calculates the quadratic symbol (aka Jacobi symbol) of the given arguments. a and b must be coprime and b must be odd, otherwise an exception is thrown.
The algorithm package Algo must comply with the following pattern. Functions, operating on long numbers expects the arguments in the form (const Unit *a,ulen na), where a is a number body and na is the body length. An argument can be regarded as a signed number or as an unsigned number. In the last case the function name starts from the U.
struct Algo
{
// types and consts
using Unit = ??? ; // unsigned integral type
static const unsigned UnitBits = ??? ;
static const Unit MaxUnit = ??? ;
static const Unit MSBit = ??? ;
Unit is a unit type. It must be an unsigned integral type.
UnitBits is the number of bits of Unit.
MaxUnit is the maximum unit, all bits are set.
MSBit is the most significant bit.
// functions static Unit SignExt(const Unit *a,ulen na); static unsigned CountZeroMSB(Unit a); static Unit DoubleUDiv(Unit hi,Unit lo,Unit den); // hi<den
SignExt() returns the sign extension unit for the given argument. I.e. it is the most significant bit of the argument, propagated to the unit.
CountZeroMSB() counts the number of zero most significant bits of the given unit.
DoubleUDiv() performs the long unsigned division. It divides the double-size number with the high part hi and the low part lo by the divisor den. It is assumed, that hi < den. The result is returned (it is representable by the unit).
// const operators static CmpResult USign(const Unit *a,ulen na); static CmpResult Sign(const Unit *a,ulen na); static CmpResult UCmp(const Unit *a,const Unit *b,ulen nab); static CmpResult UCmp(const Unit *a,ulen na,const Unit *b,ulen nb); static CmpResult Cmp(const Unit *a,ulen na,const Unit *b,ulen nb); static ulen UNormalize(const Unit *a,ulen na); static ulen Normalize(const Unit *a,ulen na);
USign() returns the sign of the argument. It always >=0.
Sign() returns the sign of the argument.
UCmp() compares arguments of the same length.
UCmp() compares arguments.
Cmp() compares arguments.
UNormalize() does normalization of the argument. It returns the normalized length. It drop the most significant units, equals zero.
Normalize() does normalization of the argument. It returns the normalized length. It drop the most significant units, equals propagated MSB of the previous unit.
// additive operators static Unit/* c */ UNeg(Unit *a,ulen na); static Unit/* msu */ Neg(Unit *a,ulen na); static Unit/* c */ UAddUnit(Unit *a,ulen na,Unit b); static Unit/* c */ USubUnit(Unit *a,ulen na,Unit b); static Unit/* c */ UAdd(Unit *restrict b,const Unit *a,ulen nab); static Unit/* msu */ Add(Unit *restrict b,ulen nb,const Unit *a,ulen na); // nb>=na static Unit/* c */ USub(Unit *restrict b,const Unit *a,ulen nab); static Unit/* msu */ Sub(Unit *restrict b,ulen nb,const Unit *a,ulen na); // nb>=na static Unit/* msu */ RevSub(Unit *restrict b,ulen nb,const Unit *a,ulen na); // nb>=na
The bit C is a carry from or a borrow to the MSU when doing unsigned operations.
UNeg() negates the argument in-place. The bit C is returned.
Neg() negates the argument in-place. The result representation requires one additional unit, this unit is returned. I.e. the result length is na+1 and the resulting MSU is not stored in the original body, but returned by the function.
UAddUnit() adds the unit b to the a in-place. The bit C is returned. If na==0, b is returned.
USubUnit() subtracts the unit b from the a in-place. The bit C is returned. If na==0, b is returned.
UAdd() adds a to b in-place. The bit C is returned. a and b have the same length nab and do not overlap.
Add() adds a to b in-place. The length of b must be greater or equal than the length of a, a and b do not overlap. The result representation requires one additional unit, this unit is returned. I.e. the result length is nb+1 and the resulting MSU is not stored in the b body, but returned by the function.
USub() subtracts a from b in-place. The bit C is returned. a and b have the same length nab and does not overlap.
Sub() subtracts a from b in-place. The length of b must be greater or equal than the length of a, a and b do not overlap. The result representation requires one additional unit, this unit is returned. I.e. the result length is nb+1 and the resulting MSU is not stored in the b body, but returned by the function.
RevSub() subtracts b from a in-place (reversed subtraction). The length of b must be greater or equal than the length of a, a and b do not overlap. The result representation requires one additional unit, this unit is returned. I.e. the result length is nb+1 and the resulting MSU is not stored in the b body, but returned by the function.
// shift operators static Unit/* msu */ ULShift(Unit *a,ulen na,unsigned shift); // 0<shift<UnitBits static Unit/* msu */ LShift(Unit *restrict b,const Unit *a,ulen nab,unsigned shift); // 0<shift<UnitBits static Unit/* msu */ ShiftUp(Unit *a,ulen na,ulen delta,unsigned shift); // a[na+delta] , 0<shift<UnitBits static void RShift(Unit *restrict b,const Unit *a,ulen nab,unsigned shift); // 0<shift<UnitBits static void ShiftDown(Unit *a,ulen na,ulen delta,unsigned shift); // a[na+delta] , 0<shift<UnitBits
In the following shift operations the shift length shift must be greater 0 and less than UnitBits.
ULShift() shifts left in-place and returns the MSU. The result representation requires one additional unit, this unit is returned. I.e. the result length is na+1 and the resulting MSU is not stored in the a body, but returned by the function.
LShift() shifts left out-of-place and returns the MSU. a is the argument and b is to store the result. a and b do not overlap. The result representation requires one additional unit, this unit is returned. I.e. the result length is nab+1 and the resulting MSU is not stored in the b body, but returned by the function.
ShiftUp() combines the left shift and the move up. It shifts the na units starting from the a and moves the result up by the delta units. The MSU is not placed in the buffer but returned.
RShift() shifts right out-of-place. a is the argument and b is to store the result. a and b do not overlap.
ShiftDown() combines the right shift and the move down. It shifts the na units starting from the a+delta and moves the result down by the delta units.
// multiplicative operators static void UMul(Unit *restrict c,const Unit *a,ulen na,const Unit *b,ulen nb); // nc==na+nb static void UMulLo(Unit *restrict c,ulen nc,const Unit *a,ulen na,const Unit *b,ulen nb); // nc<=na+nb static void Mul(Unit *restrict c,const Unit *a,ulen na,const Unit *b,ulen nb); // nc==na+nb static void Sq(Unit *restrict c,const Unit *a,ulen na); // nc==2*na
UMul() calculates the product of the arguments and places the result into the c. The length of the c must be na+nb. The input and output bodies do not overlap.
UMulLo() calculates the product of the arguments and places the lower part of the result into the c. The length of the c must not exceed na+nb. The input and output bodies do not overlap.
Mul() calculates the product of the arguments and places the result into the c. The length of the c must be na+nb. The input and output bodies do not overlap.
Sq() calculates the square of the argument a and places the result into the c. The length of the c must be 2*na. The input and output bodies do not overlap.
// data functions static void Null(Unit *a,ulen na); static void MoveUp(Unit *a,ulen na,ulen delta); // a[na+delta] static void MoveDown(Unit *a,ulen na,ulen delta); // a[na+delta] };
Null() nullifies the result.
MoveUp() moves up the body inside the larger buffer by the delta units. I.e. a[i+delta] = a[i].
MoveDown() moves down the body inside the larger buffer by the delta units. I.e. a[i] = a[i+delta].
The following content is not required by the Integer, but should also be included in a proper implementation.
struct Algo
{
....
// functions
static Unit SignExt(Unit a);
static CmpResult SignCmp(Unit a,Unit b);
static unsigned CountZeroLSB(Unit a);
SignExt() returns the sign extension of the given unit. I.e. it propagates the sign bit of the a.
SignCmp() performs the signed comparison of the given units.
CountZeroLSB() counts the number of zero least significant bits of the given unit.
// const operators static CmpResult Cmp(const Unit *a,const Unit *b,ulen nab);
Cmp() compares arguments of the same length.
// additive operators static Unit/* msu */ AddUnit(Unit *a,ulen na,Unit b); static Unit/* msu */ SubUnit(Unit *a,ulen na,Unit b); static Unit/* c */ UNegAddUnit(Unit *a,ulen na,Unit b); static Unit/* msu */ NegAddUnit(Unit *a,ulen na,Unit b); static Unit/* c */ URevSub(Unit *restrict b,const Unit *a,ulen nab);
AddUnit() adds the unit b (regarded as an unsigned number) to a in-place. The result representation requires one additional unit, this unit is returned. If na==0, b is returned.
SubUnit() subtracts the unit b (regarded as an unsigned number) from a in-place. The result representation requires one additional unit, this unit is returned. If na==0, -b is returned.
UNegAddUnit() subtracts a from b (regarded as an unsigned number) in-place (reversed subtraction). The bit C is returned. If na==0, -b is returned.
NegAddUnit() subtracts a from b (regarded as an unsigned number) in-place (reversed subtraction). The result representation requires one additional unit, this unit is returned. If na==0, b is returned.
URevSub() subtracts b from a in-place (reversed subtraction). The bit C is returned. a and b have the same length nab and does not overlap.
// shift operators static Unit/* msu */ UShiftUp(Unit *a,ulen na,ulen delta,unsigned shift); // a[na+delta] , 0<shift<UnitBits static void URShift(Unit *a,ulen na,unsigned shift); // 0<shift<UnitBits static void UShiftDown(Unit *a,ulen na,ulen delta,unsigned shift); // a[na+delta] , 0<shift<UnitBits
UShiftUp() combines the left shift and the move up. It shifts the na units starting from the a and moves the result up by the delta units. The MSU is not placed in the buffer but returned.
URShift() shifts right in-place.
UShiftDown() combines the right shift and the move down. It shifts the na units starting from the a+delta and moves the result down by the delta units.
// multiplicative operators static Unit/* c */ UMac(Unit *restrict c,const Unit *a,ulen na,const Unit *b,ulen nb); // nc==na+nb static void USq(Unit *restrict c,const Unit *a,ulen na); // nc==2*na };
UMac() performs the "multiplication and addition" operation. I.e. a and b are multiplied and added to c. The length of the c must be na+nb. The input and output bodies do not overlap. The bit C is returned.
USq() calculates the square of the argument a and places the result into the c. The length of the c must be 2*na. The input and output bodies do not overlap.
There is a default slow implementaton of this algorithm package for all unsigned integral units. This implementation is slow, for example, it has quadratic complexity of the multiplication operations. But it is generic, it does not require any CPU-specific assembler code. This package can be used as an algorithmic reference and for the comparative testing.
Any target must provide the fast implementation.