5.3k 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
+2

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

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

+5

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

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

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

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?

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

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

1
2