FLINT3.7.0-dev
Guide · nmod_vec.h

SIMD kernels of the element-wise operations

On x86-64 with AVX-512 (F, DQ and VL) or AVX2, and on ARM64 with NEON, _nmod_vec_reduce, _nmod_vec_mul, _nmod_vec_scalar_mul_nmod and _nmod_vec_scalar_addmul_nmod run vector kernels chosen from the size of nn, and so do their lazy variants (Lazy variants). The instruction set is the one FLINT is compiled for (for instance -march=native, which configure sets by default): there is no run-time detection, and FLINT_MACHINE_VECTORS_FORCE_GENERIC or FLINT_MACHINE_VECTORS_STRICT_C turn the kernels off. Below NMOD_VEC_SIMD_MIN_LEN entries the scalar code runs: 8, or with the 512-bit kernels FLINT_NMOD_VEC_AVX512_MIN_LEN of flint-mparam.h, which is 16 on Intel processors. Inside FLINT functions, where the length varies from call to call, the kernels lost on vectors of fewer than 8 entries. On Intel, a 512-bit load of entries written just before by narrow stores waits for these stores, which cannot forward their data to it: 8 to 15 such entries ran at 0.60-0.95x (Ice Lake, Cascade Lake, Nov 2026), and Zen 4 has no such loss.

With AVX-512, the last entries are handled by one masked vector rather than a scalar tail. From 128 entries, when the output is not aligned to 64 bytes and every vector has the same offset modulo 64 bytes, one masked vector first handles the entries up to the next 64-byte boundary, so that the main loop reads and writes whole cache lines. With AVX2, under the same conditions modulo 32 bytes, the scalar code first handles the entries up to the next 32-byte boundary, so that the 256-bit loads and stores do not cross cache lines. On ARM64, from 16 entries, the NEON kernels are interleaved with the scalar code, 4 entries of each per block of 8 (the scalar multiplier runs beside the NEON one); the NEON kernels alone handle the rest.

On Intel processors up to Ice Lake (Skylake-SP, Cascade Lake, Ice Lake-SP), 512-bit multiplications lower the clock of the core for some time after they run. After the multiplying kernels the clock was 12-22% lower on Cascade Lake. The kernels remain faster than the scalar code, but the scalar code that follows them runs slower: functions that alternate short kernel calls with scalar work are slightly impacted (e.g. nmod_mpoly_gcd and the geometric evaluation and interpolation, ran at 0.80-0.90x on Cascade Lake). Intel Sapphire Rapids and AMD Zen 4 show no such fixed offset, and Ice Lake and Rocket Lake client processors little or none.

Below, nn has ν\nu bits, 2ν−1≤n<2ν2^{\nu - 1} \le n < 2^{\nu}, and m=⌊(2ν+63−1)/n⌋m = \lfloor (2^{\nu + 63} - 1)/n \rfloor is the constant of NMOD_RED (Barrett reduction with an nmod_t), on 64-bit machines.

Reduction of words#

_nmod_vec_reduce reduces any 64-bit words. Its kernels use products of 32-bit halves only, with the constant m1=⌊m/232⌋=⌊(2ν+31−1)/n⌋<232m_1 = \lfloor m/2^{32} \rfloor = \lfloor (2^{\nu + 31} - 1)/n \rfloor < 2^{32} (Barrett reduction with an nmod_t).

ν\nuKernelMethodCorrections
64fullworda<2na < 2none
33 to 63top32q=⌊⌊a/232⌋m1/2ν−1⌋q = \lfloor \lfloor a/2^{32} \rfloor m_1 / 2^{\nu - 1} \rfloor, then a−qna - qnone (two at 33)
6 to 32fold29t=⌊a/2ν+29⌋(2ν+29 mod n)+(a mod 2ν+29)t = \lfloor a/2^{\nu + 29} \rfloor (2^{\nu + 29} \bmod n) + (a \bmod 2^{\nu + 29}), then q=⌊⌊t/2ν−2⌋m1/233⌋q = \lfloor \lfloor t/2^{\nu - 2} \rfloor m_1 / 2^{33} \rfloor and t−qnt - qnone
2 to 5fold32t=⌊a/232⌋(232 mod n)+(a mod 232)t = \lfloor a/2^{32} \rfloor (2^{32} \bmod n) + (a \bmod 2^{32}), then q=⌊s⌊m/231⌋/232⌋q = \lfloor s \lfloor m/2^{31} \rfloor / 2^{32} \rfloor with s=⌊t/2ν⌋s = \lfloor t/2^{\nu} \rfloor, and t−qnt - qntwo (2n2n, then nn)

