FLINT3.7.0-dev
/

_arb_poly_evaluate_horner, arb_poly_evaluate_horner, _arb_poly_evaluate_rectangular, arb_poly_evaluate_rectangular, _arb_poly_evaluate, arb_poly_evaluate

Synopsis#include <flint/arb_poly.h>
void _arb_poly_evaluate_horner(arb_t y, arb_srcptr f, slong len, const arb_t x, slong prec)source
void arb_poly_evaluate_horner(arb_t y, const arb_poly_t f, const arb_t x, slong prec)source
void _arb_poly_evaluate_rectangular(arb_t y, arb_srcptr f, slong len, const arb_t x, slong prec)source
void arb_poly_evaluate_rectangular(arb_t y, const arb_poly_t f, const arb_t x, slong prec)source
void _arb_poly_evaluate(arb_t y, arb_srcptr f, slong len, const arb_t x, slong prec)source
void arb_poly_evaluate(arb_t y, const arb_poly_t f, const arb_t x, slong prec)source

Set y = f(x) using Horner's rule, rectangular splitting [PS1973], or an automatic choice. The underscore versions accept \mathit{len} = 0.

Rectangular splitting computes x^2, \ldots, x^m for m \approx \sqrt{\mathit{len}} and evaluates the inner polynomials as dot products, using about 2\sqrt{\mathit{len}} full multiplications and \mathit{len} multiplications by the (short) coefficients. The automatic choice uses it when \mathit{prec} \ge 1024, \mathit{len} \ge 5 + 20000 / \mathit{prec} and the coefficients have at most \mathit{prec}/2 bits, and Horner's rule otherwise. Horner's rule usually gives the tighter enclosure when x is a wide ball.

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, “_arb_poly_evaluate_horner, arb_poly_evaluate_horner, _arb_poly_evaluate_rectangular, arb_poly_evaluate_rectangular, _arb_poly_evaluate, arb_poly_evaluate (arb_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/arb_poly/_arb_poly_evaluate_horner.html (generated 2026-10-20).