Analysis of Algorithms : An Active Learning Approach

108 NUMERIC ALGORITHMS

The standard evaluation algorithm is very straightforward:

Evaluate( x )

x the value to use for evaluation of the polynomial

result = a[0] + a[1]*x

xPower = x

for i = 2 to n do

xPower = xPower * x

result = result + a[i]*xPower

end for

return result

This algorithm is very clear and its analysis is obvious. The for loop has two

multiplications and is done N 
 1 times. There is one multiplication done

before the loop, giving a total of 2N
 1 multiplications. There is one addition

done inside the loop and one done before it, giving N additions.

■ 4.1.1 Horner’s Method

Horner’s method gives a better way to do this evaluation without making the

process very complex. This method is based on recognizing that the polyno-

mial equation can be factored into the following form:

(4.2)

The reader should be able to easily see that this calculates the same value as

Equation 4.1. This can be expressed in algorithmic form as

HornersMethod( x )

x the value to use for evaluation of the polynomial

result = a[n]

for i = n - 1 down to 0 do

result = result * x

result = result + a[i]

end for

return result

We see that the loop is done N times and that there is one addition and one

multiplication done in the loop. This means that there are N multiplications

andN additions done by Horner’s method. This method saves almost half of

the multiplications done by the standard algorithm.

■ 4.1.2 Preprocessed Coefficients

It is possible to do even better than this by preprocessing the coefficients. The

basic idea here is that it is possible to express a polynomial as a factorization

px()= (){}...[]()anxa+ n–1 *xa+ n–2 *x++... a 2 *xa+ 1 *xa+ 0