Skip to content

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 (5)

Every input below was run against the current Mathilda build and its output recorded.

Applications (5)

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))

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

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

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

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.

References

Notes & additional examples

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.