y-cruncher Multi-Precision Library

A Multi-threaded Multi-Precision Arithmetic Library

(Powered by y-cruncher)

(Last updated: March 7, 2016)

Shortcuts:

Numberworld Home

YMP Library:

Large Number Objects:

Low-Level Programming:

BigFloatO - Large Floating-Point (with RAII)

BigFloatO is an ownership subclass of BigFloat.

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 BigFloatO class. Users wishing to bypass even these memory allocations will be required to use BigFloatR instead.

Function List:

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

Inherited from BigFloat:

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

Constructors:

BigFloatO()
BigFloatO(u32_t x)
BigFloatO(s32_t x)
BigFloatO(uiL_t x)
BigFloatO(siL_t x)
BigFloatO(const BasicInt<wtype>& x)
BigFloatO(const ExactFloat<wtype>& x)
BigFloatO(const BigFloat<wtype>& x)

Basic Arithmetic:

negate()
strip_tzs_all()
operator<<()
operator*=()
add(), set_add()
sub(), set_sub()

Large Multiplication:

sqr(), set_sqr()
mul(), set_mul()

Functions Library:

to_string_hex()
to_string_dec()
rcp()
div()
invsqrt_uW()
pow_sL()

Constructors:

Default:

BigFloatO<u32_t>::BigFloatO ();

BigFloatO<u64_t>::BigFloatO ();

Construct a new object with the value of zero.

Small Integer:

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

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

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

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

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

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

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

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

Construct a new object with a value of x.

Bignum Object:

BigFloatO<u32_t>::BigFloatO (const BasicInt<u32_t>& x);

BigFloatO<u64_t>::BigFloatO (const BasicInt<u64_t>& x);

BigFloatO<u32_t>::BigFloatO (const ExactFloat<u32_t>& x);

BigFloatO<u64_t>::BigFloatO (const ExactFloat<u64_t>& x);

BigFloatO<u32_t>::BigFloatO (const BigFloat<u32_t>& x);

BigFloatO<u64_t>::BigFloatO (const BigFloat<u64_t>& x);

Construct a new object with a value of x. These constructors perform a copy of the value from x into the new object.

Basic Arithmetic:

Negate:

void BigFloatO<u32_t>::negate ();

void BigFloatO<u64_t>::negate ();

Description:

Negates this object.

Performance:

Time Complexity: O(1)

Strip Trailing Zeros:

void BigFloatO<u32_t>::strip_tzs_all ();

void BigFloatO<u64_t>::strip_tzs_all ();

Description:

Remove all trailing zeros from the representation of the current object.

While this has no effect on the numerical value of the current object, shortening the internal size may speed up subsequent operations on it.

Performance:

Time Complexity (best): O(1)
Time Complexity (worst): O(N)

Multiply by Power-of-Two:

void BigFloatO<u32_t>::operator<<= (siL_t pow);

void BigFloatO<u64_t>::operator<<= (siL_t pow);

Description:

Multiplies this object by 2^pow. Negative pow implies by division power-of-two.

This operation is done without loss of any precision.

Performance:

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

Single-Word Multiply:

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

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

Description:

Multiplies this object by x.

This operation is done without loss of any precision.

Performance:

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

Addition/Subtraction:

