1) The problem
Given a polynomial
\[
p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,
\]
evaluate \(p(x_0)\) for a specific input value \(x_0\).
2) Horner’s method (nested form)
Rewrite the polynomial by factoring out \(x\) repeatedly:
\[
p(x)=(((a_n x + a_{n-1})x + a_{n-2})x + \cdots + a_1)x + a_0.
\]
Then evaluation at \(x=x_0\) becomes a simple loop: “multiply by \(x_0\), add the next coefficient.”
A degree-\(n\) polynomial needs exactly \(n\) multiplications and \(n\) additions.
3) Horner / synthetic division table
Define the Horner sequence \(b_k\) by:
\[
b_n=a_n,\qquad
b_k=a_k + x_0\,b_{k+1}\quad (k=n-1,n-2,\dots,0).
\]
- \(b_0 = p(x_0)\).
-
If you divide \(p(x)\) by \((x-x_0)\), the quotient is
\[
q(x)=b_nx^{n-1}+b_{n-1}x^{n-2}+\cdots+b_2x+b_1,
\]
and the remainder is \(r=b_0\).
4) Derivative bonus (extended Horner)
You can compute \(p'(x_0)\) with a second nested pass using the already-computed \(b_k\):
\[
c_n=b_n,\qquad
c_k=b_k + x_0\,c_{k+1}\quad (k=n-1,n-2,\dots,1),
\qquad p'(x_0)=c_1.
\]
This avoids explicitly differentiating the polynomial symbolically and still costs only \(O(n)\) time.
5) Root bracketing hint (why Horner is used in solvers)
Many root-finding methods repeatedly evaluate \(p(x)\). Horner makes these evaluations fast.
A simple sign-change test says: if \(p(a)\,p(b) < 0\), then there is at least one real root in \((a,b)\).
Tip: For polynomial division and factoring workflows, Horner’s method is the “engine” behind synthetic division.
If you need a full quotient/remainder for a divisor of higher degree, use the Polynomial Division Tool.
