GATE CS 2014 Set 3 Q11 — Local Optimization

To evaluate the polynomial $P(X) = X^5 + 4X^3 + 6X + 5$ using only one temporary variable $t$, we can restructure the polynomial to minimize the number of arithmetic operations (multiplications and additions).

We can rewrite $P(X)$ in the following nested form:

Now, let us write the step-by-step evaluation sequence using a single temporary variable $t$:

1. $t = X imes X$    (Multiplication 1: $t = X^2$)
2. $t = t + 4$    (Addition 1: $t = X^2 + 4$)
3. $t = t imes X$    (Multiplication 2: $t = X^3 + 4X$)
4. $t = t imes X$    (Multiplication 3: $t = X^4 + 4X^2$)
5. $t = t + 6$    (Addition 2: $t = X^4 + 4X^2 + 6$)
6. $t = t imes X$    (Multiplication 4: $t = X^5 + 4X^3 + 6X$)
7. $t = t + 5$    (Addition 3: $t = X^5 + 4X^3 + 6X + 5$)

Counting the operations:

• Number of multiplications = $4$
• Number of additions = $3$

Thus, the minimum number of arithmetic operations required is $4 + 3 = 7$.