Let us continue exploring ways to evaluate polynomials, as described in Practice Problem 5.5. We can reduce
Question:
Let us continue exploring ways to evaluate polynomials, as described in Practice Problem 5.5. We can reduce the number of multiplications in evaluating a polynomial by applying Horner’s method, named after British mathematician William G. Horner (1786–1837). The idea is to repeatedly factor out the powers of x to get the following evaluation:
Using Horner’s method, we can implement polynomial evaluation using the following code:
A. For degree n, how many additions and how many multiplications does this code perform?
B. On our reference machine, with the arithmetic operations having the latencies shown in Figure 5.12, we measure the CPE for this function to be 8.00. Explain how this CPE arises based on the data dependencies formed between iterations due to the operations implementing line 7 of the function.
C. Explain how the function shown in Practice Problem 5.5 can run faster, even though it requires more operations.
Problem 5.5
Suppose we wish to write a function to evaluate a polynomial, where a polynomial of degree n is defined to have a set of coefficients a0, a1, a2, . . . , an. For a value x, we evaluate the polynomial by computing
This evaluation can be implemented by the following function, having as arguments an array of coefficients a, a value x, and the polynomial degree degree (the value n in Equation 5.2). In this function, we compute both the successive terms of the equation and the successive powers of x within a single loop:
Step by Step Answer:
Computer Systems A Programmers Perspective
ISBN: 9781292101767
3rd Global Edition
Authors: Randal E. Bryant, David R. O'Hallaron