Algorithms and Parallel Computing

9.5 DESIGN 1: USING HORNER’S RULE FOR BROADCAST INPUT AND PIPELINED OUTPUT

Suppose we want to evaluate the polynomial for a certain value of x:

(9.8)

We can rewrite the polynomial using Horner’s scheme as

(9.9)

Now the polynomial is recursively evaluated through the following steps:

1. Evaluate the innermost term y₀ = 2x + 4.

2. Evaluate the next innermost term y₁ = y₀ x + 5.

3. Evaluate the term y₂ = y₁x + 3.

4. Evaluate the term y₃ = y₂x + 9.

5. Evaluate p(x) to y₃.

Now we apply Horner’s’ scheme to Eq. 9.7 to obtain the recursive expression

(9.10)

The above equation can be written as

(9.11)

(9.12)

(9.13)

(9.14)

Based on the above iterative expression, task T (i) computes Y_i in Eq. 9.11 using one multiplication and one addition:

(9.15)

The output of ...