44 votes

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

87 votes

Best answer

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.

5

i think i get it

x((x^{2}((x^{2})+4))+6)+5 // x^{2} is done 1st

then x((x^{2}((x^{2})+4))+6)+5 now we lost x^{2}

so need to do x^{2} again

is it correct

7

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

the answer would be 6, if in place of last **x**, it would be **x ^{2}**

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 'x^{2' }in it, then this can be done in 6 operations only

22 votes

Multiplications, 3 Additions]

So answer is 7 arithmetic operations.

12 votes

^{5}+4x^{3}+6x+5 = x^{3}(x^{2}+4)+6x+5

x^{3} -> 3 multiply operations (also gives x^{2})

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

6 votes

P(X) = X^{5}+4X^{3}+6X+5

RHS

X(X^{4}+4X^{2}+6)+5

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

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

cannot be equal to (X^{2}+2)^{2}

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

0

@Divya

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

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.

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 multiplications & 3 additions.

4 + 3 = 7

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 multiplications & 3 additions.

4 + 3 = 7

0 votes

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.

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.