GATE2014-3-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

why not 6 is answer here:evaluate x² once

x((x²((x²)+4))+6)+5

@Arjun sir  , @joshi_nitish

---

your expression is not correct,

it is equal to -> x⁵ + 10x + 5

---

now check

---

to get 6 as answer you will require more than 1 temporary variavle, but in qsn it has mentioned tha only 1 temp variable is available.

---

i am not getting what is the meaning of using one temporary variable.

---

i think i get it 

x((x²((x²)+4))+6)+5  // x² is done 1st

then x((x²((x²)+4))+6)+5  now we lost x²

so need to do x² again

is it correct

  

---

see, if you even replace x=x², you have to first store that x in some temp, because x is used in outside last bracket x((x²((x²)+4))+6)+5 , 

the answer would be 6, if in place of last x, it would be x²

try to write in a form of 3 addr code, you will understand what is happening.

---

 Given value of X, using only one temporary variable

Hi @Anu007 ji, I think what ever you are saying looks correct to me. 

Answer could be 7 if nothing is given. But explicitly they are saying one temporary variable which means  we can store $X^2$ value and avoid recomputation.

ping @kenzou, @joshi_nitish

---

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.

---

This will be the code according to answer ...

1. T= x

2. T = T * T       [$x^{2}$]

3. T = T + 4     [$x^{2}$ + 4 ]

4. T = T *x       [$x^{3} + 4x$]

5. T = T * x      [$x^{4} + 4x^{2}$]

6. T = T + 6     [$x^{4} + 4x^{2}+ 6$]

7. T = T * x     [$x^{5} + 4x^{3}+ 6x$]

8. T = T + 5    [ $x^{5} + 4x^{3}+ 6x +5$ ]

No of operation = 7 

We hav to evaluate that expression using   single temporary variable     .....

---

@Anu007 Yes the answer should be 6. We can take a temporary variable and store 'x^2' in it, then this can be done in 6 operations only

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

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

This is wrong. (X²)²+2.2.X²+2² 

cannot be equal to (X²+2)²

It's 2.2.X^2 in middle term..not 2.2.X

---

@Divya

Here, a=X² , b=2, thus middle term is 2.2.X². If you see carefully, it is correct. I think you have overlooked the power 2.

---

Why is this not the accepted answer?

---

Got it.Thanks :)

---

Why this answer is so under rated?

Please someone select this as best answer

---

Why is this answer incorrect? @Arjun

---

Please see the comments under best answer.

---

@Arjun 

Yeah, I've read all the comments already. The selected answer assumes that $x, 4, 6, 5$ are given, and we are given a temporary variable $T$ to work with. Because after doing $x(x) +4$ the result will be in temporary variable and now to get $x(x(x) + 4)$ we definitely need to know $x$. So, there's no way that $x$ IS the temporary variable. 

Now, as pointed out in the comments, particularly one which describes the three address code for the selected answer, directly references $x$ in the 4th line.

This answer also, doesn't need to store $x^2$ in the variable cause it is being used only once, and $x$ is readily available, this answer seems correct. 

Correct me if I'm wrong. Sorry for ping. 

---

@ankitgupta.1729 @srestha 

---

@toxicdesire

Can we do square operation in single temporary variable?

---

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?

Answer 5

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

So total 1+3+1+1+1 = 7 operations