All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Static Public Member Functions | Public Attributes | Protected Member Functions | Friends | List of all members
ttmath::UInt< value_size > Class Template Reference

UInt implements a big integer value without a sign. More...

#include <ttmathuint.h>

Public Member Functions

template<class ostream_type >
void PrintTable (ostream_type &output) const
 
template<class char_type , class ostream_type >
void PrintLog (const char_type *msg, ostream_type &output) const
 
template<class char_type , class ostream_type >
void PrintLog (const char_type *msg, uint carry, ostream_type &output) const
 
uint Size () const
 
void SetZero ()
 
void SetOne ()
 
void SetMax ()
 
void SetMin ()
 
void Swap (UInt< value_size > &ss2)
 
void SetFromTable (const uint *temp_table, uint temp_table_len)
 
uint AddOne ()
 
uint SubOne ()
 
uint Rcl (uint bits, uint c=0)
 
uint Rcr (uint bits, uint c=0)
 
uint CompensationToLeft ()
 
bool FindLeadingBit (uint &table_id, uint &index) const
 
bool FindLowestBit (uint &table_id, uint &index) const
 
uint GetBit (uint bit_index) const
 
uint SetBit (uint bit_index)
 
void BitAnd (const UInt< value_size > &ss2)
 
void BitOr (const UInt< value_size > &ss2)
 
void BitXor (const UInt< value_size > &ss2)
 
void BitNot ()
 
void BitNot2 ()
 
uint MulInt (uint ss2)
 
template<uint result_size>
void MulInt (uint ss2, UInt< result_size > &result) const
 
uint Mul (const UInt< value_size > &ss2, uint algorithm=100)
 
void MulBig (const UInt< value_size > &ss2, UInt< value_size *2 > &result, uint algorithm=100)
 
uint Mul1 (const UInt< value_size > &ss2)
 
void Mul1Big (const UInt< value_size > &ss2_, UInt< value_size *2 > &result)
 
uint Mul2 (const UInt< value_size > &ss2)
 
void Mul2Big (const UInt< value_size > &ss2, UInt< value_size *2 > &result)
 
uint Mul3 (const UInt< value_size > &ss2)
 
void Mul3Big (const UInt< value_size > &ss2, UInt< value_size *2 > &result)
 
uint MulFastest (const UInt< value_size > &ss2)
 
void MulFastestBig (const UInt< value_size > &ss2, UInt< value_size *2 > &result)
 
uint DivInt (uint divisor, uint *remainder=0)
 
uint DivInt (uint divisor, uint &remainder)
 
uint Div (const UInt< value_size > &divisor, UInt< value_size > *remainder=0, uint algorithm=3)
 
uint Div (const UInt< value_size > &divisor, UInt< value_size > &remainder, uint algorithm=3)
 
