Module Field_ops_lib.Approx_msb_multiplier

The exact error of the approximation is dependent on the config provided.

The radix-2 approx msb multiplier computes the approximation as follows.

1. Given two numbers x and y, represent them as x1 + (2^k) * x0 and y1 + (2^k) * x0. The exact value of k is determined from the provided config. (Larger k will yield a larger approximation error)

2. The product of these two numbers can be written as follows

(x1 + (2^k) * x0) * (y1 + (2^k) * y0 = (x1y1 * 2^2k) + ((x0y1 + x1y0) * (2^k)) + x0y0

3. As we are computing an approximation, we drop the last term x0y0. The first term x1y1 is computed with a full multiplier (this implementation uses the karatsuba-ofman multiplier). The middle two terms (x0y1 and x1y0) are recursively computed with the Approx_msb_multiplier

4. The base case of the recursion is implemented using a ground multiplier.

This algorithm is largely similar to those of Half_width_multiplier, except it uses the upper half and is not exact.

Our implementation support both 2-part splitting (Radix_2) as well as 3-part splitting (Radix_3). 3-part splitting is similar to the above, but breaks the terms to be multiplied into 3 parts.

As mentioned, the exact upper-bound under-approximation is dependent on the provided k. Please refer to the source of Field_ops_model for expect tests that demonstrates this calculation.