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

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

---

can someone help me out in finding how is this wrong then ??

 

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

RHS

X( $X^4$+4 $X^2$ +6)+5

X((($X^{2.2}$)+2.2.$X^2$+$2^2$)+2)+5

X({$X^2$+2}.{$X^2$+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

---

@Ambuj Mishra, your answer seems correct !

Did you find yet, if  anything is wrong?

---

Someone please confirm what is wrong with Ambuj Mishra’s comment?

---

@Deepak Poonia Sir, Can’t it be done in this way? 

1. $T = x*x \ [x^2]$
2. $T = T+2 \ [x^2+2]$
3. $T = T*T \ [x^4+4x^2+4]$
4. $T = T+2 \ [x^4+4x^2+6]$
5. $T= T*x \ [x^5+4x^3+6x]$
6. $T = T+5\ [x^5+4x^3+6x+5]$

Why is this wrong? I’m getting $6$ operations

---

@Abhrajyoti00

There are only two variables $x$ and $T$ to store values

After your first statement, $T$ = $x^{4}$ and var $x$ does not change

In second statement, var $T$ cant be disturbed. So, assuming, var $x$ has to store $2 * (x^{2} + 2)$

In third statement, you need value of $x$ for computing $x^{4}$ but now var $x$ has $2 * (x^{2} + 2)$

So, I dont think you can proceed from here without storing value of $x$ in var $x$

restoration will take extra operations

---

@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