uint Div1 (const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
 
uint Div1 (const UInt< value_size > &divisor, UInt< value_size > &remainder)
 
uint Div2 (const UInt< value_size > &divisor, UInt< value_size > *remainder=0)
 
uint Div2 (const UInt< value_size > &divisor, UInt< value_size > &remainder)
 
uint Div3 (const UInt< value_size > &ss2, UInt< value_size > *remainder=0)
 
uint Div3 (const UInt< value_size > &ss2, UInt< value_size > &remainder)
 
uint Pow (UInt< value_size > pow)
 
void Sqrt ()
 
void ClearFirstBits (uint n)
 
bool IsTheHighestBitSet () const
 
bool IsTheLowestBitSet () const
 
bool IsOnlyTheHighestBitSet () const
 
bool IsOnlyTheLowestBitSet () const
 
bool IsZero () const
 
bool AreFirstBitsZero (uint bits) const
 
template<uint argument_size>
uint FromUInt (const UInt< argument_size > &p)
 
template<uint argument_size>
uint FromInt (const UInt< argument_size > &p)
 
uint FromUInt (uint value)
 
uint FromInt (uint value)
 
uint FromInt (sint value)
 
template<uint argument_size>
UInt< value_size > & operator= (const UInt< argument_size > &p)
 
UInt< value_size > & operator= (const UInt< value_size > &p)
 
UInt< value_size > & operator= (uint i)
 
 UInt (uint i)
 
UInt< value_size > & operator= (sint i)
 
 UInt (sint i)
 
uint FromUInt (ulint n)
 
uint FromInt (ulint n)
 
uint FromInt (slint n)
 
UInt< value_size > & operator= (ulint n)
 
 UInt (ulint n)
 
UInt< value_size > & operator= (slint n)
 
 UInt (slint n)
 
 UInt (const char *s)
 
 UInt (const std::string &s)
 
 UInt (const wchar_t *s)
 
 UInt (const std::wstring &s)
 
 UInt ()
 
 UInt (const UInt< value_size > &u)
 
template<uint argument_size>
 UInt (const UInt< argument_size > &u)
 
 ~UInt ()
 
uint ToUInt () const
 
uint ToUInt (uint &result) const
 
uint ToInt (uint &result) const
 
uint ToInt (sint &result) const
 
uint ToUInt (ulint &result) const
 
uint ToInt (ulint &result) const
 
uint ToInt (slint &result) const
 
template<class string_type >
void ToStringBase (string_type &result, uint b=10, bool negative=false) const
 
void ToString (std::string &result, uint b=10) const
 
std::string ToString (uint b=10) const
 
void ToString (std::wstring &result, uint b=10) const
 
std::wstring ToWString (uint b=10) const
 
uint FromString (const char *s, uint b=10, const char **after_source=0, bool *value_read=0)
 
uint FromString (const std::string &s, uint b=10)
 
UInt< value_size > & operator= (const char *s)
 
UInt< value_size > & operator= (const std::string &s)
 
uint FromString (const wchar_t *s, uint b=10, const wchar_t **after_source=0, bool *value_read=0)
 
uint FromString (const std::wstring &s, uint b=10)
 
UInt< value_size > & operator= (const wchar_t *s)
 
UInt< value_size > & operator= (const std::wstring &s)
 
bool CmpSmaller (const UInt< value_size > &l, sint index=-1) const
 
bool CmpBigger (const UInt< value_size > &l, sint index=-1) const
 
bool CmpEqual (const UInt< value_size > &l, sint index=-1) const
 
bool CmpSmallerEqual (const UInt< value_size > &l, sint index=-1) const
 
bool CmpBiggerEqual (const UInt< value_size > &l, sint index=-1) const
 
bool operator< (const UInt< value_size > &l) const
 
bool operator> (const UInt< value_size > &l) const
 
bool operator== (const UInt< value_size > &l) const
 
bool operator!= (const UInt< value_size > &l) const
 
bool operator<= (const UInt< value_size > &l) const
 
bool operator>= (const UInt< value_size > &l) const
 
UInt< value_size > operator- (const UInt< value_size > &p2) const
 
UInt< value_size > & operator-= (const UInt< value_size > &p2)
 
UInt< value_size > operator+ (const UInt< value_size > &p2) const
 
UInt< value_size > & operator+= (const UInt< value_size > &p2)
 
UInt< value_size > operator* (const UInt< value_size > &p2) const
 
UInt< value_size > & operator*= (const UInt< value_size > &p2)
 
UInt< value_size > operator/ (const UInt< value_size > &p2) const
 
UInt< value_size > & operator/= (const UInt< value_size > &p2)
 
UInt< value_size > operator% (const UInt< value_size > &p2) const
 
UInt< value_size > & operator%= (const UInt< value_size > &p2)
 
UInt< value_size > & operator++ ()
 
UInt< value_size > operator++ (int)
 
UInt< value_size > & operator-- ()
 
UInt< value_size > operator-- (int)
 
UInt< value_size > operator~ () const
 
UInt< value_size > operator& (const UInt< value_size > &p2) const
 
UInt< value_size > & operator&= (const UInt< value_size > &p2)
 
UInt< value_size > operator| (const UInt< value_size > &p2) const
 
UInt< value_size > & operator|= (const UInt< value_size > &p2)
 
UInt< value_size > operator^ (const UInt< value_size > &p2) const
 
UInt< value_size > & operator^= (const UInt< value_size > &p2)
 
UInt< value_size > operator>> (int move) const
 
UInt< value_size > & operator>>= (int move)
 
UInt< value_size > operator<< (int move) const
 
UInt< value_size > & operator<<= (int move)
 
uint Add (const UInt< value_size > &ss2, uint c=0)
 
uint AddInt (uint value, uint index=0)
 
uint AddTwoInts (uint x2, uint x1, uint index)
 
uint Sub (const UInt< value_size > &ss2, uint c=0)
 
uint SubInt (uint value, uint index=0)
 

Static Public Member Functions

template<class char_type , class ostream_type >
static void PrintVectorLog (const char_type *msg, ostream_type &output, const uint *vector, uint vector_len)
 
template<class char_type , class ostream_type >
static void PrintVectorLog (const char_type *msg, uint carry, ostream_type &output, const uint *vector, uint vector_len)
 
static uint AddTwoWords (uint a, uint b, uint carry, uint *result)
 
static uint SubTwoWords (uint a, uint b, uint carry, uint *result)
 
static const char * LibTypeStr ()
 
static LibTypeCode LibType ()
 
static uint AddVector (const uint *ss1, const uint *ss2, uint ss1_size, uint ss2_size, uint *result)
 
static uint SubVector (const uint *ss1, const uint *ss2, uint ss1_size, uint ss2_size, uint *result)
 
static sint FindLeadingBitInWord (uint x)
 
static sint FindLowestBitInWord (uint x)
 
static uint SetBitInWord (uint &value, uint bit)
 
static void MulTwoWords (uint a, uint b, uint *result_high, uint *result_low)
 
static void DivTwoWords (uint a, uint b, uint c, uint *r, uint *rest)
 

Public Attributes

uint table [value_size]
 

Protected Member Functions

double ToStringLog2 (uint x) const
 

Friends

std::ostream & operator<< (std::ostream &s, const UInt< value_size > &l)
 
std::wostream & operator<< (std::wostream &s, const UInt< value_size > &l)
 
std::istream & operator>> (std::istream &s, UInt< value_size > &l)
 
std::wistream & operator>> (std::wistream &s, UInt< value_size > &l)
 

Detailed Description

template<uint value_size>
class ttmath::UInt< value_size >

UInt implements a big integer value without a sign.

value_size - how many bytes specify our value on 32bit platforms: value_size=1 -> 4 bytes -> 32 bits on 64bit platforms: value_size=1 -> 8 bytes -> 64 bits value_size = 1,2,3,4,5,6....

Constructor & Destructor Documentation

template<uint value_size>
ttmath::UInt< value_size >::UInt ( uint  i)
inline

a constructor for converting the uint to this class

template<uint value_size>
ttmath::UInt< value_size >::UInt ( sint  i)
inline

a constructor for converting the sint to this class

look at the description of UInt::operator=(sint)

template<uint value_size>
ttmath::UInt< value_size >::UInt ( ulint  n)
inline

a constructor for converting unsigned 64 bit int to this class this constructor is created only on a 32bit platform***

template<uint value_size>
ttmath::UInt< value_size >::UInt ( slint  n)
inline

a constructor for converting signed 64 bit int to this class this constructor is created only on a 32bit platform***

template<uint value_size>
ttmath::UInt< value_size >::UInt ( const char *  s)
inline

a constructor for converting a string to this class (with the base=10)

template<uint value_size>
ttmath::UInt< value_size >::UInt ( const std::string &  s)
inline

a constructor for converting a string to this class (with the base=10)

template<uint value_size>
ttmath::UInt< value_size >::UInt ( const wchar_t *  s)
inline

a constructor for converting a string to this class (with the base=10)

template<uint value_size>
ttmath::UInt< value_size >::UInt ( const std::wstring &  s)
inline

a constructor for converting a string to this class (with the base=10)

template<uint value_size>
ttmath::UInt< value_size >::UInt ( )
inline

a default constructor

we don't clear the table

template<uint value_size>
ttmath::UInt< value_size >::UInt ( const UInt< value_size > &  u)
inline

a copy constructor

template<uint value_size>
template<uint argument_size>
ttmath::UInt< value_size >::UInt ( const UInt< argument_size > &  u)
inline

a template for producting constructors for copying from another types

template<uint value_size>
ttmath::UInt< value_size >::~UInt ( )
inline

a destructor

Member Function Documentation

template<uint value_size>
uint ttmath::UInt< value_size >::Add ( const UInt< value_size > &  ss2,
uint  c = 0 
)
template<uint value_size>
uint ttmath::UInt< value_size >::AddInt ( uint  value,
uint  index = 0 
)
template<uint value_size>
uint ttmath::UInt< value_size >::AddOne ( )
inline

basic mathematic functions

this method adds one to the existing value

template<uint value_size>
uint ttmath::UInt< value_size >::AddTwoInts ( uint  x2,
uint  x1,
uint  index 
)
template<uint value_size>
static uint ttmath::UInt< value_size >::AddTwoWords ( uint  a,
uint  b,
uint  carry,
uint result 
)
static
template<uint value_size>
static uint ttmath::UInt< value_size >::AddVector ( const uint ss1,
const uint ss2,
uint  ss1_size,
uint  ss2_size,
uint result 
)
static
template<uint value_size>
bool ttmath::UInt< value_size >::AreFirstBitsZero ( uint  bits) const
inline

returning true if first 'bits' bits are equal zero

template<uint value_size>
void ttmath::UInt< value_size >::BitAnd ( const UInt< value_size > &  ss2)
inline

this method performs a bitwise operation AND

template<uint value_size>
void ttmath::UInt< value_size >::BitNot ( )
inline

this method performs a bitwise operation NOT

template<uint value_size>
void ttmath::UInt< value_size >::BitNot2 ( )
inline

this method performs a bitwise operation NOT but only on the range of <0, leading_bit>

for example: BitNot2(8) = BitNot2( 1000(bin) ) = 111(bin) = 7

template<uint value_size>
void ttmath::UInt< value_size >::BitOr ( const UInt< value_size > &  ss2)
inline

this method performs a bitwise operation OR

template<uint value_size>
void ttmath::UInt< value_size >::BitXor ( const UInt< value_size > &  ss2)
inline

this method performs a bitwise operation XOR

template<uint value_size>
void ttmath::UInt< value_size >::ClearFirstBits ( uint  n)
inline

this method sets n first bits to value zero

For example: let n=2 then if there's a value 111 (bin) there'll be '100' (bin)

template<uint value_size>
bool ttmath::UInt< value_size >::CmpBigger ( const UInt< value_size > &  l,
sint  index = -1 
) const
inline

this method returns true if 'this' is bigger than 'l'

'index' is an index of the first word from will be the comparison performed (note: we start the comparison from back - from the last word, when index is -1 /default/ it is automatically set into the last word)

I introduced it for some kind of optimization made in the second division algorithm (Div2)

template<uint value_size>
bool ttmath::UInt< value_size >::CmpBiggerEqual ( const UInt< value_size > &  l,
sint  index = -1 
) const
inline

this method returns true if 'this' is bigger than or equal 'l'

'index' is an index of the first word from will be the comparison performed (note: we start the comparison from back - from the last word, when index is -1 /default/ it is automatically set into the last word)

template<uint value_size>
bool ttmath::UInt< value_size >::CmpEqual ( const UInt< value_size > &  l,
sint  index = -1 
) const
inline

this method returns true if 'this' is equal 'l'

'index' is an index of the first word from will be the comparison performed (note: we start the comparison from back - from the last word, when index is -1 /default/ it is automatically set into the last word)

template<uint value_size>
bool ttmath::UInt< value_size >::CmpSmaller ( const UInt< value_size > &  l,
sint  index = -1 
) const
inline

methods for comparing

this method returns true if 'this' is smaller than 'l'

'index' is an index of the first word from will be the comparison performed (note: we start the comparison from back - from the last word, when index is -1 /default/ it is automatically set into the last word) I introduced it for some kind of optimization made in the second division algorithm (Div2)

template<uint value_size>
bool ttmath::UInt< value_size >::CmpSmallerEqual ( const UInt< value_size > &  l,
sint  index = -1 
) const
inline

this method returns true if 'this' is smaller than or equal 'l'

'index' is an index of the first word from will be the comparison performed (note: we start the comparison from back - from the last word, when index is -1 /default/ it is automatically set into the last word)

template<uint value_size>
uint ttmath::UInt< value_size >::CompensationToLeft ( )
inline

this method moves all bits into the left side (it returns value how many bits have been moved)

template<uint value_size>
uint ttmath::UInt< value_size >::Div ( const UInt< value_size > &  divisor,
UInt< value_size > *  remainder = 0,
uint  algorithm = 3 
)
inline

division this = this / ss2

return values: 0 - ok 1 - division by zero 'this' will be the quotient 'remainder' - remainder

template<uint value_size>
uint ttmath::UInt< value_size >::Div ( const UInt< value_size > &  divisor,
UInt< value_size > &  remainder,
uint  algorithm = 3 
)
inline
template<uint value_size>
uint ttmath::UInt< value_size >::Div1 ( const UInt< value_size > &  divisor,
UInt< value_size > *  remainder = 0 
)
inline

the first division algorithm radix 2

template<uint value_size>
uint ttmath::UInt< value_size >::Div1 ( const UInt< value_size > &  divisor,
UInt< value_size > &  remainder 
)
inline

the first division algorithm radix 2

template<uint value_size>
uint ttmath::UInt< value_size >::Div2 ( const UInt< value_size > &  divisor,
UInt< value_size > *  remainder = 0 
)
inline

the second division algorithm

return values: 0 - ok 1 - division by zero

template<uint value_size>
uint ttmath::UInt< value_size >::Div2 ( const UInt< value_size > &  divisor,
UInt< value_size > &  remainder 
)
inline

the second division algorithm

return values: 0 - ok 1 - division by zero

template<uint value_size>
uint ttmath::UInt< value_size >::Div3 ( const UInt< value_size > &  ss2,
UInt< value_size > *  remainder = 0 
)
inline

the third division algorithm

template<uint value_size>
uint ttmath::UInt< value_size >::Div3 ( const UInt< value_size > &  ss2,
UInt< value_size > &  remainder 
)
inline

the third division algorithm

template<uint value_size>
uint ttmath::UInt< value_size >::DivInt ( uint  divisor,
uint remainder = 0 
)
inline

Division

division by one unsigned word

returns 1 when divisor is zero

template<uint value_size>
uint ttmath::UInt< value_size >::DivInt ( uint  divisor,
uint remainder 
)
inline
template<uint value_size>
static void ttmath::UInt< value_size >::DivTwoWords ( uint  a,
uint  b,
uint  c,
uint r,
uint rest 
)
static
template<uint value_size>
bool ttmath::UInt< value_size >::FindLeadingBit ( uint table_id,
uint index 
) const
inline

this method looks for the highest set bit

result: if 'this' is not zero: return value - true 'table_id' - the index of a word <0..value_size-1> 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)

