Evaluation of a polynomial

Computer Science Level 3

A polynomial of degree n n is a function of the form p ( x ) = c 0 + c 1 ⋅ x + c 2 ⋅ x 2 + ⋯ + c n ⋅ x n = ∑ k = 0 n c k x k , p(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + \dots + c_n \cdot x^n = \sum_{k = 0}^n c_k x^k, where c k c_k are the coefficients of the polynomial. Therefore, the polynominal can be represented as an array p = [ c 0 , c 1 , … , c n ] p = [c_0, c_1, \dots, c_n] . Our task is to program a function evaluate(p,x) that has as input the array p p and the number x x and returns the function value y = p ( x ) y = p (x) at the position x . x. 

1
2
3
 
def evaluate(p,x):
    # calculate the function value y = p(x)
    return y

Suppose you have implemented the function evaluate(p, x) as efficiently as possible.

How does the runtime of a function evaluation depend on the degree n n of the polynomial?

The runtime is essentially proportional to the number of multiplications that must be executed at the function call.

O ( n 2 ) \mathcal{O}(n^2) O ( n ) \mathcal{O}(n) O ( n ) \mathcal{O}(\sqrt{n}) O ( n log ⁡ n ) \mathcal{O}(n \log n)

Markus Michelmann by Markus Michelmann , 35, Germany

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Markus Michelmann
May 15, 2018

The evaluation of a polynomial is particularly efficient with the Horner method. We rewrite the polynomial a bit by factorising all instances of x x , so that no exponents appear in the expression: p ( x ) = c 0 + x ⋅ ( c 1 + x ⋅ ( c 2 + x ⋅ ( … ( c n − 1 + x ⋅ c n ) ) … ) ) p(x) = c_0 + x \cdot (c_1 + x \cdot(c_2 + x \cdot(\dots (c_{n-1} + x \cdot c_n ) )\dots)) The polynomial can now be evaluated by calculating the brackets from the inside to the outside. The intermediate results are then b 0 = c n b 1 = c n − 1 + x ⋅ b 0 b 2 = c n − 2 + x ⋅ b 1 ⋮ ⋮ b k = c n − k + x ⋅ b k − 1 ⋮ ⋮ b n = c 0 + x ⋅ b n − 1 \begin{aligned} b_0 &= c_n \\ b_1 &= c_{n-1} + x \cdot b_0 \\ b_2 &= c_{n-2} + x \cdot b_1 \\ \vdots & \qquad \vdots \\ b_k &= c_{n - k} + x \cdot b_{k-1}\\ \vdots & \qquad \vdots \\ b_n &= c_0 + x \cdot b_{n-1} \end{aligned} with the final result p ( x ) = b n p (x) = b_n . In each line (except for the first one) exactly one multiplication is executed, so that there is a total of n n multiplications. However, one cannot perform the algorithm with much fewer multiplications, since the calculation of all mononomes x k x ^ k already requires n − 1 n -1 multiplications. The runtime therefore scales with O ( n ) \mathcal {O} (n) .

Corresponding program example in Python: 

1
2
3
4
5
 
def evaluate(p, x):
  y = 0
  for c in reversed(p):
    y = y*x + c
  return y

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Great solution! When I imagined the evaluate program, I used recursion: 

def evaluate(p, x):
    if len(p) == 0: return 0
    return p[0] + x * evaluate(p[1:], x)

Brian Reinhart - 3 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...