FLINT3.7.0-dev
Algorithm

Division by an invariant word

Cost
One 1×1→21 \times 1 \to 2 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 B=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}} and let dd be normalised, meaning B/2≤d<BB/2 \le d < B. Its reciprocal is

v=⌊B2−1d⌋−B.v = \left\lfloor \frac{B^2 - 1}{d} \right\rfloor - B.

Since B<(B2−1)/d<2BB < (B^2 - 1)/d < 2B for normalised dd, we have 0<v<B0 < v < B and vv fits in a word. Equivalently, vv is the quotient of the two-word number (B−1−d)B+(B−1)(B - 1 - d) B + (B - 1) by dd, 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≠0d \ne 0 is handled by shifting: with ss the number of leading zero bits of dd, divide u2su 2^s by d2sd 2^s and shift the remainder right by ss bits. The quotient is unchanged. This is why n_preinvert_limb accepts any nonzero nn: it returns the reciprocal of n2sn 2^s.

The algorithm#

Algorithm 1: Two-by-one division with a precomputed reciprocal

Input: normalised dd, its reciprocal vv, and u=u1B+u0u = u_1 B + u_0 with 0≤u1<d0 \le u_1 < d and 0≤u0<B0 \le u_0 < B.

Output: q,rq, r with u=qd+ru = qd + r and 0≤r<d0 \le r < d.

  1. (q1,q0)←vu1+(u1B+u0)(q_1, q_0) \gets v u_1 + (u_1 B + u_0), a two-word result.
  2. q1←(q1+1) mod Bq_1 \gets (q_1 + 1) \bmod B.
  3. r←(u0−q1d) mod Br \gets (u_0 - q_1 d) \bmod B.
  4. If r>q0r > q_0: set q1←(q1−1) mod Bq_1 \gets (q_1 - 1) \bmod B and r←(r+d) mod Br \gets (r + d) \bmod B.
  5. If r≥dr \ge d: set q1←q1+1q_1 \gets q_1 + 1 and r←r−dr \gets r - d.
  6. Return q=q1q = q_1 and rr.

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 m=B+v=⌊(B2−1)/d⌋m = B + v = \lfloor (B^2 - 1)/d \rfloor and define kk by md=B2−kmd = B^2 - k. Then 1≤k≤d1 \le k \le d, because B2−1−d<md≤B2−1B^2 - 1 - d < md \le B^2 - 1.

Lemma 1. Step 1 computes q1B+q0=mu1+u0q_1 B + q_0 = m u_1 + u_0 exactly, with q1<Bq_1 < B.

Proof. Indeed vu1+u1B+u0=mu1+u0v u_1 + u_1 B + u_0 = m u_1 + u_0. Since md≤B2−1md \le B^2 - 1 and u1≤d−1u_1 \le d - 1, we get mu1+u0≤B2−1−m+B−1<B2m u_1 + u_0 \le B^2 - 1 - m + B - 1 < B^2 because m>Bm > B.

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

Lemma 2 (Bounds on the candidate remainder). With M=max⁡(q0,B−d)M = \max(q_0, B - d) we have q0−B<R<Mq_0 - B < R < M and R≥−dR \ge -d.

Proof. Multiply the identity of Lemma 1 by dd and use md=B2−kmd = B^2 - k: dq1B=(B2−k)u1+du0−dq0d q_1 B = (B^2 - k) u_1 + d u_0 - d q_0. Substituting into BR=B(u1B+u0)−Bdq1−BdB R = B(u_1 B + u_0) - B d q_1 - B d gives

BR=ku1+(B−d)u0+dq0−Bd.B R = k u_1 + (B - d) u_0 + d q_0 - B d.

For the lower bounds, the first two terms are nonnegative, so R≥d(q0−B)/BR \ge d (q_0 - B)/B. As q0−B<0q_0 - B < 0 and d<Bd < B, this is greater than q0−Bq_0 - B; as q0≥0q_0 \ge 0, it is at least −d-d.

For the upper bound, use k≤dk \le d, u1≤d−1u_1 \le d - 1 and u0≤B−1u_0 \le B - 1:

BR≤d(d−1)+(B−d)(B−1)+dq0−Bd=(B−d)2−B+dq0<(B−d)M+dM=BM.\begin{aligned} B R &\le d(d-1) + (B - d)(B - 1) + d q_0 - B d \\ &= (B - d)^2 - B + d q_0 < (B - d) M + d M = B M. \end{aligned}

Theorem 3. Algorithm 1 returns the correct quotient and remainder.

Proof. Step 3 computes r=R mod Br = R \bmod B, since u−(q1+1)d≡u0−(q1+1)du - (q_1 + 1) d \equiv u_0 - (q_1 + 1) d modulo BB. Since dd is normalised, B≤2dB \le 2d. There are three cases.

  • R<0R < 0. Then r=R+B>q0r = R + B > q_0 by Lemma 2, so step 4 decrements the quotient and sets r=R+dr = R + d, which lies in [0,d)[0, d) because −d≤R<0-d \le R < 0. Step 5 does nothing.
  • R≥0R \ge 0 and r=R≤q0r = R \le q_0. Step 4 does nothing, and 0≤R<M<B≤2d0 \le R < M < B \le 2d, so step 5 performs any necessary correction.
  • R≥0R \ge 0 and r=R>q0r = R > q_0. This can only happen when M=B−dM = B - d, so R<B−dR < B - d. Step 4 wrongly decrements the quotient and sets r=R+d<Br = R + d < B, but then d≤r<2dd \le r < 2d, and step 5 undoes the change.

In all cases the final remainder is in [0,d)[0, d). Every update of q1q_1 is an addition of ±1\pm 1 modulo BB, and the true quotient lies in [0,B)[0, B) because u1<du_1 < d, so computing the quotient modulo BB 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.

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 dd is just above B/2B/2, for about 83% when d=3B/4d = 3B/4, and for almost all of them when dd is just below BB (here d=n2sd = n 2^s 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 nn 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-v3 or x86-64-v4);
  • Intel processors up to Ice Lake, Tiger Lake and Rocket Lake: -march=haswell, broadwell, skylake, skylake-avx512, cascadelake, icelake-client, icelake-server, tigerlake and rocketlake, and the Atom processors goldmont and tremont.

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 nn: 2 to 4 times less than with the branch for most nn, about 20% more when nn is just below a power of two.

Referenced from#

References#

Cite this page

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).