Function

result 1 if a > b; 0 if a = b; -1 otherwise.

public convert(f: number, t: number, a: number[], ai: number, aj: number): number[] source

import convert from '@arithmetic-operations-for/naturals-big-endian/src/api/convert/convert.js'

Converts the input number A represented in base f to a number B represented in base t. If A is 0 the output is B = [0], otherwise all leading zeros are trimmed.

Params:

Name	Type	Attribute	Description
f	number		the base to convert from
t	number		the base to convert to
a	number[]		the origin array
ai	number		start offset in the origin array
aj	number		end offset in the origin array

Return:

The result of the conversion.

public convert_keep_zeros(f: number, t: number, a: number[], ai: number, aj: number): number[] source

import convert_keep_zeros from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/convert_keep_zeros.js'

Converts the input number A represented in base f to a number B represented in base t. All leading zeros resulting from the conversion are kept.

Params:

Name	Type	Attribute	Description
f	number		the base to convert from
t	number		the base to convert to
a	number[]		the origin array
ai	number		start offset in the origin array
aj	number		end offset in the origin array

Return:

The resulting limb array.

public decrement(r: Number, a: Array, ai: Number, aj: Number) source

import decrement from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/sub/decrement.js'

Subtracts 1 from a big endian array.

Wraps on underflow. Hence, does nothing if aj <= ai.

O(|A|) time in the worst case. O(1) amortized time over any number of successive operations starting with A = O(1). O(1) amortized time over O(|A|) successive operations starting with any A.

Params:

Name	Type	Attribute	Description
r	Number		radix
a	Array		first operand
ai	Number		a left
aj	Number		a right

public eq(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import eq from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/eq.js'

Tests whether two big endian arrays are equal.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A = B.

public euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): Array source

import euclidean_algorithm from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/gcd/euclidean_algorithm.js'

No constraints on the input.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		First input number `a>b`.
ai	Number		`a` left bound.
aj	Number		`a` right bound.
b	Array		Second input number `b<a`.
bi	Number		`b` left bound.
bj	Number		`b` right bound.

Return:

Array

The array containing the gcd of A and B (one of A and B). Return as [ d , di , dj ], where d is the array and di and dj are its left and right bounds.

public extended_euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): undefined[] source

import extended_euclidean_algorithm from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/gcd/extended_euclidean_algorithm.js'

No constraints on the input.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		First input number `a>b`.
ai	Number		`a` left bound.
aj	Number		`a` right bound.
b	Array		Second input number `b<a`.
bi	Number		`b` left bound.
bj	Number		`b` right bound.

Return:

