Function reciprocal

pub fn reciprocal(d: u64) -> u64

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

Requires $\mathsf{d} ∈ [2^{63}, 2^{64})$, i.e. the highest bit of $\mathsf{d}$ must be set.

Using MG10 algorithm 3. See also the intx implementation. Here is a direct translation of the algorithm to Python for reference:

d0 = d % 2
d9 = d // 2**55
d40 = d // 2**24 + 1
d63 = (d + 1) // 2
v0 = (2**19 - 3 * 2**8) // d9
v1 = 2**11 * v0 - v0**2 * d40 // 2**40 - 1
v2 = 2**13 * v1 + v1 * (2**60 - v1 * d40) // 2**47
e = 2**96 - v2 * d63 + (v2 // 2) * d0
v3 = (2**31 * v2 +v2 * e // 2**65) % 2**64
v4 = (v3 - (v3 + 2**64 + 1) * d // 2**64) % 2**64