if 'this' is zero: return value - false both 'table_id' and 'index' are zero

template<uint value_size>
static sint ttmath::UInt< value_size >::FindLeadingBitInWord ( uint  x)
static
template<uint value_size>
bool ttmath::UInt< value_size >::FindLowestBit ( uint table_id,
uint index 
) const
inline

this method looks for the smallest set bit

result: if 'this' is not zero: return value - true 'table_id' - the index of a word <0..value_size-1> 'index' - the index of this set bit in the word <0..TTMATH_BITS_PER_UINT)

if 'this' is zero: return value - false both 'table_id' and 'index' are zero

template<uint value_size>
static sint ttmath::UInt< value_size >::FindLowestBitInWord ( uint  x)
static
template<uint value_size>
template<uint argument_size>
uint ttmath::UInt< value_size >::FromInt ( const UInt< argument_size > &  p)
inline

this method converts an UInt<another_size> type to this class

this operation has mainly sense if the value from p is equal or smaller than that one which is returned from UInt<value_size>::SetMax()

it returns a carry if the value 'p' is too big

template<uint value_size>
uint ttmath::UInt< value_size >::FromInt ( uint  value)
inline

this method converts the uint type to this class

template<uint value_size>
uint ttmath::UInt< value_size >::FromInt ( sint  value)
inline

