# GATE2014-3-11

8.8k views
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 ______.

$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$

edited by
3

why not 6 is answer here:evaluate x2 once

x((x2((x2)+4))+6)+5

@Arjun sir  , @joshi_nitish

1

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

0
now check
0
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.
0
i am not getting what is the meaning of using one temporary variable.
5

i think i get it

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

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

so need to do x2 again

is it correct

7

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

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

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

1

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

0
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.
57

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     .....

0

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

0
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

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

0
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.
0
can u explain 2nd and 3rd line ??? Temporary value T is getting lost during that time ...

x5+4x3​+6x+5 = x3(x2+4)​+6x+5
x3 -> 3 multiply operations (also gives x2)

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

0
@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)

P(X) = X5+4X3+6X+5

RHS

X(X4+4X2+6)+5

X(((X2)2+2.2.X2+22)+2)+5

X((X2+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

0

This is wrong. (X2)2+2.2.X2+2

cannot be equal to (X2+2)2

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

0

@Divya

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

1
Why is this not the accepted answer?
0
Got it.Thanks :)
0
Why this answer is so under rated?

0

Why is this answer incorrect? @Arjun

0
1

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.

0
0

@toxicdesire

Can we do square operation in single temporary variable?

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

@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?

0
@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
1 vote
The minimum number of arithmetic operations required to evaluate
P(X)=x5+4x3+6x+5
=x(x4+4x2+6)+5
=x(x(x3+4x)+6)+5
=x(x(x(x2+4))+6)+5
=x(x(x(x(x)+4))+6)+5
4 + 3 = 7
$x$($x^3$($x+4$)$+$$6$)$+5$

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

edited
6 should also be an answer.

We are given X [a constant] and only one temporary variable to store data that are required later.

Because the purpose of temporary variables are to store information calculated using work variables for reuse later, any average programmer would interpret it as “only one temporary variable beside a work variable????”. And they would solve it like this.

(1)  temp = X;

(1)  temp  = temp*temp;       // +1 operation [$X^2$], this is stored for reuse

(2)  A = temp+4;       // +1 operation [$X^2+4$]

(2)  A = temp*(A);    // +1 operation [$X^2(X^2+4)$], and used here

(3)  A = A + 6;           // +1 operation [$X^2(X^2+4)+6$]

(4)  A = X*(A);          // +1 operation [$X(X^2(X^2+4)+6)$]

(5)  A = A+5;            // +1 operation [$X(X^2(X^2+4)+6)+5$]

6 arithmetic operations overall.

So in conclusion the question could have been more informative on the constraints.

## Related questions

1
15.7k views
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are $6$ and $6$ $8$ and $10$ $9$ and $12$ $4$ and $4$
2
6.3k views
Which of the following statements are CORRECT? Static allocation of all data areas by a compiler makes it impossible to implement recursion. Automatic garbage collection is essential to implement recursion. Dynamic allocation of activation records is essential to implement recursion. Both heap and stack are essential to ... . $1$ and $2$ only $2$ and $3$ only $3$ and $4$ only $1$ and $3$ only
3
4.9k views
Which one of the following is FALSE? A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. Available expression analysis can be used for common subexpression elimination. Live variable analysis can be used for dead code elimination. $x=4*5 \Rightarrow x=20$ is an example of common subexpression elimination.
There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $x*x=y*y=x*y*x*y=y*x*y*x=e$ where $e$ is the identity element. The maximum number of elements in such a group is ____.