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}$.