Function

BINARY and APPLIED ON a AND b

Meaningful only when r is a power of 2.

|a| = |b| = |c| > 0

BIG ENDIAN BINARY and APPLIED ON a AND b

Meaningful only when r is a power of 2.

|a| >= |b| > 0

treats b as if it was represented with the same number of blocks as a

/!\ 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 generalization of the Toom-Cook algorithm, when m = n = 2.

For further reference, see

• http://en.wikipedia.org/wiki/Karatsuba_algorithm
• http://en.wikipedia.org/wiki/Toom–Cook_multiplication

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

big endian 1 block multiplication

Wrapper for a comparison operator that returns true iff a is equal to b.

Wrapper for a comparison operator that returns true iff a is greater or equal to b.

Wrapper for a comparison operator that returns true iff a is greater than b.

LITTLE ENDIAN BINARY and APPLIED ON a AND b

Meaningful only when r is a power of 2.

|a| >= |b| > 0

treats b as if it was represented with the same number of blocks as a

Wrapper for a comparison operator that returns true iff a is less or equal to b.

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

little endian 1 block multiplication

Wrapper for a comparison operator that returns true iff a is less than b.

Wrapper for a comparison operator that returns true iff a is not equal to b.

Function template for number parsing. Endianess provided by the iterator function iterator function must be reverse ordered

Function template for number stringification. Endianess provided by the iterator function

Wrapper for binary operator. Ensures

i >= j
i0, j0, k0 >= 0

Compares two big endian arrays, |a| >= |b|

Computes pow(a, b) using naive exponentiation.

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

Computes pow(a, b) using exponentiation by squaring.

could add an additional base case for b = 1

Returns true if number is 0.

Subtracts two big endian arrays, k >= i >= j wraps