GATE CSE 2014 Set 3 | Question: 11

Question

The minimum number of arithmetic operations required to evaluate the polynomial $P(X) = X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is ______.

Answer 1

$P(X) = x^5 + 4x^3 + 6x + 5$

$=x(x^4 + 4x^2 + 6) +5$

$=x( x ( x^3 + 4x) + 6) + 5$

$=x( x ( x (x^2 + 4)) + 6) + 5$

$=x( x ( x (x(x) + 4)) + 6) + 5$

mul = pair of brackets $4$
add = num of signs $3$
total $7$

Comments

@Abhrajyoti00    regarding your first line, I think it will be

T ← x

T ← T * x

---

@Alekhyo Banerjee Why? It is not mentioned in the question that “arithmetic operations have to be done after storing them somewhere”?

They just asked min no. of arithmetic operations reqd using 1 temp variable. So why should I store $x$ first then do $x^2$? We do like this if they ask : “min register reqd. or if it’s explicitly mentioned that operations can only be performed in integer”

---

is the answer will change if number of temp variable is $\geq1$.

Answer 2

In the above 8 steps of evaluation, the total number of arithmetic operations required are 7 [4
Multiplications, 3 Additions]
So answer is 7 arithmetic operations.

Comments

If one could store in memory, it doesn't make sense to mention one temporary variable.Storing in memory is equivalent to having infinite temporaries.One could get answer 6 if storing in memory is allowed.

---

can u explain 2nd and 3rd line ??? Temporary value T is getting lost during that time ...

Answer 3

x⁵+4x³​+6x+5 = x³(x²+4)​+6x+5
x³ -> 3 multiply operations (also gives x²)

So, Totally we need 3 + 1 multiplications and 3 additions = 7 operations

Comments

@Arjun sir,

That means 3 multiplication for (x^5 part) and one multiplication for (6*x part) right?

3 addition was pretty easy. (that can be guessed intuitively)

Answer 4

P(X) = X⁵+4X³+6X+5

RHS

X(X⁴+4X²+6)+5

X(((X²)²+2.2.X²+2²)+2)+5

X((X²+2)²+2)+5

Now:

T=X*X

T=T+2

T=T*T

T=T+2

T=T*X

T=T+5

Therefore - (* operator used) =3, (+ operator used) = 3 Total=6

Comments

If the selected answer can do it, this answer can do it too. So, yes.

---

@toxicdesire

It is not possible.

because, I thought like this,can we do one register value multiplied with same register value and stored in same register. Is it possible?

Where selected ans done it?

---

@srestha see comments to best answer giving 3 address code …..there at second step same thing has been done

This will be the code according to answer ...

1. T= x

2. T = T * T