1
$\begingroup$

Here is Wikipedia's explanation of Horner's Method:

Given the polynomial

$$ 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, \ldots, a_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x$, say $x_0$.

To accomplish this, we define a new sequence of constants as follows:

$$ \begin{align} b_n & := a_n \\ b_{n-1} & := a_{n-1} + b_n x_0 \\ & {}\ \ \vdots \\ b_0 & := a_0 + b_1 x_0. \end{align} $$

Then $b_0$ is the value of $p(x_0)$.

To see why this works, note that the polynomial can be written in the form

$$ p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). $$

Thus, by iteratively substituting the b_i into the expression,

$$ \begin{align} p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\ & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\ & {} \ \ \vdots \\ & = a_0 + x_0(b_1) \\ & = b_0. \end{align} $$

Question:

Is the point of this algorithm that we can now evaluate $p(x_0)$ without having to ever evaluate any of the values $x_0^2, \ldots, x_0^n$, and instead, we are able to just just iteratively compute $b_n$ through $b_0$, where by the time we eventually get to $b_0$ we are finally able to evaluate $p(x_0)$?

If this is the case, why is this useful? Why not just compute $p(x_0)$ the normal way?


EDIT: Is it true that using Horner's rule to compute a polynomial of degree $n$ takes running time from $\Theta(n^2)$ down to $\Theta(n)$?

$\endgroup$
  • 1
    $\begingroup$ You said it yourself. $\endgroup$ – Yuval Filmus Aug 28 '15 at 15:10
5
$\begingroup$

Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way.

Example:

You have the polynomial $ax^3 + bx^2 + cx + d$. Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * x, first parenthesis * x, second parenthesis * x)

It is important to remember that in floating point calculations results from these two methods (direct and Horner) will differ.

$\endgroup$
  • $\begingroup$ I would suggest something for future use: if you are happy with answer accept it, if not share your doubts in comment. $\endgroup$ – Evil Aug 28 '15 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.