Division by an invariant word

To divide a two-word number by a fixed single word without a hardware division, FLINT uses the algorithm of Möller and Granlund [GraMol2010] (Algorithm 4 in their paper), which multiplies by a precomputed reciprocal of the divisor. Every _preinv function in ulong_extras that reduces or divides by a single word uses it.

The reciprocal#

Let $B = 2^{\mathtt{FLINT\_BITS}}$ and let $d$ be normalised, meaning $B/2 \le d < B$. Its reciprocal is

Since $B < (B^2 - 1)/d < 2B$ for normalised $d$, we have $0 < v < B$ and $v$ fits in a word. Equivalently, $v$ is the quotient of the two-word number $(B - 1 - d) B + (B - 1)$ by $d$, which is how n_preinvert_limb_prenorm computes it with a single hardware division. On platforms without a fast two-by-one division instruction, a table lookup followed by Newton steps is used instead, as in GMP.

An arbitrary divisor $d \ne 0$ is handled by shifting: with $s$ the number of leading zero bits of $d$, divide $u 2^s$ by $d 2^s$ and shift the remainder right by $s$ bits. The quotient is unchanged. This is why n_preinvert_limb accepts any nonzero $n$: it returns the reciprocal of $n 2^s$.

The algorithm#

Step 4 can be implemented without branches using a mask, and step 5 is rarely taken. Compared with the older method of Granlund and Montgomery [GraMon1994], which needs a high product and a full product in the correction, this algorithm replaces one full product with a cheaper low product.

Correctness#

Let $m = B + v = \lfloor (B^2 - 1)/d \rfloor$ and define $k$ by $md = B^2 - k$. Then $1 \le k \le d$, because $B^2 - 1 - d < md \le B^2 - 1$.

Let $q_1, q_0$ denote the values after step 1, and let $R = u - (q_1 + 1) d$ be the exact remainder belonging to the candidate quotient $q_1 + 1$ of step 2.

Use in FLINT#

The reciprocal of The reciprocal is the ninv field of every nmod_t, so this algorithm is the default modular reduction for all of FLINT's arithmetic modulo word-size integers.

• nmod_mul multiplies and reduces the two-word product with one step; the macros NMOD_RED2 and NMOD_RED3 reduce two and three words with one and two steps. NMOD_RED, for one word, uses instead a Barrett step whose constant is derived from the same reciprocal (Barrett reduction with an nmod_t). They are used throughout nmod_vec, nmod_poly, nmod_mat, nmod_mpoly and the gr contexts for $\mathbb{Z}/n\mathbb{Z}$; in particular every dot product in nmod_vec ends with one such reduction (Dot products modulo a word-size integer).
• n_mod2_preinv, n_divrem2_preinv and n_div2_preinv shift a one-word dividend into two words and run Algorithm 1 once. The condition $u_1 < d$ holds automatically after shifting.
• n_ll_mod_preinv first reduces the high word modulo $n$ if necessary and then runs the algorithm on the two-word dividend.
• n_lll_mod_preinv reduces the top two words and then the bottom two.
• n_mulmod2_preinv multiplies and reduces the two-word product with n_ll_mod_preinv; n_mulmod_preinv skips the normalisation shift by requiring a normalised modulus.