FLINT3.7.0-dev
/

_gr_poly_evaluate_horner, gr_poly_evaluate_horner, _gr_poly_evaluate_rectangular, gr_poly_evaluate_rectangular, _gr_poly_evaluate_modular, gr_poly_evaluate_modular

Synopsis#include <flint/gr_poly.h>
int _gr_poly_evaluate_horner(gr_ptr res, gr_srcptr poly, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_poly_evaluate_horner(gr_ptr res, const gr_poly_t poly, gr_srcptr x, gr_ctx_t ctx)source
int _gr_poly_evaluate_rectangular(gr_ptr res, gr_srcptr poly, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_poly_evaluate_rectangular(gr_ptr res, const gr_poly_t poly, gr_srcptr x, gr_ctx_t ctx)source
int _gr_poly_evaluate_modular(gr_ptr res, gr_srcptr poly, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_poly_evaluate_modular(gr_ptr res, const gr_poly_t poly, gr_srcptr x, gr_ctx_t ctx)source

Set res to f(x) with a specific algorithm. Horner's rule uses \mathit{len} - 1 multiplications by x. The rectangular version (rectangular splitting, [PS1973]) computes x, \ldots, x^m for m \approx \sqrt{\mathit{len}}, evaluates the blocks of m coefficients as dot products with these powers and combines the blocks by Horner's rule in x^m, so that only O(\sqrt{\mathit{len}}) multiplications are full products of ring elements; this pays off when the coefficients are cheaper than x (small integers and a large x, scalars and a matrix or polynomial argument). The modular version also computes the powers (x^j)^0, \ldots, (x^j)^{k-1} with j \approx k \approx \sqrt{\mathit{len}} and evaluates everything with j + 1 dot products, which suits rings where dot products are much cheaper than separate multiplications (delayed modular reduction).

References#

  • [PS1973] M. S. Paterson and L. J. Stockmeyer, "On the number of nonscalar multiplications necessary to evaluate polynomials", SIAM J. Comput (1973)
Cite this page

The FLINT team, “_gr_poly_evaluate_horner, gr_poly_evaluate_horner, _gr_poly_evaluate_rectangular, gr_poly_evaluate_rectangular, _gr_poly_evaluate_modular, gr_poly_evaluate_modular (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_evaluate_horner.html (generated 2026-10-20).