FLINT3.7.0-dev
/

_nmod_poly_evaluate_nmod_horner, _nmod_poly_evaluate_nmod_rectangular

Synopsis#include <flint/nmod_poly.h>
ulong _nmod_poly_evaluate_nmod_horner(nn_srcptr poly, slong len, ulong c, nmod_t mod)source
ulong _nmod_poly_evaluate_nmod_rectangular(nn_srcptr poly, slong len, ulong c, nmod_t mod)source

Return poly(c)\mathit{poly}(c) by Horner's rule, and by rectangular splitting: with m=min⁡(⌊len⌋+1,1024)m = \min(\lfloor\sqrt{\mathit{len}}\rfloor + 1, 1024), the powers c,…,cmc, \ldots, c^m are computed once, each block of mm coefficients is evaluated by a dot product (see Computing dot products), and the blocks are combined by Horner's rule in cmc^m. The dot products accumulate without intermediate reductions, which makes rectangular splitting faster than Horner's rule for long polynomials although it does the same number of multiplications.

Cite this page

The FLINT team, “_nmod_poly_evaluate_nmod_horner, _nmod_poly_evaluate_nmod_rectangular (nmod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly/_nmod_poly_evaluate_nmod_horner.html (generated 2026-11-02).