Barrett and Lemire reduction

The methods of Barrett and of Lemire, Kaser and Kurz reduce a single word $x$ modulo $n$, rather than a two-word product, using a precomputed approximation of $B/n$. They are cheaper than a two-word Möller–Granlund reduction when the value to be reduced is known to fit in one word, as in hashing, sieving and table lookups. Throughout, $B = 2^{\mathtt{FLINT\_BITS}}$.

Barrett reduction#

Barrett's method [Bar1987] estimates the quotient as follows.

The value $x - \tilde q n$ is at most $x$, so it is computed exactly with word arithmetic even when $2n > B$. n_mod_barrett_lazy returns it, and n_mod_barrett subtracts $n$ once if needed. n_barrett_precomp computes $m$ with one division.

Barrett reduction with an nmod_t#

NMOD_RED reduces a word with the same kind of quotient estimate, but its constant comes from the nmod_t, so it needs no division and no extra field. Let $\nu$ be the number of bits of $n$, that is $2^{\nu - 1} \le n < 2^{\nu}$ and $\mathit{norm} = \mathtt{FLINT\_BITS} - \nu$. The ninv field is the Möller–Granlund reciprocal of $n 2^{\mathit{norm}}$.

So NMOD_RED computes $\tilde q$ as the high word of $a m$ shifted right by $\mathtt{FLINT\_BITS} - 1 - \mathit{norm}$ bits, subtracts $\tilde q n$ (at most $a$, so there is no overflow) and corrects once. This holds for every modulus $1 \le n < B$, including powers of two and $n \ge 2^{\mathtt{FLINT\_BITS} - 1}$, and every word $a$. The cost is one high product, one low product and one comparison, against a full product, a low product and two corrections for a Möller–Granlund step on the two-word number $(0, a)$.

When $n$ has FLINT_BITS bits (mod.norm $= 0$), $a < 2n$ for every word $a$, so NMOD_RED skips the product and only corrects once. The test on mod.norm is moved out of loops by the compiler, and the remaining loop of comparisons can then be trivially vectorized.

Shifting $m$ gives the constants of the same family for other input sizes: $\lfloor m / 2^k \rfloor = \lfloor (2^{\nu + \mathtt{FLINT\_BITS} - 1 - k} - 1)/n \rfloor$ for $0 \le k < \nu + \mathtt{FLINT\_BITS} - 1$. For instance $k = \nu - 1$ gives $\lfloor (B - 1)/n \rfloor$, which is the constant of n_barrett_precomp unless $n$ is a power of two.

Lemire–Kaser–Kurz reduction#

The method of Lemire, Kaser and Kurz [LKK2019] computes the remainder directly from the fractional part of $x/n$. With $c = \lceil B/n \rceil$, the low word $xc \bmod B$ approximates $B \{x/n\}$, where $\{\cdot\}$ denotes the fractional part; multiplying it by $n$ and keeping the high word gives $x \bmod n$. The approximation is exact when $n$ and $x$ are below $2^{\mathtt{FLINT\_BITS}/2}$, which is the condition required by n_mod_lemire. The method needs no correction step, but its range restriction makes it useful only for half-word values.

@misc{flint-doc-algorithms-arithmetic-barrett,
  author       = {{The FLINT team}},
  title        = {{Barrett and Lemire reduction}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/arithmetic/barrett.html},
  note         = {Generated 2026-11-02}
}