y-cruncher Multi-Precision Library

A Multi-threaded Multi-Precision Arithmetic Library

(Powered by y-cruncher)

(Last updated: March 3, 2016)

Shortcuts:

Numberworld Home

YMP Library:

Large Number Objects:

Low-Level Programming:

BigIntO - Large Integer (with RAII)

BigIntO is an ownership subclass of BigInt.

Ownership subclasses are standard RAII objects that can be copied and moved. While they are easy to use, they also have tremendous overhead from memory allocation and page-commit. If utmost maximum performance is desired, consider using the raw classes intstead.

Ownership classes are designed for scripting and research. They are not used in y-cruncher. Most functions for ownership classes are implemented as wrappers over their counterparts from the raw classes.

More on "ownership" classes.

Most functions that require large multiplication have two versions: One with and one without the mp parameter that allows control over the "hidden parameters" required for large multiplication.

Some functions require more scratch buffers in addition to the one in the mp parameter. These extra scratch buffers are allocated automatically and currently cannot be controlled with the BigIntO class. Users wishing to bypass even these memory allocations will be required to use BigIntR instead.

Function List:

Headers: ymp/BigIntO.h
Sources: none
Namespace: ymp

Inherited from BigInt:

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

Constructors:

BigIntO()
BigIntO(u32_t x)
BigIntO(s32_t x)
BigIntO(uiL_t x)
BigIntO(siL_t x)

Basic Arithmetic:

negate()
operator<<()
operator>>()
operator*=()
operator+(), operator+=(), add(), set_add()
operator-(), operator-=(), sub(), set_sub()

Large Multiplication:

sqr(), set_sqr()
operator*(), operator*=(), mul(), set_mul()

Functions Library:

to_string_hex()
to_string_dec()
div()
mod()
divmod()

Constructors:

Default:

BigIntO<u32_t>::BigIntO ();

BigIntO<u64_t>::BigIntO ();

Construct a new object with the value of zero.

Small Integer:

BigIntO<u32_t>::BigIntO (u32_t x);

BigIntO<u64_t>::BigIntO (u32_t x);

BigIntO<u32_t>::BigIntO (s32_t x);

BigIntO<u64_t>::BigIntO (s32_t x);

BigIntO<u32_t>::BigIntO (uiL_t x);

BigIntO<u64_t>::BigIntO (uiL_t x);

BigIntO<u32_t>::BigIntO (siL_t x);

BigIntO<u64_t>::BigIntO (siL_t x);

Construct a new object with a value of x.

Truncate from BigFloat:

explicit BigIntO<u32_t>::BigIntO (const BigFloat<u32_t>& x);

explicit BigIntO<u64_t>::BigIntO (const BigFloat<u64_t>& x);

Construct a new object from BigFloat x. The value is truncated to an integer towards zero.

Basic Arithmetic:

Negate:

void BigIntO<u32_t>::negate ();

void BigIntO<u64_t>::negate ();

Description:

Negates this object.

Performance:

Time Complexity: O(1)

Multiply by Power-of-Two:

void BigIntO<u32_t>::operator<<= (upL_t bits);

void BigIntO<u64_t>::operator<<= (upL_t bits);

Description:

Multiplies this object by 2^bits.

Performance:

Time Complexity (best): O(1)
Time Complexity (average/worst): O(N)
Scratch Memory: O(N)

Divide by Power-of-Two:

void BigIntO<u32_t>::operator>>= (upL_t bits);

void BigIntO<u64_t>::operator>>= (upL_t bits);

Description:

Divides this object by 2^bits rounding towards zero.

Performance:

Time Complexity (best): O(1)
Time Complexity (average/worst): O(N)
Scratch Memory: O(N)

Single-Word Multiply:

void BigIntO<u32_t>::operator*= (u32_t x);

void BigIntO<u64_t>::operator*= (u64_t x);

Description:

Multiplies this object by x.

Performance:

Time Complexity: O(N)
Scratch Memory: O(N)

Addition/Subtraction:

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

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

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

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

void BigIntO<u32_t>::operator+= (const BigInt<u32_t>& B);

void BigIntO<u64_t>::operator+= (const BigInt<u64_t>& B);

void BigIntO<u32_t>::operator-= (const BigInt<u32_t>& B);

void BigIntO<u64_t>::operator-= (const BigInt<u64_t>& B);

