y-cruncher Multi-Precision Library
	A Multi-threaded Multi-Precision Arithmetic Library (Powered by y-cruncher)

(Last updated: March 3, 2016)

 

BigInt - Large Integer

 

BigInt is a large floating-point object:

• It can represent arbitrarily large integers limited only by memory address space.
• It supports both positive and negative numbers. It also supports zero.
• It supports fast algorithms and parallelism for large multiplication and dependent operations. Multiplication runs in approximately O(N log(N)) time.

 

Types:

 

BigInt is an abstract base class for BigIntR and BigIntO. So it cannot be used directly.

• BigIntO is a standard RAII object that is easy to use but has a lot of overhead.
• BigIntR is a low-level object that is difficult to use and has little overhead.

These subclasses differ in only their resource ownership policies. But otherwise, they have nearly identical functionality.

 

 

Representation:

 

The current representation of the BigInt object is as follows:

BigInt = sign * ( A[0] + A[1]*base¹ + A[2]*base² + A[3]*base³ + ... )

with the following relevant fields:

• T - The pointer to the start of the array.
• L - The length of the array.
• sign - The sign.

 

Function List:

• Headers: Objects/GenericInt/GenericInt.h
• Sources: none
• Namespace: ymp

 

Being the abstract base class, there isn't much functionality here.

 

Const Getters:

• get_T()
• get_L()
• get_sign()
• get_buffersize()
• is_zero()
• operator[]
• get_range()
• operator<(), operator>()
• operator<=(), operator>=()
• operator==()
• cmp()
• iPsize()

 

Getters:

 

Get Array Pointer:

const u32_t* BigInt<u32_t>::get_T () const;

const u64_t* BigInt<u64_t>::get_T () const;

 

Returns a pointer to the start of the internal array.

Get Length:

upL_t BigInt<u32_t>::get_L () const;

upL_t BigInt<u64_t>::get_L () const;

 

Return the logical length of the array. (the mantissa)

Get Sign:

int BigInt<u32_t>::get_sign () const;

int BigInt<u64_t>::get_sign () const;

 

Returns:

• 1 if the object is positive.
• 0 if the object is zero.
• -1 if the object is negative.

Get Buffer Size:

upL_t BigInt<u32_t>::get_buffersize () const;

upL_t BigInt<u64_t>::get_buffersize () const;

 

Returns the size of the internal buffer. This gives the largest number (in words) that can be stored in the object.

 

---

Is Zero:

bool BigInt<u32_t>::is_zero () const;

bool BigInt<u64_t>::is_zero () const;

Description:

Returns true if the current object is zero.

 

---

Operator[]:

u32_t BigInt<u32_t>::operator[] (siL_t mag) const;

u64_t BigInt<u64_t>::operator[] (siL_t mag) const;

Description:

Returns the word at the specified magnitude.

 

Mathematically:

(return value) = Floor( Abs(this) / base^mag ) mod base

 

---

Get Range:

void BigInt<u32_t>::get_range (u32_t* buffer, siL_t s, upL_t L) const;

void BigInt<u64_t>::get_range (u64_t* buffer, siL_t s, upL_t L) const;

Description:

Get the words in the range [s, s + L) and write them to buffer. This is a multi-word version of operator[].

 

Mathematically:

{buffer, L} = Floor( Abs(this) / base^s ) mod base^L

 

---

Compare:

bool operator< (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

bool operator< (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

 

bool operator> (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

bool operator> (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

 

bool operator<= (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

bool operator<= (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

 

bool operator>= (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

bool operator>= (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

 

bool operator== (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

bool operator== (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

 

int BigInt<u32_t>::cmp (const BigInt<u32_t>& B) const;

int BigInt<u64_t>::cmp (const BigInt<u64_t>& B) const;

Description:

Standard comparison operators.

 

cmp() returns:

• 1 if this > B
• 0 if this == B
• -1 if this < B

 

---

Incremental Scratch Buffer Size:

static uiL_t BigInt<u32_t>::iPsize_clen (uiL_t clen, upL_t tds = 1);

static uiL_t BigInt<u64_t>::iPsize_clen (uiL_t clen, upL_t tds = 1);

Description:

Similar to mul_iPsize().

 

Returns the size of the scratch buffer needed to call any large multiplication on a BigInt object with a product of at most clen words and using a task decomposition of at most tds.

 

This is mainly used for populating the BasicParameters object.