Module div

⚠️ Collection of division algorithms.

Warning. Most functions in this module are currently not considered part of the stable API and may be changed or removed in future minor releases.

All division algorithms also compute the remainder. There is no benefit to splitting the division and remainder into separate functions, since the remainder is always computed as part of the division algorithm.

These functions are adapted from algorithms in MG10 and K97.

Functions

div

⚠️ Division with remainder.

div_2x1

⚠️ Computes the quotient and remainder of a u128 divided by a u64.

div_2x1_mg10

⚠️ Computes the quotient and remainder of a u128 divided by a u64.

div_2x1_ref

div_3x2

⚠️ Computes the quotient of a 192 bits divided by a normalized u128.

div_3x2_mg10

⚠️ Computes the quotient of a 192 bits divided by a normalized u128.

div_3x2_ref

TODO: This implementation is off by one.

div_nx1

⚠️ Compute single limb division.

div_nx2

⚠️ Compute double limb division.

div_nx1_normalized

⚠️ Compute single limb normalized division.

div_nx2_normalized

⚠️ Compute double limb normalized division.

div_nxm

⚠️ In-place Knuth long division with implicit normalization and reciprocals.

div_nxm_normalized

⚠️ In-place Knuth normalized long division with reciprocals.

reciprocal

⚠️ Computes $\floor{\frac{2^{128} - 1}{\mathsf{d}}} - 2^{64}$.

reciprocal_2

⚠️ Computes $\floor{\frac{2^{192} - 1}{\mathsf{d}}} - 2^{64}$.

reciprocal_2_mg10

⚠️ Computes $\floor{\frac{2^{192} - 1}{\mathsf{d}}} - 2^{64}$.

reciprocal_mg10

⚠️ Computes $\floor{\frac{2^{128} - 1}{\mathsf{d}}} - 2^{64}$.

reciprocal_ref

⚠️ Computes $\floor{\frac{2^{128} - 1}{\mathtt{d}}} - 2^{64}$.