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)y = f(x) using Horner's rule, rectangular splitting [PS1973], or an automatic choice. The underscore versions accept len=0\mathit{len} = 0.

Rectangular splitting computes x2,…,xmx^2, \ldots, x^m for m≈lenm \approx \sqrt{\mathit{len}} and evaluates the inner polynomials as dot products, using about 2len2\sqrt{\mathit{len}} full multiplications and len\mathit{len} multiplications by the (short) coefficients. The automatic choice uses it when prec≥1024\mathit{prec} \ge 1024, len≥5+20000/prec\mathit{len} \ge 5 + 20000 / \mathit{prec} and the coefficients have at most prec/2\mathit{prec}/2 bits, and Horner's rule otherwise. Horner's rule usually gives the tighter enclosure when xx 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-11-02).