FLINT3.7.0-dev
/

_gr_fmpz_poly_evaluate_horner, gr_fmpz_poly_evaluate_horner, _gr_fmpz_poly_evaluate_rectangular, gr_fmpz_poly_evaluate_rectangular, _gr_fmpz_poly_evaluate, gr_fmpz_poly_evaluate

Synopsis#include <flint/gr_generic.h>
int _gr_fmpz_poly_evaluate_horner(gr_ptr res, const fmpz * f, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_fmpz_poly_evaluate_horner(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)source
int _gr_fmpz_poly_evaluate_rectangular(gr_ptr res, const fmpz * f, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_fmpz_poly_evaluate_rectangular(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)source
int _gr_fmpz_poly_evaluate(gr_ptr res, const fmpz * f, slong len, gr_srcptr x, gr_ctx_t ctx)source
int gr_fmpz_poly_evaluate(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)source

Set res to f(x) for the integer polynomial f (as an fmpz array of length len, or an fmpz_poly_t): by Horner's rule, by rectangular splitting, or (_gr_fmpz_poly_evaluate) by Horner's rule for length at most 6 and rectangular splitting otherwise. Declared only if fmpz_poly.h is included first.

Rectangular splitting [PS1973] computes the powers x^2, \ldots, x^m with m \approx \sqrt{n} once and evaluates f as a polynomial in x^m whose coefficients are linear combinations of the precomputed powers with integer coefficients; this uses about 2\sqrt{n} multiplications in the ring instead of n, and the multiplications by the integer coefficients are cheap scalar operations (_gr_vec_dot_fmpz). It is preferable in rings where a multiplication is much more expensive than a multiplication by an integer, such as balls at high precision or matrices.

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_fmpz_poly_evaluate_horner, gr_fmpz_poly_evaluate_horner, _gr_fmpz_poly_evaluate_rectangular, gr_fmpz_poly_evaluate_rectangular, _gr_fmpz_poly_evaluate, gr_fmpz_poly_evaluate (gr_generic.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_generic/_gr_fmpz_poly_evaluate_horner.html (generated 2026-10-20).