void BigIntO<u32_t>::set_add (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

void BigIntO<u64_t>::set_add (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

void BigIntO<u32_t>::set_sub (const BigInt<u32_t>& A, const BigInt<u32_t>& B);

void BigIntO<u64_t>::set_sub (const BigInt<u64_t>& A, const BigInt<u64_t>& B);

Description:

Computes A + B or A - B.

Variants:

set_add() and set_sub() will replace the contents of the current object - reallocating if necessary.

Performance:

Time Complexity: O(p)
Scratch Memory: none

Large Multiplication:

Large Multiplication - Basic:

BigIntO<u32_t> sqr (const BigInt<u32_t>& A, upL_t tds = 1);

BigIntO<u64_t> sqr (const BigInt<u64_t>& A, upL_t tds = 1);

BigIntO<u32_t> mul (const BigInt<u32_t>& A, const BigInt<u32_t>& B, upL_t tds = 1);

BigIntO<u64_t> mul (const BigInt<u64_t>& A, const BigInt<u64_t>& B, upL_t tds = 1);

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

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

void BigIntO<u32_t>::operator*= (const BigInt<u32_t>& B);

void BigIntO<u64_t>::operator*= (const BigInt<u64_t>& B);

void BigIntO<u32_t>::set_sqr (const BigInt<u32_t>& A, upL_t tds = 1);

void BigIntO<u64_t>::set_sqr (const BigInt<u64_t>& A, upL_t tds = 1);

void BigIntO<u32_t>::set_mul (const BigInt<u32_t>& A, const BigInt<u32_t>& B, upL_t tds = 1);

void BigIntO<u64_t>::set_mul (const BigInt<u64_t>& A, const BigInt<u64_t>& B, upL_t tds = 1);

Large Multiplication - Parameter Controlled:

void BigIntO<u32_t>::set_sqr (const BasicParameters& mp, const BigInt<u32_t>& A);

void BigIntO<u64_t>::set_sqr (const BasicParameters& mp, const BigInt<u64_t>& A);

void BigIntO<u32_t>::set_mul (const BasicParameters& mp, const BigInt<u32_t>& A, const BigInt<u32_t>& B);

void BigIntO<u64_t>::set_mul (const BasicParameters& mp, const BigInt<u64_t>& A, const BigInt<u64_t>& B);

Description:

Computes A² or A * B.

The operator overloading functions use tds = 1 (no parallelism).

Parameters:

tds - Specifies the desired level of task decomposition for the purpose of parallelism.
mp - The low-level multiplication parameters struct.

Variants:

sqr() and mul() will return the result.
operator*() and operator*=() will use a task decomposition of 1. (no parallelism)
set_sqr() and set_mul() will replace the contents of the current object - reallocating if necessary.

Performance:

Time Complexity: O( N * log(N) )
Scratch Memory: O(N) for the basic functions. None for the parameter controlled functions.

BasicParameter (mp) Required Fields:

mp.tw
mp.M
mp.ML
mp.tds

Functions Library:

Addition, subtraction, and multiplication are the only operations that are supported by the class itself. Everything else is implemented separately in a functions library.

Object to Hexadecimal String:

std::string to_string_hex (const BigInt<u32_t>& x);

std::string to_string_hex (const BigInt<u64_t>& x);

Description:

Converts x to a string representation in base 16.

Performance:

Time Complexity: O(N)
Scratch Memory: O(N)

Object to Decimal String:

std::string to_string_dec (const BigInt<u32_t>& x, upL_t tds = 1);

std::string to_string_dec (const BigInt<u64_t>& x, upL_t tds = 1);

Description:

Converts x to a string representation in base 10.

Note that the current implementation of this function suffers heavily from Amdahl's Law - the serial part being the string formatting and the final conversion to std::string.

Parameters:

tds - Specifies the desired level of task decomposition for the purpose of parallelism.

Performance:

Time Complexity: O( N * log(N)² )
Scratch Memory: O(N)

Division:

BigIntO<u32_t> div (const BigInt<u32_t>& A, const BigInt<u32_t>& B, upL_t tds = 1);

BigIntO<u64_t> div (const BigInt<u64_t>& A, const BigInt<u64_t>& B, upL_t tds = 1);

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

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

Description:

Computes floor(A / B).

The operator overloading functions use tds = 1 (no parallelism).

Parameters:

tds - Specifies the desired level of task decomposition for the purpose of parallelism.

Performance:

Time Complexity: O( N * log(N) )
Scratch Memory: O(N)

Modulus:

BigIntO<u32_t> mod (const BigInt<u32_t>& A, const BigInt<u32_t>& B, upL_t tds = 1);

BigIntO<u64_t> mod (const BigInt<u64_t>& A, const BigInt<u64_t>& B, upL_t tds = 1);

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

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

Description:

Computes A - B * floor(A / B).

The operator overloading functions use tds = 1 (no parallelism).

Parameters:

tds - Specifies the desired level of task decomposition for the purpose of parallelism.

Performance:

Time Complexity: O( N * log(N) )
Scratch Memory: O(N)

Divide and Modulus:

void divmod (BigIntO<u32_t>& Q, BigIntO<u32_t>& R, const BigInt<u32_t>& A, const BigInt<u32_t>& B, upL_t tds = 1);

void divmod (BigIntO<u64_t>& Q, BigIntO<u64_t>& R, const BigInt<u64_t>& A, const BigInt<u64_t>& B, upL_t tds = 1);

Description:

Computes:

Q = floor(A / B)

R = A - B * floor(A / B)

This function is more efficient than calling div() and mod() separately.

Parameters:

tds - Specifies the desired level of task decomposition for the purpose of parallelism.

Performance:

Time Complexity: O( N * log(N) )
Scratch Memory: O(N)

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

y-cruncher Multi-Precision Library

A Multi-threaded Multi-Precision Arithmetic Library

(Powered by y-cruncher)

y-cruncher Multi-Precision Library

A Multi-threaded Multi-Precision Arithmetic Library

(Powered by y-cruncher)