Horner's method
Polynomial evaluation and long division

Given the polynomial p (x) = ∑ i = 0 n a i x i = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x n, {\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},} where a 0, …, a n {\displaystyle a_{0},\ldots,a_{n}} are constant coefficients, the problem is to evaluate the polynomial at a specific value x 0 {\displaystyle x_{0}} of x. {\displaystyle x.}

For this, a new sequence of constants is defined recursively as follows:

Then b 0 {\displaystyle b_{0}} is the value of p (x 0) {\displaystyle p(x_{0})}.

To see why this works, the polynomial can be written in the form p (x) = a 0 + x (a 1 + x (a 2 + x (a 3 + ⋯ + x (a n − 1 + x a n) ⋯))). {\displaystyle p(x)=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big)}{\Big)}{\bigg)}\.}

Thus, by iteratively substituting the b i {\displaystyle b_{i}} into the expression, p (x 0) = a 0 + x 0 (a 1 + x 0 (a 2 + ⋯ + x 0 (a n − 1 + b n x 0) ⋯)) = a 0 + x 0 (a 1 + x 0 (a 2 + ⋯ + x 0 b n − 1)) ⋮ = a 0 + x 0 b 1 = b 0. {\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big)}{\Big)}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big)}{\Big)}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}}

Now, it can be proven that;

This expression constitutes Horner's practical application, as it offers a very quick way of determining the outcome of; p (x) / (x − x 0) {\displaystyle p(x)/(x-x_{0})} with b 0 {\displaystyle b_{0}} (which is equal to p (x 0) {\displaystyle p(x_{0})}) being the division's remainder, as is demonstrated by the examples below. If x 0 {\displaystyle x_{0}} is a root of p (x) {\displaystyle p(x)}, then b 0 = 0 {\displaystyle b_{0}=0} (meaning the remainder is 0 {\displaystyle 0}), which means you can factor p (x) {\displaystyle p(x)} as x − x 0 {\displaystyle x-x_{0}}.

To finding the consecutive b {\displaystyle b} -values, you start with determining b n {\displaystyle b_{n}}, which is simply equal to a n {\displaystyle a_{n}}. Then you then work recursively using the formula: b n − 1 = a n − 1 + b n x 0 {\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0}} till you arrive at b 0 {\displaystyle b_{0}}.
punctuation:no_comma, keywords:letter_frequency