this method converts the sint type to this class

template<uint value_size>
uint ttmath::UInt< value_size >::FromInt ( ulint  n)
inline

this method converts unsigned 64 bit int type to this class this method is created only on a 32bit platform***

template<uint value_size>
uint ttmath::UInt< value_size >::FromInt ( slint  n)
inline

this method converts signed 64 bit int type to this class this method is created only on a 32bit platform***

template<uint value_size>
uint ttmath::UInt< value_size >::FromString ( const char *  s,
uint  b = 10,
const char **  after_source = 0,
bool *  value_read = 0 
)
inline

this method converts a string into its value it returns carry=1 if the value will be too big or an incorrect base 'b' is given

string is ended with a non-digit value, for example: "12" will be translated to 12 as well as: "12foo" will be translated to 12 too

existing first white characters will be ommited

if the value from s is too large the rest digits will be skipped

after_source (if exists) is pointing at the end of the parsed string

value_read (if exists) tells whether something has actually been read (at least one digit)

template<uint value_size>
uint ttmath::UInt< value_size >::FromString ( const std::string &  s,
uint  b = 10 
)
inline

this method converts a string into its value

(it returns carry=1 if the value will be too big or an incorrect base 'b' is given)

template<uint value_size>
uint ttmath::UInt< value_size >::FromString ( const wchar_t *  s,
uint  b = 10,
const wchar_t **  after_source = 0,
bool *  value_read = 0 
)
inline

