tango.math.internal.BiguintCore

Fundamental operations for arbitrary-precision arithmetic
These functions are for internal use only.

License:

BSD style: see license.txt

Authors:

Don Clugston
struct BigUint [public] #
BigUint performs memory management and wraps the low-level calls.
void opAssign(ulong u) [public] #
int opCmp(BigUint y) [public] #
int opCmp(ulong y) [public] #
char [] toHexString(int frontExtraBytes, char separator = 0, int minPadding = 0, char padChar = '0') [public] #
Convert to a hex string, printing a minimum number of digits 'minPadding', allocating an additional 'frontExtraBytes' at the start of the string. Padding is done with padChar, which may be '0' or ' '. 'separator' is a digit separation character. If non-zero, it is inserted between every 8 digits. Separator characters do not contribute to the minPadding.
BigUint opShr(ulong y) [public] #
BigUint pow(BigUint x, ulong y) [public, static] #
Return a BigUint which is x raised to the power of y.

Method:

Powers of 2 are removed from x, then left-to-right binary exponentiation is used. Memory allocation is minimized: at most one temporary BigUint is used.
BigDigit [] addInt(BigDigit[] x, ulong y) [private] #
return x + y
BigDigit [] subInt(BigDigit[] x, ulong y) [private] #
Return x - y. x must be greater than y.
void mulInternal(BigDigit[] result, BigDigit[] x, BigDigit[] y) [private] #
General unsigned multiply routine for bigints. Sets result = x * y.
The length of y must not be larger than the length of x. Different algorithms are used, depending on the lengths of x and y.

TODO:

"Modern Computer Arithmetic" suggests the OddEvenKaratsuba algorithm for the unbalanced case. (But I doubt it would be faster in practice).
void squareInternal(BigDigit[] result, BigDigit[] x) [private] #
General unsigned squaring routine for BigInts. Sets result = x*x.

NOTE:

If the highest half-digit of x is zero, the highest digit of result will also be zero.
void divModInternal(BigDigit [] quotient, BigDigit[] remainder, BigDigit [] u, BigDigit [] v) [private] #
if remainder is null, only calculate quotient.
int biguintToDecimal(char [] buff, BigDigit [] data) [private] #
Convert a big uint into a decimal string.

Params:

buffdata The biguint to be converted. Will be destroyed. buff The destination buffer for the decimal string. Must be large enough to store the result, including leading zeros. Will be filled backwards, starting from buff[$-1].

buff.length must be >= (data.length*32)/log2(10) = 9.63296 * data.length.

Returns:

the lowest index of buff which was used.
int biguintFromDecimal(BigDigit [] data, char [] s) [private] #
Convert a decimal string into a big uint.

Params:

data The biguint to be receive the result. Must be large enough to store the result. s The decimal string. May contain 0..9, or _. Will be preserved.

The required length for the destination buffer is slightly less than 1 + s.length/log2(10) = 1 + s.length/3.3219.

Returns:

the highest index of data which was used.