With 32-bit words, aa is a two-word integer and, for ν≤32\nu \le 32, nn is a one-word modulus: these kernels are reductions of Barrett and Lemire reduction at that word size. The top32 kernel is the estimate of NMOD_RED from the top halves of aa and mm; the fold29 kernel is the step of NMOD_RED2_BOUNDED after a fold; the fold32 kernel folds as n_lll_mod_barrett does, where NMOD2_RED2 would reduce the high half and take a Möller–Granlund step. AVX-512 computes qnqn for ν≥33\nu \ge 33 with one vpmullq, AVX2 and NEON with two products of 32-bit halves (q<232q < 2^{32}). NEON has no kernel for ν≤5\nu \le 5, where the scalar code was faster.

Lemma 1. Let 33≤ν≤6333 \le \nu \le 63, 0≤a<2640 \le a < 2^{64} and q=⌊⌊a/232⌋m1/2ν−1⌋q = \lfloor \lfloor a/2^{32} \rfloor m_1 / 2^{\nu - 1} \rfloor. Then 0≤a−qn<2n0 \le a - qn < 2n for ν≥34\nu \ge 34, and <3n< 3n for ν=33\nu = 33.

Proof. Write a=a1232+a0a = a_1 2^{32} + a_0 with a0,a1<232a_0, a_1 < 2^{32}. From (2ν+31−n)/n≤m1≤2ν+31/n(2^{\nu + 31} - n)/n \le m_1 \le 2^{\nu + 31}/n,

an−232n−a12ν−1<a1m12ν−1≤a1232n≤an,\frac{a}{n} - \frac{2^{32}}{n} - \frac{a_1}{2^{\nu - 1}} < \frac{a_1 m_1}{2^{\nu - 1}} \le \frac{a_1 2^{32}}{n} \le \frac{a}{n},

so q≤a/nq \le a/n, and q>a/n−1−232/n−a1/2ν−1q > a/n - 1 - 2^{32}/n - a_1/2^{\nu - 1}. Both 232/n2^{32}/n and a1/2ν−1a_1/2^{\nu - 1} are below 233−ν2^{33 - \nu}, so a/n−q<1+234−νa/n - q < 1 + 2^{34 - \nu}: at most 2 for ν≥34\nu \ge 34 and 3 for ν=33\nu = 33, and a−qna - qn is below 2n2n, respectively 3n3n.

Lemma 2. Let 6≤ν≤326 \le \nu \le 32, tt and qq as in the table. Then t≡a(modn)t \equiv a \pmod n, t<2ν+30t < 2^{\nu + 30} and 0≤t−qn<2n0 \le t - qn < 2n.

Proof. The high part ⌊a/2ν+29⌋<235−ν\lfloor a/2^{\nu + 29} \rfloor < 2^{35 - \nu} times 2ν+29 mod n<2ν2^{\nu + 29} \bmod n < 2^{\nu} is below 235≤2ν+292^{35} \le 2^{\nu + 29}, and the low part is below 2ν+292^{\nu + 29}, so t<2ν+30t < 2^{\nu + 30}. This is the hypothesis of Theorem 4 of Barrett and Lemire reduction with 32-bit words, whose constant ⌊(2ν+31−1)/n⌋\lfloor (2^{\nu + 31} - 1)/n \rfloor is m1m_1 and whose estimate is qq. That theorem assumes ν≤31\nu \le 31, so that t−qnt - qn fits a 32-bit word; its proof of 0≤t−qn<2n0 \le t - qn < 2n only uses m1<232m_1 < 2^{32}, which also holds for ν=32\nu = 32, and the kernels compute t−qnt - qn in 64 bits.

