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.

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.