HornerForm¶

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description¶

HornerForm[poly]
    rewrites the univariate polynomial poly in nested (Horner) form,
    which evaluates in n multiplications and n additions instead of
    the naive 2n.
HornerForm[poly, var]
    uses var as the recursion variable for multivariate poly.
HornerForm[poly1 / poly2, vars1, vars2]
    puts a rational function in Horner form, nested with respect to
    vars1 in the numerator and vars2 in the denominator.

Examples¶

No verified examples yet for this function.

Implementation notes¶

Algorithm. builtin_hornerform (in src/poly/poly.c) rewrites a polynomial in nested multiply-add form. It first splits a rational input into numerator/denominator (scanning a top-level Times/Power for negative-exponent factors), then applies the recursive worker horner_form_rec to the numerator. That worker expr_expands, verifies the expression is a polynomial in the lead variable via PolynomialQ, obtains its dense coefficients with CoefficientList, and folds from the highest-degree coefficient downward using the Horner recurrence H ← c_i + v·H (with zero-coefficient short-circuits). For multiple variables it recurses on each coefficient with the remaining variable list, producing a nested Horner form.

Data structures. Reuses the CoefficientList array as the coefficient sequence; nested Times/Plus nodes (built via internal_times/internal_plus) form the output.

Attributes: Protected.

Implementation status¶

Stable — documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

References¶

W. G. Horner, "A new method of solving numerical equations of all orders, by continuous approximation", Phil. Trans. R. Soc. 1819.
Source: src/poly/poly.c
Specification: docs/spec/builtins/structural-manipulation.md

Notes & additional examples¶

Worked examples¶

In[1]:= HornerForm[1 + x + x^2 + x^3]
Out[1]= 1 + x (1 + x (1 + x))

In[2]:= HornerForm[a x^3 + b x^2 + c x + d, x]
Out[2]= d + x (c + x (b + a x))

Sparse and mixed-sign polynomials nest just as cleanly, skipping absent degrees:

In[1]:= HornerForm[3 x^4 - 2 x^3 + x - 7]
Out[1]= -7 + x (1 + x^2 (-2 + 3 x))

For multivariate input, choose the recursion variable; the other variables ride along inside the coefficients:

In[1]:= HornerForm[1 + 2 x + 3 x^2 y + 4 x y^2, x]
Out[1]= 1 + x (2 + 3 x y + 4 y^2)

A rational function can be nested numerator and denominator independently:

In[1]:= HornerForm[(x^2 + 1)/(x^3 - x + 2), x, x]
Out[1]= (1 + x^2)/(2 + x (-1 + x^2))

Notes¶

The nested (Horner) form evaluates a degree-n polynomial in n multiplications and n additions instead of the naive 2n. Pass an explicit variable as the second argument when the coefficients are themselves symbolic.