For 2≤ν≤52 \le \nu \le 5, the fold is that of Two and three words with 2322^{32} in place of the word base: t<232nt < 2^{32} n, which exceeds the bound of Theorem 4 of Barrett and Lemire reduction. So s=⌊t/2ν⌋<232s = \lfloor t/2^{\nu} \rfloor < 2^{32}, and the argument of Lemma 1 with ⌊m/231⌋=⌊(2ν+32−1)/n⌋\lfloor m/2^{31} \rfloor = \lfloor (2^{\nu + 32} - 1)/n \rfloor gives 0≤t−qn<4n0 \le t - qn < 4n, hence the two corrections. This constant exceeds 2322^{32}, so the kernels compute s⌊m/231⌋s \lfloor m/2^{31} \rfloor as s232+s(⌊m/231⌋−232)s 2^{32} + s (\lfloor m/2^{31} \rfloor - 2^{32}). Every product in these kernels has both factors below 2322^{32}, except qnqn for ν≥33\nu \ge 33, which AVX2 and NEON split into two such products.

The full Barrett step of NMOD_RED, with the high half of a 64×6464 \times 64 product emulated from 32-bit products, was 1.3 to 1.6 times slower than these kernels.

Products of two vectors#

_nmod_vec_mul multiplies reduced entries. Its kernels:

ν\nuAVX-512AVX2NEON
2 to 32halflimbhalflimbhalflimb, hybrid from 16 entries
33 to 50ifma50 (with AVX512-IFMA), else fp50fp50fp50
51 to 62red2boundedscalar codescalar code
63, 64scalar codescalar codescalar code

The halflimb kernels, for ν≤32\nu \le 32, take a 32-bit Barrett step on the product p=ab<22νp = ab < 2^{2\nu}, which fits a word: q=⌊⌊p/2s⌋m1/2ν+31−s⌋q = \lfloor \lfloor p/2^s \rfloor m_1 / 2^{\nu + 31 - s} \rfloor with s=ν−2s = \nu - 2, or s=30s = 30 for ν=31\nu = 31 and s=32s = 32 for ν=32\nu = 32, so that ⌊p/2s⌋<232\lfloor p/2^s \rfloor < 2^{32}. For ν≤30\nu \le 30, p<2ν+30p < 2^{\nu + 30} and Theorem 4 of Barrett and Lemire reduction with 32-bit words, as in Lemma 2, gives p−qn<2np - qn < 2n. For ν=31,32\nu = 31, 32 the same argument gives p/n−q<1+2s/n+n2/2ν+31p/n - q < 1 + 2^s/n + n^2/2^{\nu + 31}, where the last two terms, convex in nn, stay below 3 on [2ν−1,2ν)[2^{\nu - 1}, 2^{\nu}): so p−qn<4np - qn < 4n, and the kernels correct by 2n2n, then by nn.

The fp50 kernels compute ab−qnab - qn in (−n,n)(-n, n) with qq the rounded quotient, as vec4d_mulmod (Multiplication), and add nn to a negative result. The ifma50 kernel splits p=p1252+p0p = p_1 2^{52} + p_0 with two 52-bit products, takes s=⌊p/2ν−2⌋<2ν+2s = \lfloor p/2^{\nu - 2} \rfloor < 2^{\nu + 2} and q=⌊s⌊m/213⌋/252⌋q = \lfloor s \lfloor m/2^{13} \rfloor / 2^{52} \rfloor (for ν=50\nu = 50, ⌊s⌊m/212⌋/253⌋\lfloor s \lfloor m/2^{12} \rfloor / 2^{53} \rfloor, so that the constant fits 52 bits), and computes p0−qnp_0 - qn modulo 2522^{52} as p0+q(252−n)p_0 + q(2^{52} - n), which is exact since p−qn<2n<252p - qn < 2n < 2^{52}: for ν=50\nu = 50 this is Theorem 4 of Barrett and Lemire reduction with 52-bit words, and for ν≤49\nu \le 49 its proof still applies, since p<22ν≤2ν+49p < 2^{2\nu} \le 2^{\nu + 49}, half the bound of that theorem, leaves room for the halved constant.