this method converts a string into its value

template<uint value_size>
uint ttmath::UInt< value_size >::FromString ( const std::wstring &  s,
uint  b = 10 
)
inline

this method converts a string into its value

(it returns carry=1 if the value will be too big or an incorrect base 'b' is given)

template<uint value_size>
template<uint argument_size>
uint ttmath::UInt< value_size >::FromUInt ( const UInt< argument_size > &  p)
inline

conversion methods

this method converts an UInt<another_size> type to this class

this operation has mainly sense if the value from p is equal or smaller than that one which is returned from UInt<value_size>::SetMax()

it returns a carry if the value 'p' is too big

template<uint value_size>
uint ttmath::UInt< value_size >::FromUInt ( uint  value)
inline

this method converts the uint type to this class

template<uint value_size>
uint ttmath::UInt< value_size >::FromUInt ( ulint  n)
inline

this method converts unsigned 64 bit int type to this class this method is created only on a 32bit platform***

template<uint value_size>
uint ttmath::UInt< value_size >::GetBit ( uint  bit_index) const
inline

getting the 'bit_index' bit

bit_index bigger or equal zero

template<uint value_size>
bool ttmath::UInt< value_size >::IsOnlyTheHighestBitSet ( ) const
inline

returning true if only the highest bit is set

template<uint value_size>
bool ttmath::UInt< value_size >::IsOnlyTheLowestBitSet ( ) const
inline

returning true if only the lowest bit is set

template<uint value_size>
bool ttmath::UInt< value_size >::IsTheHighestBitSet ( ) const
inline

this method returns true if the highest bit of the value is set

template<uint value_size>
bool ttmath::UInt< value_size >::IsTheLowestBitSet ( ) const
inline

this method returns true if the lowest bit of the value is set

template<uint value_size>
bool ttmath::UInt< value_size >::IsZero ( ) const
inline

this method returns true if the value is equal zero

template<uint value_size>
static LibTypeCode ttmath::UInt< value_size >::LibType ( )
static
template<uint value_size>
static const char* ttmath::UInt< value_size >::LibTypeStr ( )
static
template<uint value_size>
uint ttmath::UInt< value_size >::Mul ( const UInt< value_size > &  ss2,
uint  algorithm = 100 
)
inline

the multiplication 'this' = 'this' * ss2

algorithm: 100 - means automatically choose the fastest algorithm

template<uint value_size>
uint ttmath::UInt< value_size >::Mul1 ( const UInt< value_size > &  ss2)
inline

