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

checked_reciprocal

Checked version of reciprocal_mg10.

checked_reciprocal_2

Checked version of reciprocal_2_mg10. Returns None if $\mathsf{d} < 2^{127}$.

div

⚠️ Division with remainder.

div_1x1

⚠️ Compute single limb division.

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

⚠️ Reference implementation for div_2x1.

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

⚠️ Reference implementation for div_3x2.

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