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 a 0 , a 1 , a 2 , , a n For a value x, we evaluate the polynomial by computing This evaluation can be implemented by the following function, having as arguments an a...

Polynomial evaluation is a core technique for solving many pro ...

Suppose we wish to write a function to evaluate a polynomial, where a polynomial of degree n

Question:

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 a₀, a₁, a₂, . . . , a_n. 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:

1 2 3 4 5 6 7 8 9 10 11 double poly (double a[], double x, long degree) { } long i; double result = a [0];

A. For degree n, how many additions and how many multiplications does this code perform?

B. On our reference machine, with arithmetic operations having the latencies shown in Figure 5.12, we measure the CPE for this function to be 5.00. Explain how this CPE arises based on the data dependencies formed between iterations due to the operations implementing lines 7–8 of the function.

Figure 5.12