multiplication: this = this * ss2 can return carry

template<uint value_size>
void ttmath::UInt< value_size >::Mul1Big ( const UInt< value_size > &  ss2_,
UInt< value_size *2 > &  result 
)
inline

multiplication: result = this * ss2

result is twice bigger than 'this' and 'ss2' this method never returns carry

template<uint value_size>
uint ttmath::UInt< value_size >::Mul2 ( const UInt< value_size > &  ss2)
inline

the second version of the multiplication algorithm

this algorithm is similar to the 'schoolbook method' which is done by hand

multiplication: this = this * ss2

it returns carry if it has been

template<uint value_size>
void ttmath::UInt< value_size >::Mul2Big ( const UInt< value_size > &  ss2,
UInt< value_size *2 > &  result 
)
inline

multiplication: result = this * ss2

result is twice bigger than this and ss2 this method never returns carry

template<uint value_size>
uint ttmath::UInt< value_size >::Mul3 ( const UInt< value_size > &  ss2)
inline

multiplication: this = this * ss2

This is Karatsuba Multiplication algorithm, we're using it when value_size is greater than or equal to TTMATH_USE_KARATSUBA_MULTIPLICATION_FROM_SIZE macro (defined in ttmathuint.h). If value_size is smaller then we're using Mul2Big() instead.

Karatsuba multiplication: Assume we have: this = x = x1*B^m + x0 ss2 = y = y1*B^m + y0 where x0 and y0 are less than B^m the product from multiplication we can show as: x*y = (x1*B^m + x0)(y1*B^m + y0) = z2*B^(2m) + z1*B^m + z0 where z2 = x1*y1 z1 = x1*y0 + x0*y1 z0 = x0*y0 this is standard schoolbook algorithm with O(n^2), Karatsuba observed that z1 can be given in other form: z1 = (x1 + x0)*(y1 + y0) - z2 - z0 / z1 = (x1*y1 + x1*y0 + x0*y1 + x0*y0) - x1*y1 - x0*y0 = x1*y0 + x0*y1 / and to calculate the multiplication we need only three multiplications (with some additions and subtractions)

Our objects 'this' and 'ss2' we divide into two parts and by using recurrence we calculate the multiplication. Karatsuba multiplication has O( n^(ln(3)/ln(2)) )

template<uint value_size>
void ttmath::UInt< value_size >::Mul3Big ( const UInt< value_size > &  ss2,
UInt< value_size *2 > &  result 
)
inline

multiplication: result = this * ss2

result is twice bigger than this and ss2, this method never returns carry, (Karatsuba multiplication)

template<uint value_size>
void ttmath::UInt< value_size >::MulBig ( const UInt< value_size > &  ss2,
UInt< value_size *2 > &  result,
uint  algorithm = 100 
)
inline

the multiplication 'result' = 'this' * ss2

since the 'result' is twice bigger than 'this' and 'ss2' this method never returns a carry

algorithm: 100 - means automatically choose the fastest algorithm

template<uint value_size>
uint ttmath::UInt< value_size >::MulFastest ( const UInt< value_size > &  ss2)
inline

multiplication this = this * ss2

template<uint value_size>
void ttmath::UInt< value_size >::MulFastestBig ( const UInt< value_size > &  ss2,
UInt< value_size *2 > &  result 
)
inline

multiplication result = this * ss2

this method is trying to select the fastest algorithm (in the future this method can be improved)

template<uint value_size>
uint ttmath::UInt< value_size >::MulInt ( uint  ss2)
inline

Multiplication

multiplication: this = this * ss2

it can return a carry

template<uint value_size>
template<uint result_size>
void ttmath::UInt< value_size >::MulInt ( uint  ss2,
UInt< result_size > &  result 
) const
inline

multiplication: result = this * ss2

we're using this method only when result_size is greater than value_size if so there will not be a carry

template<uint value_size>
static void ttmath::UInt< value_size >::MulTwoWords ( uint  a,
uint  b,
uint result_high,
uint result_low 
)
static
template<uint value_size>
bool ttmath::UInt< value_size >::operator!= ( const UInt< value_size > &  l) const
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator% ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator%= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator& ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator&= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator* ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator*= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator+ ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator++ ( )
inline

Prefix operator e.g ++variable

template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator++ ( int  )
inline

Postfix operator e.g variable++

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator+= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator- ( const UInt< value_size > &  p2) const
inline

standard mathematical operators

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator-- ( )
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator-- ( int  )
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator-= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator/ ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator/= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
bool ttmath::UInt< value_size >::operator< ( const UInt< value_size > &  l) const
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator<< ( int  move) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator<<= ( int  move)
inline
template<uint value_size>
bool ttmath::UInt< value_size >::operator<= ( const UInt< value_size > &  l) const
inline
template<uint value_size>
template<uint argument_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const UInt< argument_size > &  p)
inline

this operator converts an UInt<another_size> type to this class

it doesn't return a carry

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const UInt< value_size > &  p)
inline

the assignment operator

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( uint  i)
inline

this method converts the uint type to this class

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( sint  i)
inline

this method converts the sint type to this class

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( ulint  n)
inline

this operator converts unsigned 64 bit int type to this class this operator is created only on a 32bit platform***

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( slint  n)
inline

this operator converts signed 64 bit int type to this class this operator is created only on a 32bit platform***

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const char *  s)
inline

this operator converts a string into its value (with base = 10)

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const std::string &  s)
inline

this operator converts a string into its value (with base = 10)

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const wchar_t *  s)
inline

this operator converts a string into its value (with base = 10)

template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator= ( const std::wstring &  s)
inline

this operator converts a string into its value (with base = 10)

template<uint value_size>
bool ttmath::UInt< value_size >::operator== ( const UInt< value_size > &  l) const
inline
template<uint value_size>
bool ttmath::UInt< value_size >::operator> ( const UInt< value_size > &  l) const
inline
template<uint value_size>
bool ttmath::UInt< value_size >::operator>= ( const UInt< value_size > &  l) const
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator>> ( int  move) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator>>= ( int  move)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator^ ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator^= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator| ( const UInt< value_size > &  p2) const
inline
template<uint value_size>
UInt<value_size>& ttmath::UInt< value_size >::operator|= ( const UInt< value_size > &  p2)
inline
template<uint value_size>
UInt<value_size> ttmath::UInt< value_size >::operator~ ( ) const
inline

bitwise operators

template<uint value_size>
uint ttmath::UInt< value_size >::Pow ( UInt< value_size >  pow)
inline

power this = this ^ pow binary algorithm (r-to-l)

return values: 0 - ok 1 - carry 2 - incorrect argument (0^0)

template<uint value_size>
template<class char_type , class ostream_type >
void ttmath::UInt< value_size >::PrintLog ( const char_type *  msg,
ostream_type &  output 
) const
inline

this method is used when macro TTMATH_DEBUG_LOG is defined

template<uint value_size>
template<class char_type , class ostream_type >
void ttmath::UInt< value_size >::PrintLog ( const char_type *  msg,
uint  carry,
ostream_type &  output 
) const
inline

this method is used when macro TTMATH_DEBUG_LOG is defined

template<uint value_size>
template<class ostream_type >
void ttmath::UInt< value_size >::PrintTable ( ostream_type &  output) const
inline

some methods used for debugging purposes

this method is only for debugging purposes or when we want to make a table of a variable (constant) in ttmathbig.h

it prints the table in a nice form of several columns

template<uint value_size>
template<class char_type , class ostream_type >
static void ttmath::UInt< value_size >::PrintVectorLog ( const char_type *  msg,
ostream_type &  output,
const uint vector,
uint  vector_len 
)
inlinestatic

this method is used when macro TTMATH_DEBUG_LOG is defined

template<uint value_size>
template<class char_type , class ostream_type >
static void ttmath::UInt< value_size >::PrintVectorLog ( const char_type *  msg,
uint  carry,
ostream_type &  output,
const uint vector,
uint  vector_len 
)
inlinestatic

this method is used when macro TTMATH_DEBUG_LOG is defined

template<uint value_size>
uint ttmath::UInt< value_size >::Rcl ( uint  bits,
uint  c = 0 
)
inline

moving all bits into the left side 'bits' times return value <- this <- C

bits is from a range of <0, man * TTMATH_BITS_PER_UINT> or it can be even bigger then all bits will be set to 'c'

the value c will be set into the lowest bits and the method returns state of the last moved bit

template<uint value_size>
uint ttmath::UInt< value_size >::Rcr ( uint  bits,
uint  c = 0 
)
inline

moving all bits into the right side 'bits' times c -> this -> return value

bits is from a range of <0, man * TTMATH_BITS_PER_UINT> or it can be even bigger then all bits will be set to 'c'

the value c will be set into the highest bits and the method returns state of the last moved bit

template<uint value_size>
uint ttmath::UInt< value_size >::SetBit ( uint  bit_index)
inline

setting the 'bit_index' bit and returning the last state of the bit

bit_index bigger or equal zero

template<uint value_size>
static uint ttmath::UInt< value_size >::SetBitInWord ( uint value,
uint  bit 
)
static
template<uint value_size>
void ttmath::UInt< value_size >::SetFromTable ( const uint temp_table,
uint  temp_table_len 
)
inline

this method copies the value stored in an another table (warning: first values in temp_table are the highest words – it's different from our table)

we copy as many words as it is possible

if temp_table_len is bigger than value_size we'll try to round the lowest word from table depending on the last not used bit in temp_table (this rounding isn't a perfect rounding – look at the description below)

and if temp_table_len is smaller than value_size we'll clear the rest words in the table

template<uint value_size>
void ttmath::UInt< value_size >::SetMax ( )
inline

