FLINT3.7.0-dev

_nmod_red3_fold_can_skip_sub, _nmod_red3_precomp_init, _nmod_red3_precomp

Synopsis#include <flint/nmod.h>
int _nmod_red3_fold_can_skip_sub(ulong ymax, ulong b1, ulong b2, nmod_t mod)source
void _nmod_red3_precomp_init(nmod_red3_precomp_struct * P, ulong ymax, nmod_t mod)source
ulong _nmod_red3_precomp(ulong a_hi, ulong a_me, ulong a_lo, const nmod_red3_precomp_struct * P, nmod_t mod)source

_nmod_red3_fold_can_skip_sub returns whether Yb2+(B−1)(b1+1)<nBY b_2 + (B - 1)(b_1 + 1) < nB with YY = ymax, the exact condition for NMOD_RED3_FOLD_FULLWORD_NOSUB on inputs with ahi≤Ya_{hi} \le Y. _nmod_red3_precomp_init sets P for n≥2n \ge 2 and inputs with ahi≤a_{hi} \le ymax (pass UWORD_MAX if no bound is known), and _nmod_red3_precomp returns (ahiB2+ameB+alo) mod n(a_{hi} B^2 + a_{me} B + a_{lo}) \bmod n for such inputs: by n_lll_mod_barrett for n<2FLINT_BITS−1n < 2^{\mathtt{FLINT\_BITS} - 1}, and by one of the two folds above otherwise. In a loop, testing P->nosub before the loop and calling NMOD_RED3_FOLD_FULLWORD_NOSUB directly when it is set is faster with clang, which leaves the tests of _nmod_red3_precomp in the loop and then compiles the reductions with branches.

Cite this page

The FLINT team, “_nmod_red3_fold_can_skip_sub, _nmod_red3_precomp_init, _nmod_red3_precomp (nmod.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod/_nmod_red3_fold_can_skip_sub.html (generated 2026-11-20).