Tony
I am Tony, a Chinese guy. I'm trying to be an Artificial Intelligence researcher. My blogs can help me summarize what I have learned, and may bring some lights to others. I'm very happy to see your comments. Good luck!

Efficient Metholds for Evaluting Polynomials

•
•
•
•
•
•
•
•
•

Introduction

It had been said that the more basic the operations are, the more we can stand to gain by doing it efficiently. Addition and multiplication may be the most basic operations to us all, and so is their combination, the polynomials. Many functions, no matter how complecated they are, can be approximated by a polynomial. For instance: $\sin(x),x\in[-\pi,\pi]$ can be approximated by
$$0.987862x-0.155271x^3+0.00564312x^5 \tag{1}$$

their curves are like these:
1. $g(x)=0.987862x-0.155271x^3+0.00564312x^5$

2. $f(x)=\sin(x)$

3. $f(x)=\sin(x)$ and $g(x)=0.987862x-0.155271x^3+0.00564312x^5$

All figures above show how sophisticated polynomials are in approximation. However, How to get this polynomial is not the things we should concern in the class, and what we should worry about is how to comput the formula (1) more efficiently.
We, now, change our polynomial (1) to a general one which contains entries of all distict integer exponents:
$$P(x)=2x^4+3x^3-3x^2+5x-1\tag{2}$$
What we are going to do is to find the best way to evaluate polynomial (2) at $x=\frac{1}{2}$. Assuming that, the coefficients of the polynomial and the number $\frac{1}{2}$ are always stored in memory or even registors, which is to say that we will not take the transportation time into account.

Mearsure the effeciency of the operation

However, How to mearsure the effeciency of evaluting is a new problem coming to our faces, and I got two ways to solve this problem:
1. The first one is to count the ticks of the entire process, which is in the view of time. For instance, if our algorithm have taken 10 seconds, and the state-of-art algorithm have taken 11 seconds, our algorithm would be better.
2. The second is to count the total quantity of the operations of the algorithm, such as, if our algoritm have had 10 multiplications and 5 additions, while the state-of-art algorithm have had 11 multipilications and 5 additions, our algorithm would be better.

In this section, we will measure the effiecent of the algorithm through the second way, counting the quantity of the operations.

Evaluating a Polynomial

Now, we go back to our main problem of finding out the best way to evalute:
$$P(x)=2x^4+3x^3-3x^2+5x-1\tag{3}$$

Method 1

In a usual way, we will evaluat
\begin{aligned} P(\frac{1}{2})=&2\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\newline&+3\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\newline&-3\times \frac{1}{2}\times \frac{1}{2}\newline&+5\times \frac{1}{2}\newline &-1 \end{aligned}\tag{4}
There are $4+3+2+1=10$ multiplications and $1+1+1+1=4$ additions(the subtraction here is regarded as the same as addition).
Method one has 10 multiplications and 4 additions.

Method 2

Smart readers may have found that we have done ‘$\frac{1}{2}\times \frac{1}{2}$’ more times than necessary, while, some results can be stored in the memory, instead of computing them again and again. So the method becomes:
\begin{aligned} \frac{1}{2}\times\frac{1}{2}&=(\frac{1}{2})^2\newline \frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}&=(\frac{1}{2})^2\times\frac{1}{2}=(\frac{1}{2})^3\newline \frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}&=(\frac{1}{2})^3\times\frac{1}{2}=(\frac{1}{2})^4 \end{aligned}\tag{5}

That is to say $(\frac{1}{2})^2$ has one multiplication, and $(\frac{1}{2})^3$ has two multiplications, while the $(\frac{1}{2})^3$ has two multiplications as well. So there totally are $2+2+2+1=7$ mutiplications and 4 addtions(the subtraction here is regarded as the same as addition).
Method two has 7 multiplications and 4 additions.

Method 3(Nested Multiplication)

Rewrite the polynomial as:
\begin{aligned} P(x)&=-1+x(5-3x+3x^2+2x^3)\newline &=-1+x(5+x(-3+3x+2x^2))\newline &=-1+x(5+x(-3+x(3+2x)))\newline &=-1+x\times(5+x\times(-3+x\times(3+x\times 2))) \end{aligned}\tag{6}
When $x=\frac{1}{2}$, we evaluate the polynomial from the inside out:
1. $\frac{1}{2}\times 2$ , add $+3\to 4$
2. $\frac{1}{2}\times 4$ , add $-3\to -1$
3. $\frac{1}{2}\times (-1)$ , add $+5\to \frac{9}{2}$
4. $\frac{1}{2}\times \frac{9}{2}$ , add $-1\to \frac{5}{4}$

This method is called nested multiplication or Horner’s method, in which there are 4 multiplications and 4 additions. A general degree $d$ polynomial can be evaluated in $d$ multiplications and $d$ additions.

The example of polynomial evaluation is characteristic of the entire topic of computational methods for scientific computing. While the standard form for a polynomial $c_1+c_2x+c_3x^2+c_4x^3+c_5x^4$ can be written in nested form as:
$$c_1+x(c_2+x(c_3+x(c_4+x(c_5))))\tag{7}$$

Interpolation Calculations

In chapter 3 we will require the form：
$$c_1+(x-r_1)(c_2+(x-r_2)(c_3+(x-r_3)(c_4+(x-r_4)(c_5))))\tag{8}$$
where we call $r_1,r_2,r_3$ and $r_4$ the base points. when we set $r_1=r_2=r_3=r_4=0$, formula (8) is recovered to formula (7).

Conclusion

Polynomial can be evaluated in a very effiecent way through nested multiplication. But, what is more important for us in this subject are these:
1. Computers are very fast at doing very simple things.
2. It’s important to do even simple tasks as efficiently as possible.
3. The best way may not be the obvious way.

Reference

1. Sauer, T., Columbus, B., New, I., San, Y., Upper, F., River, S., … Tokyo, T. (n.d.). Numerical Analysis. Retrieved from http://www.pearsoned.com/legal/permissions.htm.

•
•
•
•
•
•
•
•
•
Share

Tony Tan

I am Tony, a Chinese guy. I'm trying to be an Artificial Intelligence researcher. My blogs can help me summarize what I have learned, and may bring some lights to others. I'm very happy to see your comments. Good luck!