this method sets the max value which this class can hold (all bits will be one)

template<uint value_size>
void ttmath::UInt< value_size >::SetMin ( )
inline

this method sets the min value which this class can hold (for an unsigned integer value the zero is the smallest value)

template<uint value_size>
void ttmath::UInt< value_size >::SetOne ( )
inline

this method sets one

template<uint value_size>
void ttmath::UInt< value_size >::SetZero ( )
inline

this method sets zero

template<uint value_size>
uint ttmath::UInt< value_size >::Size ( ) const
inline

this method returns the size of the table

template<uint value_size>
void ttmath::UInt< value_size >::Sqrt ( )
inline

square root e.g. Sqrt(9) = 3 ('digit-by-digit' algorithm)

template<uint value_size>
uint ttmath::UInt< value_size >::Sub ( const UInt< value_size > &  ss2,
uint  c = 0 
)
template<uint value_size>
uint ttmath::UInt< value_size >::SubInt ( uint  value,
uint  index = 0 
)
template<uint value_size>
uint ttmath::UInt< value_size >::SubOne ( )
inline

this method subtracts one from the existing value

template<uint value_size>
static uint ttmath::UInt< value_size >::SubTwoWords ( uint  a,
uint  b,
uint  carry,
uint result 
)
static
template<uint value_size>
static uint ttmath::UInt< value_size >::SubVector ( const uint ss1,
const uint ss2,
uint  ss1_size,
uint  ss2_size,
uint result 
)
static
template<uint value_size>
void ttmath::UInt< value_size >::Swap ( UInt< value_size > &  ss2)
inline

this method swappes this for an argument

template<uint value_size>
uint ttmath::UInt< value_size >::ToInt ( uint result) const
inline

this method converts the value to uint type can return a carry if the value is too long to store it in uint type

template<uint value_size>
uint ttmath::UInt< value_size >::ToInt ( sint result) const
inline

this method converts the value to sint type (signed integer) can return a carry if the value is too long to store it in sint type

template<uint value_size>
uint ttmath::UInt< value_size >::ToInt ( ulint result) const
inline

this method converts the value to ulint type (64 bit unsigned integer) can return a carry if the value is too long to store it in ulint type this method is created only on a 32 bit platform ***

template<uint value_size>
uint ttmath::UInt< value_size >::ToInt ( slint result) const
inline

this method converts the value to slint type (64 bit signed integer) can return a carry if the value is too long to store it in slint type this method is created only on a 32 bit platform ***

template<uint value_size>
void ttmath::UInt< value_size >::ToString ( std::string &  result,
uint  b = 10 
) const
inline

this method converts the value to a string with a base equal 'b'

template<uint value_size>
std::string ttmath::UInt< value_size >::ToString ( uint  b = 10) const
inline
template<uint value_size>
void ttmath::UInt< value_size >::ToString ( std::wstring &  result,
uint  b = 10 
) const
inline
template<uint value_size>
template<class string_type >
void ttmath::UInt< value_size >::ToStringBase ( string_type &  result,
uint  b = 10,
bool  negative = false 
) const
inline

an auxiliary method for converting to a string it's used from Int::ToString() too (negative is set true then)

template<uint value_size>
double ttmath::UInt< value_size >::ToStringLog2 ( uint  x) const
inlineprotected

an auxiliary method for converting into the string it returns the log (with the base 2) from x where x is in <2;16>

template<uint value_size>
uint ttmath::UInt< value_size >::ToUInt ( ) const
inline

this method returns the lowest value from table

we must be sure when we using this method whether the value will hold in an uint type or not (the rest value from the table must be zero)

template<uint value_size>
uint ttmath::UInt< value_size >::ToUInt ( uint result) const
inline

this method converts the value to uint type can return a carry if the value is too long to store it in uint type

template<uint value_size>
uint ttmath::UInt< value_size >::ToUInt ( ulint result) const
inline

this method converts the value to ulint type (64 bit unsigned integer) can return a carry if the value is too long to store it in ulint type this method is created only on a 32 bit platform ***

template<uint value_size>
std::wstring ttmath::UInt< value_size >::ToWString ( uint  b = 10) const
inline

Friends And Related Function Documentation

template<uint value_size>
std::ostream& operator<< ( std::ostream &  s,
const UInt< value_size > &  l 
)
friend

output to standard streams

template<uint value_size>
std::wostream& operator<< ( std::wostream &  s,
const UInt< value_size > &  l 
)
friend

output to standard streams

template<uint value_size>
std::istream& operator>> ( std::istream &  s,
UInt< value_size > &  l 
)
friend

input from standard streams

template<uint value_size>
std::wistream& operator>> ( std::wistream &  s,
UInt< value_size > &  l 
)
friend

input from standard streams

Member Data Documentation

template<uint value_size>
uint ttmath::UInt< value_size >::table[value_size]

buffer for the integer value table[0] - the lowest word of the value


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