Evaluation Polynomials

PROBLEM
Compute the value of a given polynomial A.N*X**N+...+A.1*X+A.0 of degree N at a given point V.

ALGORITHM
A simple algorithm which avoids recomputation of the powers of X is known as Horner's rule. A degree N polynomial can be evaluated using only N-1 multiplications and N additions. This program assumes the array representation for polynomials.

 

IMPLEMENTATION
Unit: internal function
 
Global variables: vector A.0,A.1,...,A.N of coefficients from the set of real numbers
 
Parameters: a positive integer N - the degree of the polynomial, real number V - a given point
 
Returns: Evaluating the polynomial A. at the given point V
 

HORNER: procedure expose A.
parse arg N, V
P = A.N
do J = N - 1 to 0 by -1
  P = P * V + A.J
end
return P

 

EXAMPLE
The value of a given polynomial 5*X**3+4*X-10 of degree N=3 at a given point V=8 is 2582. See the following fragment of program:

N = 3
A. = 0
A.3 = 5; A.1 = 4; A.0 = -10
V = 8
say HORNER(N, V)
exit
...

 

CONNECTIONS

Literature
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984


Cover Contents Index Main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic