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)f(x) with a specific algorithm. Horner's rule uses len−1\mathit{len} - 1 multiplications by xx. The rectangular version (rectangular splitting, [PS1973]) computes x,…,xmx, \ldots, x^m for m≈lenm \approx \sqrt{\mathit{len}}, evaluates the blocks of mm coefficients as dot products with these powers and combines the blocks by Horner's rule in xmx^m, so that only O(len)O(\sqrt{\mathit{len}}) multiplications are full products of ring elements; this pays off when the coefficients are cheaper than xx (small integers and a large xx, scalars and a matrix or polynomial argument). The modular version also computes the powers (xj)0,…,(xj)k−1(x^j)^0, \ldots, (x^j)^{k-1} with j≈k≈lenj \approx k \approx \sqrt{\mathit{len}} and evaluates everything with j+1j + 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-11-02).