Division by an invariant word
- Cost
- One word product, one low product, a two-word addition and two comparisons. The reciprocal costs one division.
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 and let be normalised, meaning . Its reciprocal is
Since for normalised , we have and fits in a word. Equivalently, is the quotient of the two-word number by , 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 is handled by shifting: with the number of leading zero bits of , divide by and shift the remainder right by bits. The quotient is unchanged. This is why n_preinvert_limb accepts any nonzero : it returns the reciprocal of .
The algorithm#
Input: normalised , its reciprocal , and with and .
Output: with and .
- , a two-word result.
- .
- .
- If : set and .
- If : set and .
- Return and .
Step 4 can be implemented without branches using a mask, and step 5 is rarely taken (Branches and compilers explains what compilers do with them). 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 and define by . Then , because .
Lemma 1. Step 1 computes exactly, with .
Proof. Indeed . Since and , we get because .
Let denote the values after step 1, and let be the exact remainder belonging to the candidate quotient of step 2.
Lemma 2 (Bounds on the candidate remainder). With we have and .
Proof. Multiply the identity of Lemma 1 by and use : . Substituting into gives
For the lower bounds, the first two terms are nonnegative, so . As and , this is greater than ; as , it is at least .
For the upper bound, use , and :
Theorem 3. Algorithm 1 returns the correct quotient and remainder.
Proof. Step 3 computes , since modulo . Since is normalised, . There are three cases.
- . Then by Lemma 2, so step 4 decrements the quotient and sets , which lies in because . Step 5 does nothing.
- and . Step 4 does nothing, and , so step 5 performs any necessary correction.
- and . This can only happen when , so . Step 4 wrongly decrements the quotient and sets , but then , and step 5 undoes the change.
In all cases the final remainder is in . Every update of is an addition of modulo , and the true quotient lies in because , so computing the quotient modulo gives the right answer even if step 2 wraps around.
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_mulmultiplies and reduces the two-word product with one step; the macrosNMOD_RED2andNMOD_RED3reduce 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 annmod_t). They are used throughoutnmod_vec,nmod_poly,nmod_mat,nmod_mpolyand thegrcontexts for ; in particular every dot product innmod_vecends with one such reduction (Dot products modulo a word-size integer).n_mod2_preinv,n_divrem2_preinv,n_div2_preinvandn_divrem_preinv, for a one-word dividend, use instead the Barrett step ofNMOD_REDwith the constant derived from the same reciprocal (Barrett reduction with annmod_t).n_ll_mod_preinvfirst reduces the high word modulo if necessary and then runs the algorithm on the two-word dividend.n_lll_mod_preinvreduces the top two words and then the bottom two.n_mulmod2_preinvmultiplies and reduces the two-word product withn_ll_mod_preinv;n_mulmod_preinvskips the normalisation shift by requiring a normalised modulus.- The macro
udiv_qrnnd_preinvof longlong.h is Algorithm 1 for a normalised divisor, with the quotient. The divisions of limb arrays by a limb in mpn_extras.h, the carries of radix.h arithmetic and the divisions by a leading coefficient in fmpz_mpoly.h use it.
Branches and compilers#
Whether step 4 is taken depends on the input. For the product of two random residues, as in nmod_mul, it is taken for about half of the inputs when is just above , for about 83% when , and for almost all of them when is just below (here is the normalised modulus). Step 5 is almost never taken.
FLINT writes step 4 as a plain if and leaves the code to the compiler. GCC compiles it to a conditional move, without a branch. So does clang, except in a loop of independent reductions, such as res[i] = nmod_mul(a[i], b[i], mod) or a loop of NMOD_RED2: there, when compiling for some x86 processors, it turns the conditional move back into a branch. On random inputs this branch is often mispredicted, and such loops take 2 to 4 times longer than with the conditional move (unless is just below a power of two, where the branch is well predicted). This was observed with clang 18, 19 and 22 when compiling for
- generic x86-64 (
-march=x86-64,x86-64-v3orx86-64-v4); - Intel processors up to Ice Lake, Tiger Lake and Rocket Lake:
-march=haswell,broadwell,skylake,skylake-avx512,cascadelake,icelake-client,icelake-server,tigerlakeandrocketlake, and the Atom processorsgoldmontandtremont.
The code for Alder Lake and later desktop processors (-march=alderlake, raptorlake, meteorlake, arrowlake, ...), Sapphire Rapids and later servers, all AMD Zen processors, and ARM64 keeps the conditional move. What matters is the processor that the code is compiled for, not the one that runs it: configure compiles FLINT for the host processor (Processor-specific code), and a program that calls the inline function nmod_mul in a loop is compiled with its own flags.
Reductions that depend on each other, as in Horner's rule or powering, are not affected (clang keeps the conditional move), nor are functions compiled out of line such as n_mulmod2_preinv and n_ll_mod_preinv.
Some options to avoid the slowdown are: compile with GCC; or compile with clang and the flag -mllvm -x86-cmov-converter=false. The loops above then take the same time for every : 2 to 4 times less than with the branch for most , about 20% more when is just below a power of two.
Referenced from#
- Barrett and Lemire reduction (algorithm)
- Montgomery multiplication (REDC) (algorithm)
- Modular multiplication with a multiword modulus (algorithm)
- Integer division and Newton iteration (algorithm)
- Dot products modulo a word-size integer (algorithm)
- Strong probable prime test (algorithm)
- Division and rounding conventions
- Building, testing and installing (overview)
udiv_qrnnd_preinv- mpn_extras.h (module)
- Basic arithmetic modulo n
nmod_t- nmod.h (module)
- Multiplication with a precomputed inverse
- Exponentiation with a precomputed inverse
- Division with a precomputed inverse
References#
- [GraMol2010] N. Möller and T. Granlund, "Improved division by invariant integers", IEEE Transactions on Computers 60 (2011), 165–175, https://gmplib.org/~tege/division-paper.pdf
- [GraMon1994] Törbjorn Granlund and Peter L. Montgomery : Division by Invariant Integers using Multiplication https://gmplib.org/~tege/divcnst-pldi94.pdf
The FLINT team, “Division by an invariant word,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/arithmetic/moller-granlund.html (generated 2026-11-20).
@misc{flint-doc-algorithms-arithmetic-moller-granlund,
author = {{The FLINT team}},
title = {{Division by an invariant word}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/arithmetic/moller-granlund.html},
note = {Generated 2026-11-20}
}