BigFloatO<u32_t> add (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

BigFloatO<u64_t> add (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

BigFloatO<u32_t> sub (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

BigFloatO<u64_t> sub (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

void BigFloatO<u32_t>::set_add (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

void BigFloatO<u64_t>::set_add (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

void BigFloatO<u32_t>::set_sub (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

void BigFloatO<u64_t>::set_sub (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

Description:

Computes A + B or A - B.

The result will have an error no more than base^-p relative to the larger input (in magnitude).

The rounding behavior is not defined. Though the current implementation truncates towards zero.

Variants:

add() and sub() will return the result.
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:

BigFloatO<u32_t> sqr (const BigFloat<u32_t>& A, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> sqr (const BigFloat<u64_t>& A, upL_t p, upL_t tds = 1);

BigFloatO<u32_t> mul (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> mul (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p, upL_t tds = 1);

void BigFloatO<u32_t>::set_sqr (const BigFloat<u32_t>& A, upL_t p, upL_t tds = 1);

void BigFloatO<u64_t>::set_sqr (const BigFloat<u64_t>& A, upL_t p, upL_t tds = 1);

void BigFloatO<u32_t>::set_mul (const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p, upL_t tds = 1);

void BigFloatO<u64_t>::set_mul (const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p, upL_t tds = 1);

Large Multiplication - Parameter Controlled:

BigFloatO<u32_t> sqr (const BasicParameters& mp, const BigFloat<u32_t>& A, upL_t p);

BigFloatO<u64_t> sqr (const BasicParameters& mp, const BigFloat<u64_t>& A, upL_t p);

BigFloatO<u32_t> mul (const BasicParameters& mp, const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

BigFloatO<u64_t> mul (const BasicParameters& mp, const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

void BigFloatO<u32_t>::set_sqr (const BasicParameters& mp, const BigFloat<u32_t>& A, upL_t p);

void BigFloatO<u64_t>::set_sqr (const BasicParameters& mp, const BigFloat<u64_t>& A, upL_t p);

void BigFloatO<u32_t>::set_mul (const BasicParameters& mp, const BigFloat<u32_t>& A, const BigFloat<u32_t>& B, upL_t p);

void BigFloatO<u64_t>::set_mul (const BasicParameters& mp, const BigFloat<u64_t>& A, const BigFloat<u64_t>& B, upL_t p);

Description:

Computes A² or A * B.

The result will have an error no more than base^-p relative to a correct result (as if it were done using infinite precision).

The rounding behavior is not defined.

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.
set_sqr() and set_mul() will replace the contents of the current object - reallocating if necessary.

Performance:

Time Complexity: O( p * log(p) )
Scratch Memory: O(p) 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.

Most functions here are thin wrappers over native implementations in y-cruncher. So they have access to optimizations that are only possible via the internal interface.

Object to Hexadecimal String:

std::string to_string_hex (const BigFloat<u32_t>& x, upL_t digits);

std::string to_string_hex (const BigFloat<u64_t>& x, upL_t digits);

Description:

Converts x to a string representation in base 16 with at most digits significant digits.

The rounding behavior is unspecified. But the current implementation truncates towards zero.

The function will auto-select between floating and scientific notation.

Performance:

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

Object to Decimal String:

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

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

Description:

Converts x to a string representation in base 10 with at most digits significant digits.

The rounding behavior is unspecified. But the current implementation usually truncates towards zero.

The function will auto-select between floating and scientific notation.

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( digits * log(digits)² )
Scratch Memory: O(digits)

Reciprocal and Division - Basic:

BigFloatO<u32_t> rcp (const BigFloat<u32_t>& A, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> rcp (const BigFloat<u64_t>& A, upL_t p, upL_t tds = 1);

BigFloatO<u32_t> div (const BigFloat<u32_t>& N, const BigFloat<u32_t>& D, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> div (const BigFloat<u64_t>& N, const BigFloat<u64_t>& D, upL_t p, upL_t tds = 1);

Reciprocal and Division - Parameter Controlled:

void rcp (const BasicParameters& mp, BigFloatO<u32_t>& T, const BigFloat<u32_t>& A, upL_t p);

void rcp (const BasicParameters& mp, BigFloatO<u32_t>& T, const BigFloat<u64_t>& A, upL_t p);

void rcp_sizes<u32_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

void rcp_sizes<u64_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

void div (const BasicParameters& mp, BigFloatO<u32_t>& T, const BigFloat<u32_t>& N, const BigFloat<u32_t>& D, upL_t p);

void div (const BasicParameters& mp, BigFloatO<u32_t>& T, const BigFloat<u64_t>& N, const BigFloat<u64_t>& D, upL_t p);

void div_sizes<u32_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

void div_sizes<u64_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

Description:

Computes 1/A or N/D and returns the result. Division by zero will throw an exception.

The result will have an error no more than base^-p relative to a correct result (as if it were done using infinite precision).

The rounding behavior is not defined.

The minimum size of {mp.M, mp.ML} can be obtained by calling rcp_sizes() and div_sizes() respectively. While these sizing functions are intended for the BigFloatR class, they are applicable here as well.

Parameters:

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

Performance:

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

BasicParameter (mp) Required Fields:

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

Inverse Square Root (Single Word) - Basic:

BigFloatO<u32_t> invsqrt_uW (u32_t x, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> invsqrt_uW (u64_t x, upL_t p, upL_t tds = 1);

Inverse Square Root (Single Word) - Parameter Controlled:

void invsqrt_uW (const BasicParameters& mp, BigFloatR<u32_t>& T, u32_t x, upL_t p);

void invsqrt_uW (const BasicParameters& mp, BigFloatR<u64_t>& T, u64_t x, upL_t p);

void invsqrt_uW_sizes<u32_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

void invsqrt_uW_sizes<u64_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

Description:

Computes 1 / sqrt(x) and returns the result. Division by zero will throw an exception.

The result will have an error no more than base^-p relative to a correct result (as if it were done using infinite precision).

The rounding behavior is not defined.

The minimum size of {mp.M, mp.ML} can be obtained by calling invsqrt_uW_sizes(). While this sizing function is intended for the BigFloatR class, it is applicable here as well.

Parameters:

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

Performance:

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

BasicParameter (mp) Required Fields:

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

Square Root - Basic:

BigFloatO<u32_t> invsqrt (const BigFloat<u32_t>& x, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> invsqrt (const BigFloat<u64_t>& x, upL_t p, upL_t tds = 1);

BigFloatO<u32_t> sqrt (const BigFloat<u32_t>& x, upL_t p, upL_t tds = 1);

BigFloatO<u64_t> sqrt (const BigFloat<u64_t>& x, upL_t p, upL_t tds = 1);

Description:

Computes 1 / sqrt(x) or sqrt(x) and returns the result. Division by zero will throw an exception.

The result will have an error no more than base^-p relative to a correct result (as if it were done using infinite precision).

The rounding behavior is not defined.

There are currently no BigFloatR or parameter controlled versions of these functions.

Parameters:

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

Performance:

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

Power Function (Integer Power) - Basic:

void pow_sL (BigFloatR<u32_t>& T, u32_t x, siL_t pow, upL_t p, upL_t tds = 1);

void pow_sL (BigFloatR<u64_t>& T, u64_t x, siL_t pow, upL_t p, upL_t tds = 1);

Power Function (Integer Power) - Parameter Controlled:

void pow_sL (const BasicParameters& mp, BigFloatR<u32_t>& T, u32_t x, siL_t pow, upL_t p);

void pow_sL (const BasicParameters& mp, BigFloatR<u64_t>& T, u64_t x, siL_t pow, upL_t p);

void pow_sL_sizes<u32_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

void pow_sL_sizes<u64_t> (uiL_t& Tsize, uiL_t& Psize, uiL_t& Msize, uiL_t p, upL_t tds);

Description:

Computes x^pow. The result is stored into T overwriting it. Division by zero will throw an exception. 0⁰ is undefined.

The result will have an error no more than base^-p relative to a correct result (as if it were done using infinite precision).

The rounding behavior is not defined.

The minimum size of {mp.M, mp.ML} can be obtained by calling pow_sL_sizes(). While this sizing function is intended for the BigFloatR class, it is applicable here as well.

Currently, there is only support for integer^integer. This will likely be extended to BigFloat^integer in a later version.

Support for BigFloat^BigFloatwill be more difficult as that requires exp() which requires log() which requires AGM() which requires sqrt(). And none of these are currently supported.

Parameters:

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

Performance:

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

BasicParameter (mp) Required Fields:

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

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)