The red2bounded kernel, for 51≤ν≤6251 \le \nu \le 62, forms the full product and reduces it as NMOD_RED2_BOUNDED (Two words below a bound), whose estimate q~=⌊xm/265⌋\tilde q = \lfloor x m / 2^{65} \rfloor leaves a remainder below 2n2n; the high word of xmxm is computed from three 32-bit products and may be up to 2 too small, so the quotient may be one less and the remainder is below 3n3n: two corrections. Without AVX-512, this kernel, with its 64-bit products emulated, was slower than the scalar code.

Products by a scalar#

_nmod_vec_scalar_mul_nmod and _nmod_vec_scalar_addmul_nmod, for c∉{0,1,n−1}c \notin \{0, 1, n - 1\}, use Shoup's method in several radixes, with c^=⌊c264/n⌋\hat c = \lfloor c 2^{64}/n \rfloor computed once; _nmod_vec_scalar_addmul_nmod adds the result and corrects once more.

ν\nuAVX-512AVX2NEON
2 to 32shoup32shoup32shoup32
33 to 50shoup52 (with AVX512-IFMA), else fp50fp50fp50 (scalar_mul only)
51shoup52 (with AVX512-IFMA), else shoup64lazyscalar codescalar code
52 to 62shoup64lazyscalar codescalar code
63shoup64scalar codescalar code
64scalar codescalar codescalar code

In radix R=232R = 2^{32} or 2522^{52}, with ⌊c^/264−k⌋=⌊cR/n⌋\lfloor \hat c / 2^{64 - k} \rfloor = \lfloor cR/n \rfloor for R=2kR = 2^k, Lemma 1 of Multiplication by a fixed operand (Shoup) holds for entries x<Rx < R: the quotient q=⌊x⌊cR/n⌋/R⌋q = \lfloor x \lfloor cR/n \rfloor / R \rfloor is ⌊xc/n⌋\lfloor xc/n \rfloor or one less, and xc−qn<2nxc - qn < 2n. With 32-bit products (shoup32) the difference is computed exactly in 64 bits; with IFMA (shoup52) it is computed modulo 2522^{52} as xc+q(252−n)xc + q(2^{52} - n), which requires 2n<2522n < 2^{52}, hence ν≤51\nu \le 51. In shoup64lazy the high word of xc^x \hat c is computed from three 32-bit products and may be up to 2 too small, so xc−qn<4nxc - qn < 4n, below 2642^{64} for ν≤62\nu \le 62, and the kernel corrects by 2n2n, then by nn; in shoup64, for ν=63\nu = 63, it is exact.

The fp50 kernels are the doubles of Products of two vectors, with cc in place of the second entry; on AVX-512 without IFMA, they were faster than shoup64lazy at 33 to 50 bits. On AVX2, Shoup's method above 32 bits, with emulated 64-bit products, and on NEON, Shoup's method above 32 bits and the doubles for scalar_addmul, were slower than the scalar code.

Lazy variants#

_nmod_vec_reduce_lazy, _nmod_vec_mul_lazy, _nmod_vec_scalar_mul_nmod_lazy and _nmod_vec_scalar_addmul_nmod_lazy require n<2FLINT_BITS−2n < 2^{\mathtt{FLINT\_BITS} - 2}, that is n<262n < 2^{62} on the 64-bit machines that have these kernels, and run the kernels above without their last correction, so that their outputs are in [0,2n)[0, 2n). Before that correction, every kernel already has a value below 2n2n:

  • the remainders of top32 for ν≥34\nu \ge 34, fold29, halflimb for ν≤30\nu \le 30, ifma50, shoup32 and shoup52 are below 2n2n (Lemma 1, Lemma 2, Products of two vectors, Products by a scalar);
  • top32 at ν=33\nu = 33, fold32, halflimb at ν=31,32\nu = 31, 32, red2bounded and shoup64lazy correct by nn or 2n2n first, which leaves a value below 2n2n from a remainder below 3n3n or 4n4n;
  • the doubles kernels give z+nz + n in (0,2n)(0, 2n) instead of correcting z∈(−n,n)z \in (-n, n).

_nmod_vec_scalar_addmul_nmod_lazy also accepts entries of res in [0,2n)[0, 2n): the sum with a product in [0,2n)[0, 2n) is below 4n<2644n < 2^{64} and is corrected once, by 2n2n. On AVX2 this sum is corrected on 64-bit lanes, since 4n4n may exceed 2322^{32} at 31 bits; in the doubles kernels, z+s−n∈(−2n,2n)z + s - n \in (-2n, 2n) gets 2n2n added when negative. The entries of vec must be reduced, also when vec is res.

The doubles kernels of AVX-512 and AVX2 convert z+nz + n to an integer by adding 252+n2^{52} + n instead of 2522^{52} (the sum is an integer below 2532^{53}, so it is exact), one addition fewer than adding nn first; NEON converts with one instruction and adds nn.

The lazy functions run the exact code, whose outputs are reduced, for vectors of fewer than NMOD_VEC_SIMD_MIN_LEN entries, without SIMD, for n=1n = 1, and in the following cases:

FunctionAVX-512AVX2NEON
_nmod_vec_reduce_lazynonenoneν≤5\nu \le 5
_nmod_vec_mul_lazynone51≤ν≤6251 \le \nu \le 6251≤ν≤6251 \le \nu \le 62
_nmod_vec_scalar_mul_nmod_lazynone51≤ν≤6251 \le \nu \le 6251≤ν≤6251 \le \nu \le 62
_nmod_vec_scalar_addmul_nmod_lazynone51≤ν≤6251 \le \nu \le 6233≤ν≤6233 \le \nu \le 62

In these cases and without SIMD, from 8 entries and for n>232n > 2^{32}, the products by a scalar run instead Shoup's product without its last correction, which is in [0,2n)[0, 2n) (Lemma 1 of Multiplication by a fixed operand (Shoup)), and _nmod_vec_scalar_addmul_nmod_lazy adds res and corrects the sum, below 4n4n, by 2n2n: against the exact code, 1.05-1.66x at 8 to 12 entries and 1.06-1.53x from 16 entries (Nov 2026). For n<232n < 2^{32}, _nmod_vec_scalar_addmul_nmod_lazy runs the one-word loop of the exact code on res in [0,2n)[0, 2n) directly: res[i]+vec[i]c<2n+(n−1)2≤n2\mathtt{res}[i] + \mathtt{vec}[i] c < 2n + (n - 1)^2 \le n^2 fits one word.

_nmod_vec_scalar_mul_nmod_lazy also runs the exact code for c∈{0,1,n−1}c \in \{0, 1, n - 1\} (a zeroing, a copy or a negation), and _nmod_vec_scalar_addmul_nmod_lazy leaves res unchanged for c=0c = 0. Where _nmod_vec_scalar_addmul_nmod_lazy runs the exact code, it first reduces res.

Against the exact functions, on long vectors (Nov 2026): reduce 1.11-1.64x, mul 0.99-1.29x, scalar_mul 1.08-1.60x, scalar_addmul 1.04-1.35x, NEON 1.13-1.60x; shoup52 1.10-1.21x; the fold of nn into 2522^{52} 1.03-1.16x more for the doubles kernels. With the ifma50 kernel, _nmod_vec_mul_lazy gained nothing (0.87-1.10x).

Cite this page

The FLINT team, “SIMD kernels of the element-wise operations (nmod_vec.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_vec/simd.html (generated 2026-11-20).