Module karatsuba 

Karatsuba multiplication:

This is a method which reduces the complexity of multiplication from O(n^2) to O(n^1.585). For smaller numbers, it is best to stick to schoolbook multiplication, taking advantage of better cache locality and avoiding recursion.

In general, we consider the multiplication of two numbers of an equal size, n bits. Setting b = 2^(n/2), then we can decompose the values: x•y = (x0 + x1•b)(y0 + y1•b)

This equation is equivalent to a linear combination of three products of size n/2, which may each be reduced by applying the same optimization. Setting z0 = x0y0, z1 = (x0 + x1)(y1 + y0), z2 = x1y1: x•y = z0 + (z1 - z0 - z2)•b + z2•b^2

Considering each sub-product as a tuple of integers (lo, hi), the product is calculated as follows (with appropriate carries): [z0.0, z0.1 + z1.0 - z0.0 - z2.0, z1.1 - z0.1 + z2.0 - z2.1, z2.1]

Squaring uses a similar optimization, breaking the operation down into two half-size squarings and a half-size multiplication:

x^2 = (x0 + x1•b)^2 = x0^2 + 2x0x1•b + (x1•b)^2

The wrapping implementations of these methods employ variations on these algorithms. Because the fixed-size implementations for power-of-two Uint sizes are optimized well by the compiler, the dynamic implementations break down large multiplications into calls to these optimized methods.

Constants

MIN_STARTING_LIMBS

Functions

concat_wide 🔒

Join two Uints into an output Uint, potentially larger than both in size.

previous_power_of_2 🔒

Compute the power of 2 p such that p <= value < p*2.

resize_wide 🔒

Resize a pair of Uints.

widening_mul_fixed

Compute a wide multiplication result for fixed-size arguments. Common power-of-two limb counts are implemented explicitly and used as a basis for general multiplication.

widening_square_fixed

Compute a wide squaring result for a fixed-size argument. Common power-of-two limb counts are implemented explicitly and used as a basis for general squaring.

wrapping_mul

Multiply two limb slices, placing the potentially-truncated result in out.

wrapping_mul_fixed

Compute a wrapping multiplication result for a fixed LHS and dynamic RHS argument. Common power-of-two limb counts are implemented explicitly and used as a basis for general multiplication.

wrapping_square 🔒

Square a limb slice, placing the potentially-truncated result in out.

wrapping_square_fixed

Compute a wrapping square for a fixed-size argument. This method defers to the dynamic implementation, but inlining results in the selection of an efficient algorithm.