Home Manual Reference Source

References

api/arithmetic/add

summary
public	F add(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * Adds two big endian arrays and puts result in a destination array.
public	F iadd(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * Adds a big endian array to another *in-place*.
public	F increment(r: Number, a: Array, ai: Number, aj: Number) Adds 1 to a big endian array.

api/arithmetic/div

summary
private	F _divmod(r: Number, D: Array, Di: Number, Dj: Number, d: Array, di: Number, dj: Number, Q: Array, Qi: Number, Qj: Number, R: Array, Ri: Number, Rj: Number) Computes the quotient and remainder of two numbers.
private	F _idivmod(r: Number, D: Array, Di: Number, Dj: Number, d: Array, di: Number, dj: Number, Q: Array, Qi: Number, Qj: Number): * Computes the quotient and remainder of two numbers.
private	F _imod(r: Number, D: Array, Di: Number, Dj: Number, d: Array, di: Number, dj: Number, _: Array, _i: Number, _j: Number): * Computes the remainder of two numbers.

api/arithmetic/gcd

summary
public	F euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): Array No constraints on the input.
public	F extended_euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): undefined[] No constraints on the input.

api/arithmetic/mul

summary
public	F mul(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * Multiplies two big endian arrays and puts result in a destination array.

api/arithmetic/sub

summary
public	F decrement(r: Number, a: Array, ai: Number, aj: Number) Subtracts 1 from a big endian array.

api/compare

summary
public	F cmp(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): number Compares two big endian arrays with little constraints on the operands.
public	F eq(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Tests whether two big endian arrays are equal.
public	F ge(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Compares two big endian arrays: returns true if the first is greater or equal to the second.
public	F gt(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Compares two big endian arrays: returns true if the first is greater than the second.
public	F jz(a: number[], ai: number, aj: number): boolean Returns true if and only if input number A is 0.
public	F le(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Compares two big endian arrays: returns true if the first is less or equal to the second.
public	F lt(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Compares two big endian arrays: returns true if the first is less than the second.
public	F ne(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean Tests whether two big endian arrays are not equal.

api/convert

summary
public	F convert(f: number, t: number, a: number[], ai: number, aj: number): number[] Converts the input number A represented in base f to a number B represented in base t.
public	F parse(f: number, t: number, string: string): number[] Converts a string representation in base f to a limb array in base t.
public	F stringify(f: number, t: number, a: number[], ai: number, aj: number): string Converts a limb array in base f to a string representation in base t.
public	F translate(f: number, t: number, string: string): string Converts a string representation in base f to a string representation in base t.

core/arithmetic/add

summary
private	F _add(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number) Adds two big endian arrays and puts result in a destination array.
private	F _iadd(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) Adds a big endian array to another.
private	F _iadd_limb(r: Number, x: Number, a: Array, ai: Number, aj: Number) Adds single limb to a big endian array.

core/arithmetic/div

summary
private	F _div_limb_with_prefix(r: Number, tmp: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number) Divides a big endian number by a single limb number.
private	F _idivmod_dc(X: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number) Input No leading zeros \|A\| = \|C\| C must be zero-initialized.
private	F _idivmod_dc_21(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ): * Algorithm 3.3 Divide-and-conquer division (2 by 1)
private	F _idivmod_dc_32(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ) Algorithm 3.4 Divide-and-conquer division (3 by 2)
private	F _idivmod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number): * Divides a big endian number by a single limb number.
private	F _idivmod_limb_with_prefix(r: Number, tmp: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number) Divides a big endian number by a single limb number.
private	F _idivmod_schoolbook(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) Computes q <- a / b and a <- a % b.
private	F _idivmod_schoolbook_large_divisor(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number): * Input Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
private	F _idivmod_schoolbook_subroutine(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) Input Two integers A and B such that 0 <= A < β^(n+1) and (β^n)/2 <= B < β^n.
private	F _idivmod_schoolbook_subroutine_do(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) Input Two integers A and B such that 0 <= A < B * β and (β^n)/2 <= B < β^n.
private	F _idivmod_slow(x: Number, r: array, ri: Number, rj: Number, b: array, bi: Number, bj: Number, q: array, qi: Number) Computes quotient and remainder of two big endian arrays.
private	F _imod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number) Divides a big endian number by a single limb number and writes the remainder to the dividend array.
private	F _imod_schoolbook(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) Divides a big endian number by another big endian number and writes the remainder to the dividend array.
private	F _imod_schoolbook_large_divisor(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * Input Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
private	F _imod_schoolbook_subroutine(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) Input Two integers A and B such that 0 <= A < β^(n+1) and (β^n)/2 <= B < β^n.
private	F _imod_schoolbook_subroutine_do(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) Input Two integers A and B such that 0 <= A < B * β and (β^n)/2 <= B < β^n.
private	F _mod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number): Number Divides a big endian number by a single limb number and returns only the remainder.

core/arithmetic/gcd

summary
private	F _euclidean_algorithm_loop(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): Array Euclidean algorithm.
private	F _extended_euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * Precondition: A >= B No leading zeroes.
private	F _extended_euclidean_algorithm_allocate(m: , n: ): undefined[] M >= n >= 0 m >= 1
private	F _extended_euclidean_algorithm_loop(r: , R0: , R1: , S0: , T0: , S1: , T1: , Q: , X: *): undefined[] Extended Euclidean algorithm.

core/arithmetic/mul

summary
private	F _karatsuba(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * Multiply two big endian arrays using karatsuba algorithm, \|A\| >= \|B\| >= 1, \|C\| >= \|A\| + \|B\|, \|A\| >= 2.
private	F _karatsuba_right_op_is_small(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number) Multiply two big endian arrays using karatsuba algorithm, WHEN THE SECOND OPERAND IS SMALL.
private	F _mul(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * Computes C = A+B.
private	F _mul_limb(r: , x: , b: , bi: , bj: , c: , ci: , cj: ) Compute x * b where x is a single limb.
private	F _schoolbook_mul(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ) Computes the product of two big endian arrays using schoolbook multiplication.
private	V _toom22: *

core/arithmetic/pow

summary
private	F _pow_double(r: Number, x: Number, a: Array, ai: Number, aj: Number, c: Array, ci: Number, cj: Number) Computes `pow(a,x) = a^x` using exponentiation by squaring.
private	F _pow_double_recursive(r: Number, x: Number, a: Array, ai: Number, aj: Number, c: Array, ci: Number, cj: Number) Computes `pow(a,x) = a^x` using exponentiation by squaring.

core/arithmetic/sub

summary
private	F _isub(r: Number, a: array, ai: Number, aj: Number, b: array, bi: Number, bj: Number) Subtracts B from A, \|A\| >= \|B\|.
private	F _sub(r: Number, a: array, ai: Number, aj: Number, b: array, bi: Number, bj: Number, c: array, ci: Number, cj: Number) Subtracts two big endian arrays, \|C\| >= \|A\| >= \|B\|.

core/array

summary
private	F _alloc(n: number): number[] Allocate a new limb array.
private	F _build(base: , number: , data: , n: ): *
private	F _copy(a: number[], ai: number, aj: number, b: number[], bi: number) Copy a limb array into another limb array.
private	F _fill(a: number[], ai: number, aj: number, v: number) Fill the input limb array with a fixed value.
private	F _reset(a: number[], ai: number, aj: number) Fill the input limb array with zeros.
private	F _validate(base: , a: , ai: , aj: ): boolean
private	F _zeros(n: number): number[] Allocate a new limb array filled with zeros.

core/compare

summary
private	F _cmp(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): number Compares two big endian arrays.
private	F _cmp_half(r: Number, a: array, ai: Number, aj: Number): Number Compares a number A with size n = \|A\| to R = (r^n)/2.
private	F _cmp_half_even_radix(_r: , a: , ai: , aj: ): *
private	F _cmp_half_odd_radix(_r: , a: , ai: , aj: ): *
private	F _cmp_n(a: number[], ai: number, aj: number, b: number[], bi: number): number Compares two big endian arrays.

core/convert

summary
private	F _chr(x: number): string Converts a limb to a character representation.
private	F _convert(f: number, t: number, a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): * Dispatcher for the various base conversion implementations.
private	F _convert_dc(size_small_block: Number, f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) O(M(N) log N) where M(N) is multiplication time complexity.
private	F _convert_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * F != t
private	F _convert_to_larger(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): *
private	F _convert_to_larger_fast(ar: Number, z: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number)
private	F _convert_to_larger_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) O(N^2).
private	F _convert_to_smaller(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): *
private	F _convert_to_smaller_fast(br: Number, z: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number)
private	F _convert_to_smaller_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) O(N^2).
private	F _from_string(string: string): number[] Converts a string representation to a limb array representation without radix conversion.
private	F _int(x: string): number Converts an input character representation to a limb.
private	F _log(x: , y: ): undefined[]
private	F _to_string(b: number[]): string Convert an entire limb array to a string representation (without changing the radix).
private	F _trim_positive(a: number[], ai: number, aj: number): number Compute the new inclusive left bound of a limb array by skipping all leading zeros.
public	F convert_keep_zeros(f: number, t: number, a: number[], ai: number, aj: number): number[] Converts the input number A represented in base f to a number B represented in base t.
public	F parse_keep_zeros(f: number, t: number, string: string): number[] Converts a string representation in base f to a limb array in base t keeping all leading zeros resulting from the conversion process.
public	F trim_natural(a: number[], ai: number, aj: number): number[] Trim a limb array so that it is either [0] or does not start with any leading zeros.

core/thresholds

summary
public	V THRESHOLD_CONVERT_DC: *
public	V THRESHOLD_DIV_DC: *
public	V THRESHOLD_MUL_TOOM22: number

Directories