Module div_limb 

Implementation of constant-time division via reciprocal precomputation, as described in “Improved Division by Invariant Integers” by Niels Möller and Torbjorn Granlund (DOI: 10.1109/TC.2010.143, https://gmplib.org/~tege/division-paper.pdf).

Structs

Reciprocal

A pre-calculated reciprocal for division by a single limb.

Functions

div2by1 🔒

Calculate the quotient and the remainder of the division of a wide word (supplied as high and low words) by d, with a precalculated reciprocal v.

div3by2 🔒

Given two long integers u = (..., u0, u1, u2) and v = (..., v0, v1) (where u2 and v1 are the most significant limbs), where floor(u / v) <= Limb::MAX, calculates q such that q - 1 <= floor(u / v) <= q. In place of v1 takes its reciprocal, and assumes that v was already pre-shifted so that v1 has its most significant bit set (that is, the reciprocal’s shift is 0).

mul_rem 🔒

Computes (a * b) % d.

reciprocal

Calculates the reciprocal of the given 64-bit divisor with the highmost bit set.

rem_limb_with_reciprocal 🔒

Divides u by the divisor encoded in the reciprocal, and returns the remainder.

short_div 🔒

Calculates dividend / divisor, given dividend and divisor along with their maximum bitsizes.