public ge(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import ge from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/ge.js'

Compares two big endian arrays: returns true if the first is greater or equal to the second.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A >= B.

public gt(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import gt from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/gt.js'

Compares two big endian arrays: returns true if the first is greater than the second.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A > B.

public iadd(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import iadd from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/add/iadd.js'

Adds a big endian array to another in-place. Wraps on overflow. Works with any combination of array sizes.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand (modified in-place)
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right

Return:

public increment(r: Number, a: Array, ai: Number, aj: Number) source

import increment from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/add/increment.js'

Adds 1 to a big endian array.

Wraps on overflow. Hence, does nothing if aj <= ai.

O(|A|) time in the worst case. O(1) amortized time over any number of successive operations starting with A = O(1). O(1) amortized time over O(|A|) successive operations starting with any A.

Params:

Name	Type	Attribute	Description
r	Number		radix
a	Array		first operand
ai	Number		a left
aj	Number		a right

public jz(a: number[], ai: number, aj: number): boolean source

import jz from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/jz.js'

Returns true if and only if input number A is 0.

Returns true if aj <= ai. O(|A|) time in the worst case. O(1) time if A has no leading zero.

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right

Return:

true if and only if input number is 0.

public le(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import le from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/le.js'

Compares two big endian arrays: returns true if the first is less or equal to the second.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A <= B.

public lt(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import lt from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/lt.js'

Compares two big endian arrays: returns true if the first is less than the second.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A < B.

public mul(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * source

import mul from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/mul/mul.js'

Multiplies two big endian arrays and puts result in a destination array.

Constraints:

C is zero initialized,
|A| >= 0,
|B| >= 0,
|C| >= |A| + |B|.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right
c	Array		result, must be 0 initialized and be able to contain result
ci	Number		c left
cj	Number		c right

Return:

public ne(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): boolean source

import ne from '@arithmetic-operations-for/naturals-big-endian/src/api/compare/ne.js'

Tests whether two big endian arrays are not equal.

Input:

|A| >= 0
|B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

true iff A != B.

public parse(f: number, t: number, string: string): number[] source

import parse from '@arithmetic-operations-for/naturals-big-endian/src/api/convert/parse.js'

Converts a string representation in base f to a limb array in base t.

Params:

Name	Type	Attribute	Description
f	number		radix of the representation
t	number		radix of the limb array
string	string		the input representation

Return:

the resulting limb array

public parse_keep_zeros(f: number, t: number, string: string): number[] source

import parse_keep_zeros from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/parse_keep_zeros.js'

Converts a string representation in base f to a limb array in base t keeping all leading zeros resulting from the conversion process.

Params:

Name	Type	Attribute	Description
f	number		radix of the representation
t	number		radix of the limb array
string	string		the input representation

Return:

the resulting limb array

public stringify(f: number, t: number, a: number[], ai: number, aj: number): string source

import stringify from '@arithmetic-operations-for/naturals-big-endian/src/api/convert/stringify.js'

Converts a limb array in base f to a string representation in base t.

Params:

Name	Type	Attribute	Description
f	number		radix of the limb array
t	number		radix of the representation
a	number[]		the input limb array
ai	number		left bound of the input
aj	number		non-inclusive right bound of the input

Return:

the resulting representation

public translate(f: number, t: number, string: string): string source

import translate from '@arithmetic-operations-for/naturals-big-endian/src/api/convert/translate.js'

Converts a string representation in base f to a string representation in base t.

Params:

Name	Type	Attribute	Description
f	number		radix of the input
t	number		radix of the output
string	string		the input representation

Return:

the output representation

public trim_natural(a: number[], ai: number, aj: number): number[] source

import trim_natural from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/trim_natural.js'

Trim a limb array so that it is either [0] or does not start with any leading zeros. Return a newly allocated array and does not modify the input.

Params:

Name	Type	Attribute	Description
a	number[]		The input limb array.
ai	number
aj	number

Return:

The input but trimmed.

Static Private

private _add(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number) source

import _add from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/add/_add.js'

Adds two big endian arrays and puts result in a destination array. Wraps on overflow. |C| >= |A| >= |B|.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right
c	Array		result, must be 0 initialized
ci	Number		c left
cj	Number		c right

private _alloc(n: number): number[] source

import _alloc from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_alloc.js'

Allocate a new limb array.

Params:

Name	Type	Attribute	Description
n	number		The size of the array to allocate.

Return:

The new limb array.

private _build(base: , number: , data: , n: ): * source

import _build from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_build.js'

Params:

Name	Type	Attribute	Description
base	*
number	*
data	*
n	*

Return:

private _chr(x: number): string source

import _chr from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_chr.js'

Converts a limb to a character representation. This only works if the limb is at most 35.

Params:

Name	Type	Attribute	Description
x	number		The input limb.

Return:

The corresponding character representation.

private _cmp(a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): number source

import _cmp from '@arithmetic-operations-for/naturals-big-endian/src/core/compare/_cmp.js'

Compares two big endian arrays. The second operand cannot have more limbs than the first.

Input:

|A| >= |B| >= 0

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left
bj	number		b right

Return:

result 1 if a > b; 0 if a = b; -1 otherwise.

private _cmp_half(r: Number, a: array, ai: Number, aj: Number): Number source

import _cmp_half from '@arithmetic-operations-for/naturals-big-endian/src/core/compare/_cmp_half.js'

Compares a number A with size n = |A| to R = (r^n)/2. When n=0, R=1/2, hence result is -1.

Params:

Name	Type	Attribute	Description
r	Number		the base
a	array		first operand
ai	Number		a left
aj	Number		a right

Return:

Number

result 1 if A > R; 0 if a = R; -1 otherwise.

private _cmp_half_even_radix(_r: , a: , ai: , aj: ): * source

import _cmp_half_even_radix from '@arithmetic-operations-for/naturals-big-endian/src/core/compare/_cmp_half_even_radix.js'

Params:

Name	Type	Attribute	Description
_r	*
a	*
ai	*
aj	*

Return:

private _cmp_half_odd_radix(_r: , a: , ai: , aj: ): * source

import _cmp_half_odd_radix from '@arithmetic-operations-for/naturals-big-endian/src/core/compare/_cmp_half_odd_radix.js'

Params:

Name	Type	Attribute	Description
_r	*
a	*
ai	*
aj	*

Return:

private _cmp_n(a: number[], ai: number, aj: number, b: number[], bi: number): number source

import _cmp_n from '@arithmetic-operations-for/naturals-big-endian/src/core/compare/_cmp_n.js'

Compares two big endian arrays.

Input:

|A| = |B|

Params:

Name	Type	Attribute	Description
a	number[]		first operand
ai	number		a left
aj	number		a right
b	number[]		second operand
bi	number		b left

Return:

1 if a > b; 0 if a = b; -1 otherwise.

private _convert(f: number, t: number, a: number[], ai: number, aj: number, b: number[], bi: number, bj: number): * source

import _convert from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert.js'

Dispatcher for the various base conversion implementations. The decision is based on the relation f <= t.

Params:

Name	Type	Attribute	Description
f	number		the base to convert from
t	number		the base to convert to
a	number[]		the origin array
ai	number		start offset in the origin array
aj	number		end offset in the origin array
b	number[]		the destination array
bi	number		start offset in the destination array
bj	number		end offset in the destination array

Return:

private _convert_dc(size_small_block: Number, f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _convert_dc from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_dc.js'

O(M(N) log N) where M(N) is multiplication time complexity.

bj - bi >= log_t(f) * ( aj - ai ) ;

Roughly, split number A into two halves A0 * f^l + A1. Convert A0 to B0 and A1 to B1 recursively. Then multiply B0 by f^l in base t and finally add B1.

This implementation is not recursive. It is iterative, and will call a simpler subroutine for the base case.

Params:

Name	Type	Attribute	Description
size_small_block	Number		the size of a small block
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

private _convert_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import _convert_slow from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_slow.js'

F != t

Params:

Name	Type	Attribute	Description
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

Return:

private _convert_to_larger(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import _convert_to_larger from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_larger.js'

Params:

Name	Type	Attribute	Description
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

Return:

private _convert_to_larger_fast(ar: Number, z: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _convert_to_larger_fast from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_larger_fast.js'

Params:

Name	Type	Attribute	Description
ar	Number		the base to convert from
z	Number		if br is the base to convert to then log(br) = z log(ar)
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

private _convert_to_larger_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _convert_to_larger_slow from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_larger_slow.js'

O(N^2). f < t.

Params:

Name	Type	Attribute	Description
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

private _convert_to_smaller(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import _convert_to_smaller from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_smaller.js'

Params:

Name	Type	Attribute	Description
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

Return:

private _convert_to_smaller_fast(br: Number, z: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _convert_to_smaller_fast from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_smaller_fast.js'

Params:

Name	Type	Attribute	Description
br	Number		the base to convert to
z	Number		if ar is the base to convert to then log(ar) = z log(br)
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

private _convert_to_smaller_slow(f: Number, t: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _convert_to_smaller_slow from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_convert_to_smaller_slow.js'

O(N^2). f > t.

|A| >= 1 |B| is large enough to hold the result

Params:

Name	Type	Attribute	Description
f	Number		the base to convert from
t	Number		the base to convert to
a	Array		the origin array
ai	Number		start offset in the origin array
aj	Number		end offset in the origin array
b	Array		the destination array
bi	Number		start offset in the destination array
bj	Number		end offset in the destination array

private _copy(a: number[], ai: number, aj: number, b: number[], bi: number) source

import _copy from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_copy.js'

Copy a limb array into another limb array.

Params:

Name	Type	Attribute	Description
a	number[]		The copied limb array.
ai	number
aj	number
b	number[]		The destination limb array.
bi	number

private _div_limb_with_prefix(r: Number, tmp: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number) source

import _div_limb_with_prefix from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_div_limb_with_prefix.js'

Divides a big endian number by a single limb number. Can only work with limbs of size at most sqrt( 2^53 ). Allows to prefix the dividend with an intermediate remainder.

Does not update the remainder.

Input

0 <= tmp <= d - 1
1 <= d <= r - 1
|Q| = |D|

Params:

Name	Type	Attribute	Description
r	Number		The radix.
tmp	Number		Intermediate remainder (MUST be `< d`).
d	Number		The divisor >= 1.
D	Array		The dividend (NOT modified).
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
Q	Array		The quotient.
Qi	Number		Left of quotient.

private _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) source

import _divmod from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/div/_divmod.js'

Computes the quotient and remainder of two numbers. Uses the most appropriate algorithms depending on the size of the operands. The remainder is written to the dividend array. There are a few assumptions made on the input.

Input

No leading zeros in D or Q.
|D| = |Q| = |R|

Params:

Name	Type	Attribute	Description
r	Number		The base to work with.
D	Array		Dividend array.
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
d	Array		Divisor array.
di	Number		Left of divisor.
dj	Number		Right of divisor.
Q	Array		Quotient array.
Qi	Number		Left of quotient.
Qj	Number		Right of quotient.
R	Array		Remainder array.
Ri	Number		Left of remainder.
Rj	Number		Right of remainder.

private _euclidean_algorithm_loop(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): Array source

import _euclidean_algorithm_loop from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/gcd/_euclidean_algorithm_loop.js'

Euclidean algorithm. Computes the gcd of the two input numbers A and B, A >= B. Input arrays are modified in-place.

Input

A >= B
No leading zeros

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		The first input number A.
ai	Number		Left of A.
aj	Number		Right of A.
b	Array		The second input number B.
bi	Number		Left of B.
bj	Number		Right of B.

Return:

Array

The array containing the gcd of A and B (one of A and B). Return as [ d , di , dj ], where d is the array and di and dj are its left and right bounds.

private _extended_euclidean_algorithm(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import _extended_euclidean_algorithm from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/gcd/_extended_euclidean_algorithm.js'

Precondition:

A >= B
No leading zeroes.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		First input number `a>b`.
ai	Number		`a` left bound.
aj	Number		`a` right bound.
b	Array		Second input number `b<a`.
bi	Number		`b` left bound.
bj	Number		`b` right bound.

Return:

private _extended_euclidean_algorithm_allocate(m: , n: ): undefined[] source

import _extended_euclidean_algorithm_allocate from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/gcd/_extended_euclidean_algorithm_allocate.js'

M >= n >= 0 m >= 1

Params:

Name	Type	Attribute	Description
m	*
n	*

Return:

private _extended_euclidean_algorithm_loop(r: , R0: , R1: , S0: , T0: , S1: , T1: , Q: , X: *): undefined[] source

import _extended_euclidean_algorithm_loop from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/gcd/_extended_euclidean_algorithm_loop.js'

Extended Euclidean algorithm.

Params:

Name	Type	Attribute	Description
r	*
R0	*
R1	*
S0	*
T0	*
S1	*
T1	*
Q	*
X	*

Return:

See:

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Given two input integers a and b, a > b. Let r_0 = a, r_1 = b, s_0 = 1, s_1 = 0, t_0 = 0, t_1 = 1 (Fibonacci :winkemoji:). Let r_{i+1} = r_{i-1} % r_i (division remainder) Let q_i = (r_{i-1} - r_{i+1}) / r_i > 0 (division quotient) An alternative definition is r_{i+1} = r_{i-1} - q_i r_i (with 0 <= r_{i+1} < r_i) then define s_{i+1}="s_{i-1}" - q_i s_i t_{i+1}="t_{i-1}" t_i let k be such that r_i> 0 for all i <= k and r_{k+1}="0." since q_i> 0, if t_{i-1} > 0 and t_i < 0 then t_{i+1} > 0. On the other hand, if t_{i-1} < 0 and t_i > 0 then t_{i+1} < 0. Note that t_2 < 0, so the signs of the t_i alternate: t_0 = 0, t_1 = 1, t_2 < 0, t_3 > 0, t_4 < 0, t_5 > 0, etc. The pattern for t is 0, 1, -, +, -, +, -, etc. The same holds for the s_i with flipped signs: note that s_2 = 1, then s_0 = 1, s_1 = 0, s_2 = 1, s_3 < 0, s_4 > 0, s_5 < 0, etc. The pattern for s is 1, 0, 1, -, +, -, +, etc. | 0 1 2 3 4 5 6 ------------------------ s | 1 0 1 - + - + t | 0 1 - + - + - With i >= 1, |t_{i+1}| >= |t_i| + |t_{i-1}| > |t_i| because q_i >= 1 and |t_i| > 0 and, since the signs are alternating, we have |t_{i-1} - q_i t_i| = |t_{i-1}| + |q_i t_i|. Same goes for s_{i+1} w.r.t s_i and s_{i-1}. Input ----- - No leading zeroes - R0 >= R1 - (two bullets above imply |R1| >= |R0|) - More at _extended_euclidean_algorithm_allocate. Implementation details ---------------------- Here the implementation avoids computing with negative numbers and will only output the absolute value of s_{i} and t_{i}. The signs can be recovered from the number of steps of the algorithm. Note that s_i <= b and t_i <="a" (proof?). equality holds when i="k+1" a are coprime. thus s_i can sit in an array as large same for a. output ------ calling this function returns the number of steps that were executed.<>

private _fill(a: number[], ai: number, aj: number, v: number) source

import _fill from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_fill.js'

Fill the input limb array with a fixed value.

Params:

Name	Type	Attribute	Description
a	number[]		input limb array
ai	number
aj	number
v	number		the value used to fill the input array

private _from_string(string: string): number[] source

import _from_string from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_from_string.js'

Converts a string representation to a limb array representation without radix conversion.

Params:

Name	Type	Attribute	Description
string	string		input string

Return:

output limb array

private _iadd(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _iadd from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/add/_iadd.js'

Adds a big endian array to another. Wraps on overflow. |A| >= |B|.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right

private _iadd_limb(r: Number, x: Number, a: Array, ai: Number, aj: Number) source

import _iadd_limb from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/add/_iadd_limb.js'

Adds single limb to a big endian array. Wraps on overflow.

Input:

|A| >= 1.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
x	Number		limb to add
a	Array		first operand
ai	Number		a left
aj	Number		a right

private _idivmod(r: Number, D: Array, Di: Number, Dj: Number, d: Array, di: Number, dj: Number, Q: Array, Qi: Number, Qj: Number): * source

import _idivmod from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/div/_idivmod.js'

Computes the quotient and remainder of two numbers. Uses the most appropriate algorithm depending on the size of the operands. The remainder is written to the dividend array. There are a few assumptions made on the input.

Input

|d| >= 1
|D| = |Q| >= 1
No leading zeros in D or d.
Q is zero initialized.

Params:

Name	Type	Attribute	Description
r	Number		The base to work with.
D	Array		Dividend / Remainder array (remainder computed in-place).
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
d	Array		Divisor array.
di	Number		Left of divisor.
dj	Number		Right of divisor.
Q	Array		Quotient array (zero initialized).
Qi	Number		Left of quotient.
Qj	Number		Right of quotient.

Return:

private _idivmod_dc(X: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number) source

import _idivmod_dc from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_dc.js'

Input

No leading zeros
|A| = |C|
C must be zero-initialized.

References

https://gmplib.org/manual/Divide-and-Conquer-Division.html

Params:

Name	Type	Attribute	Description
X	Number		The radix.
a	Array		Dividend / Remainder.
ai	Number
aj	Number
b	Array		Divisor.
bi	Number
bj	Number
c	Array		Quotient.
ci	Number
cj	Number

private _idivmod_dc_21(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ): * source

import _idivmod_dc_21 from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_dc_21.js'

Algorithm 3.3 Divide-and-conquer division (2 by 1)

Input

Two nonnegative integers A and B, such that A < β^n B and β^n / 2 ≤ B < β^n. n must be even if n >= THRESHOLD_DIV_DC.

               -----------                 -----
              |  :  |  :  |               |  :  |
               -----------                 -----

Output

The quotient floor( A/B ) and the remainder A mod B.

Complexity

T(n) = 2T'(n/2) + K

Params:

Name	Type	Attribute	Description
r	*
a	*
ai	*
aj	*
b	*
bi	*
bj	*
c	*
ci	*
cj	*

Return:

private _idivmod_dc_32(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ) source

import _idivmod_dc_32 from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_dc_32.js'

Algorithm 3.4 Divide-and-conquer division (3 by 2)

Input

Two nonnegative integers A and B, such that A < β^n B and β^{2n} / 2 ≤ B < β^{2n}. n must be even.

               --------                 -----
              |  |  |  |               |  |  |
               --------                 -----

Output

The quotient floor( A/B ) and the remainder A mod B.

Complexity

T'(n) ≤ T(n) + M(n) + Ln

Params:

Name	Type	Attribute	Description
r	*
a	*
ai	*
aj	*
b	*
bi	*
bj	*
c	*
ci	*
cj	*

private _idivmod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number): * source

import _idivmod_limb from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_limb.js'

Divides a big endian number by a single limb number. Can only work with limbs of size at most sqrt( 2^53 ).

Params:

Name	Type	Attribute	Description
r	Number		The radix.
d	Number		The divisor.
D	Array		The dividend.
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
Q	Array		The quotient.
Qi	Number		Left of quotient.

Return:

private _idivmod_limb_with_prefix(r: Number, tmp: Number, d: Number, D: Array, Di: Number, Dj: Number, Q: Array, Qi: Number) source

import _idivmod_limb_with_prefix from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_limb_with_prefix.js'

Divides a big endian number by a single limb number. Can only work with limbs of size at most sqrt( 2^53 ). Allows to prefix the dividend with an intermediate remainder.

Input

|Q| = |D| >= 1.
NO NEED to reset Q. The loop will set every member of Q.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
tmp	Number		Intermediate remainder (MUST be `< d`).
d	Number		The divisor >= 1.
D	Array		The dividend.
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
Q	Array		The quotient.
Qi	Number		Left of quotient.

private _idivmod_schoolbook(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) source

import _idivmod_schoolbook from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_schoolbook.js'

Computes q <- a / b and a <- a % b. No leading zeros allowed. q has length at least aj - ai

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend / Remainder.
ai	Number
aj	Number
b	Array		Divisor.
bi	Number
bj	Number
q	Array		Quotient.
qi	Number

private _idivmod_schoolbook_large_divisor(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number): * source

import _idivmod_schoolbook_large_divisor from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_schoolbook_large_divisor.js'

Input

Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
No leading zeros (ONLY IN B?)
Q is initialized with some limbs.

Output

The quotient floor( A/B ) and the remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.
q	Array		Quotient.
qi	Number		Left of quotient.

Return:

private _idivmod_schoolbook_subroutine(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) source

import _idivmod_schoolbook_subroutine from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_schoolbook_subroutine.js'

Input

Two integers A and B such that 0 <= A < β^(n+1) and (β^n)/2 <= B < β^n.
|A| = |B| + 1
|Q| = |A|

Output

The quotient floor( A/B ) and the remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.
q	Array		Quotient.
qi	Number		Left of quotient.

private _idivmod_schoolbook_subroutine_do(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, q: Array, qi: Number) source

import _idivmod_schoolbook_subroutine_do from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_schoolbook_subroutine_do.js'

Input

Two integers A and B such that 0 <= A < B * β and (β^n)/2 <= B < β^n. (Hence B >= 1).
|A| = |B| + 1
|Q| = |A|

Output

The quotient floor( A/B ) and the remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.
q	Array		Quotient.
qi	Number		Left of quotient.

private _idivmod_slow(x: Number, r: array, ri: Number, rj: Number, b: array, bi: Number, bj: Number, q: array, qi: Number) source

import _idivmod_slow from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_idivmod_slow.js'

Computes quotient and remainder of two big endian arrays.

Computes quotient and remainder of two big endian arrays using long division algorithm (the one teached in european primary schools).

/!\ This algorithm modifies its first operand.

HYP : q is at least as large as r b is not zero

Params:

Name	Type	Attribute	Description
x	Number		the radix
r	array		dividend and remainder
ri	Number		r left
rj	Number		r right
b	array		divisor
bi	Number		b left
bj	Number		b right
q	array		quotient, must be 0 initialized
qi	Number		q left

private _imod(r: Number, D: Array, Di: Number, Dj: Number, d: Array, di: Number, dj: Number, _: Array, _i: Number, _j: Number): * source

import _imod from '@arithmetic-operations-for/naturals-big-endian/src/api/arithmetic/div/_imod.js'

Computes the remainder of two numbers. Uses the most appropriate algorithm depending on the size of the operands. The remainder is written to the dividend array. There are a few assumptions made on the input.

Input

|d| >= 1
|D| = |_| >= 1
No leading zeros in D or d.

Params:

Name	Type	Attribute	Description
r	Number		The base to work with.
D	Array		Dividend / Remainder array (remainder computed in-place).
Di	Number		Left of dividend.
Dj	Number		Right of dividend.
d	Array		Divisor array.
di	Number		Left of divisor.
dj	Number		Right of divisor.
_	Array		Additional memory array.
_i	Number		Left of memory.
_j	Number		Right of memory.

Return:

private _imod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number) source

import _imod_limb from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_imod_limb.js'

Divides a big endian number by a single limb number and writes the remainder to the dividend array.

Computes a <- a % b. Only works with limbs of size at most sqrt( 2^53 ).

Params:

Name	Type	Attribute	Description
r	Number		The radix of D.
d	Number		The divisor >= 1.
D	Array		The dividend.
Di	Number		Left of D.
Dj	Number		Right of D.

private _imod_schoolbook(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _imod_schoolbook from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_imod_schoolbook.js'

Divides a big endian number by another big endian number and writes the remainder to the dividend array.

Computes a <- a % b. No leading zeros allowed.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend / Remainder.
ai	Number
aj	Number
b	Array		Divisor.
bi	Number
bj	Number

private _imod_schoolbook_large_divisor(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number): * source

import _imod_schoolbook_large_divisor from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_imod_schoolbook_large_divisor.js'

Input

Two integers A and B such that r^(m-1) <= A < r^m and (r^n)/2 <= B < r^(n).
No leading zeros (ONLY IN B?)

Output

The remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.

Return:

private _imod_schoolbook_subroutine(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _imod_schoolbook_subroutine from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_imod_schoolbook_subroutine.js'

Input

Two integers A and B such that 0 <= A < β^(n+1) and (β^n)/2 <= B < β^n.
|A| = |B| + 1

Output

The remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.

private _imod_schoolbook_subroutine_do(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number) source

import _imod_schoolbook_subroutine_do from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_imod_schoolbook_subroutine_do.js'

Input

Two integers A and B such that 0 <= A < B * β and (β^n)/2 <= B < β^n. (Hence B >= 1).
|A| = |B| + 1

Output

The remainder A mod B.

Params:

Name	Type	Attribute	Description
r	Number		The radix.
a	Array		Dividend.
ai	Number		Left of dividend.
aj	Number		Right of dividend.
b	Array		Divisor.
bi	Number		Left of divisor.
bj	Number		Right of divisor.

private _int(x: string): number source

import _int from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_int.js'

Converts an input character representation to a limb.

Params:

Name	Type	Attribute	Description
x	string		input character

Return:

output limb

private _isub(r: Number, a: array, ai: Number, aj: Number, b: array, bi: Number, bj: Number) source

import _isub from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/sub/_isub.js'

Subtracts B from A, |A| >= |B|. Wraps.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	array		first operand
ai	Number		a left
aj	Number		a right
b	array		second operand
bi	Number		b left
bj	Number		b right

private _karatsuba(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * source

import _karatsuba from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/mul/_karatsuba.js'

Multiply two big endian arrays using karatsuba algorithm, |A| >= |B| >= 1, |C| >= |A| + |B|, |A| >= 2.

/!\ BLOCK MULTIPLICATION RESULT MUST HOLD IN THE JAVASCRIPT NUMBER TYPE (DOUBLE i.e. 53 bits)

EXPLANATION

###########

We consider the numbers a and b, both of size N = 2n.

We divide a and b into their lower and upper parts.

a = a1 r^{n} + a0 (1) b = b1 r^{n} + b0 (2)

We express the product of a and b using their lower and upper parts.

a b = (a1 r^{n} + a0) (b1 r^{n} + b0) (3) = a1 b1 r^{2n} + (a1 b0 + a0 b1) r^{n} + a0 b0 (4)

This gives us 4 multiplications with operands of size n. Using a simple trick, we can reduce this computation to 3 multiplications.

We give the 3 terms of (4) the names z0, z1 and z2.

z2 = a1 b1 z1 = a1 b0 + a0 b1 z0 = a0 b0

a b = z2 r^{2n} + z1 r^{n} + z0

We then express z1 using z0, z2 and one additional multiplication.

(a1 + a0)(b1 + b0) = a1 b1 + a0 b0 + (a1 b0 + a0 b1) = z2 + z0 + z1

z1 = (a1 + a0)(b1 + b0) - z2 - z0

AN ANOTHER WAY AROUND (not used here)

(a1 - a0)(b1 - b0) = (a1 b1 + a0 b0) - (a1 b0 + a0 b1) (a0 - a1)(b1 - b0) = (a1 b0 + a0 b1) - (a1 b1 + a0 b0) a b = (r^{2n} + r^{n})a1 b1 + r^{n}(a0 - a1)(b1 - b0) + (r^{n} + 1)a0 b0

This algorithm is a specific case of the Toom-Cook algorithm, when m = n = 2.

For further reference, see

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right
c	Array		result, must be 0 initialized
ci	Number		c left
cj	Number		c right

Return:

private _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) source

import _karatsuba_right_op_is_small from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/mul/_karatsuba_right_op_is_small.js'

Multiply two big endian arrays using karatsuba algorithm, WHEN THE SECOND OPERAND IS SMALL. |A| >= |B| >= 1, |C| >= |A| + |B|, |A| >= 2, Math.ceil(|A|/2) >= |B|.

/!\ BLOCK MULTIPLICATION RESULT MUST HOLD IN THE JAVASCRIPT NUMBER TYPE (DOUBLE i.e. 53 bits)

EXPLANATION

###########

We consider the numbers a and b0. a has size N = 2n, and b0 has size n.

We divide a into its lower and upper parts.

a = a1 r^{n} + a0 (1)

We express the product of a and b0 using these.

a b0 = (a1 r^{n} + a0) b0 (3) = a1 b0 r^{n} + a0 b0 (4)

This gives us 2 multiplications with operands of size n.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand
bi	Number		b left
bj	Number		b right
c	Array		result, must be 0 initialized
ci	Number		c left
cj	Number		c right

private _log(x: , y: ): undefined[] source

import _log from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_log.js'

Params:

Name	Type	Attribute	Description
x	*
y	*

Return:

private _mod_limb(r: Number, d: Number, D: Array, Di: Number, Dj: Number): Number source

import _mod_limb from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/div/_mod_limb.js'

Divides a big endian number by a single limb number and returns only the remainder.

Only works with limbs of size at most sqrt( 2^53 ).

Params:

Name	Type	Attribute	Description
r	Number		The radix of D.
d	Number		The divisor >= 1.
D	Array		The dividend (NOT modified).
Di	Number		Left of D.
Dj	Number		Right of D.

Return:

Number

The remainder D % d.

private _mul(r: Number, a: Array, ai: Number, aj: Number, b: Array, bi: Number, bj: Number, c: Array, ci: Number, cj: Number): * source

import _mul from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/mul/_mul.js'

Computes C = A+B.

Constraints:

C is zero initialized,
|A| >= |B| >= 0,
|C| >= |A| + |B|.

TODO:

Use schoolbook mul if n = O(log m).

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	Array		first operand
ai	Number		a left
aj	Number		a right
b	Array		second operand, cannot have more limbs than A
bi	Number		b left
bj	Number		b right
c	Array		result, must be 0 initialized and be able to contain A+B
ci	Number		c left
cj	Number		c right

Return:

private _mul_limb(r: , x: , b: , bi: , bj: , c: , ci: , cj: ) source

import _mul_limb from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/mul/_mul_limb.js'

Compute x * b where x is a single limb. 0 <= x <= r-1 No restriction on operand sizes.

Params:

Name	Type	Attribute	Description
r	*
x	*
b	*
bi	*
bj	*
c	*
ci	*
cj	*

private _pow_double(r: Number, x: Number, a: Array, ai: Number, aj: Number, c: Array, ci: Number, cj: Number) source

import _pow_double from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/pow/_pow_double.js'

Computes pow(a,x) = a^x using exponentiation by squaring. Writes result to output array.

/!\ |A| >= 1, |C| >= 1, |C| >= |A| * x, |C| = 000...0

Params:

Name	Type	Attribute	Description
r	Number		The base to work with.
x	Number		The power to raise `a` to.
a	Array		The base array.
ai	Number		`a` left.
aj	Number		`b` right.
c	Array		The output array.
ci	Number		`a` left.
cj	Number		`b` right.

private _pow_double_recursive(r: Number, x: Number, a: Array, ai: Number, aj: Number, c: Array, ci: Number, cj: Number) source

import _pow_double_recursive from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/pow/_pow_double_recursive.js'

Computes pow(a,x) = a^x using exponentiation by squaring. Writes result to output array.

/!\ |A| >= 1, |C| >= 1, |C| >= |A| * x, |C| = 000...0

Params:

Name	Type	Attribute	Description
r	Number		The base to work with.
x	Number		The power to raise `a` to.
a	Array		The base array.
ai	Number		`a` left.
aj	Number		`b` right.
c	Array		The output array.
ci	Number		`a` left.
cj	Number		`b` right.

private _reset(a: number[], ai: number, aj: number) source

import _reset from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_reset.js'

Fill the input limb array with zeros.

Params:

Name	Type	Attribute	Description
a	number[]		input limb array
ai	number
aj	number

private _schoolbook_mul(r: , a: , ai: , aj: , b: , bi: , bj: , c: , ci: , cj: ) source

import _schoolbook_mul from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/mul/_schoolbook_mul.js'

Computes the product of two big endian arrays using schoolbook multiplication. |C| >= |A|+|B|.

TODO Can this be optimized if we know that |A| >= |B|? Probably better to do many small passes rather than few large passes ?! This is what this implementation achieves, although it returns correct results even when |A| < |B|.

Params:

Name	Type	Attribute	Description
r	*
a	*
ai	*
aj	*
b	*
bi	*
bj	*
c	*
ci	*
cj	*

private _sub(r: Number, a: array, ai: Number, aj: Number, b: array, bi: Number, bj: Number, c: array, ci: Number, cj: Number) source

import _sub from '@arithmetic-operations-for/naturals-big-endian/src/core/arithmetic/sub/_sub.js'

Subtracts two big endian arrays, |C| >= |A| >= |B|. Wraps.

Params:

Name	Type	Attribute	Description
r	Number		base (radix)
a	array		first operand
ai	Number		a left
aj	Number		a right
b	array		second operand
bi	Number		b left
bj	Number		b right
c	array		result, must be 0 initialized
ci	Number		c left
cj	Number		c right

private _to_string(b: number[]): string source

import _to_string from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_to_string.js'

Convert an entire limb array to a string representation (without changing the radix).

Params:

Name	Type	Attribute	Description
b	number[]		The inpurt limb array.

Return:

The string representation.

private _trim_positive(a: number[], ai: number, aj: number): number source

import _trim_positive from '@arithmetic-operations-for/naturals-big-endian/src/core/convert/_trim_positive.js'

Compute the new inclusive left bound of a limb array by skipping all leading zeros.

Params:

Name	Type	Attribute	Description
a	number[]		The input limb array.
ai	number
aj	number

Return:

The new inclusive left bound of the input.

private _validate(base: , a: , ai: , aj: ): boolean source

import _validate from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_validate.js'

Params:

Name	Type	Attribute	Description
base	*
a	*
ai	*
aj	*

Return:

private _zeros(n: number): number[] source

import _zeros from '@arithmetic-operations-for/naturals-big-endian/src/core/array/_zeros.js'

Allocate a new limb array filled with zeros.

Params:

Name	Type	Attribute	Description
n	number		The size of the allocated array.

Return: