The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+29 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 ______.
in Compiler Design by Veteran (98.5k points) | 5.5k views

5 Answers

+62 votes
Best answer
$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$
by Loyal (8.1k points)
edited by

why not 6 is answer here:evaluate x2 once


@Arjun sir  , @joshi_nitish


your expression is not correct,

it is equal to -> x5 + 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((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



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.


 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 'x2' in it, then this can be done in 6 operations only

+20 votes

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.

by Boss (19.9k points)
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 ...
+9 votes

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

by Veteran (416k points)
+5 votes

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












Therefore - (* operator used) =3, (+ operator used) = 3 Total=6

by (479 points)

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



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.

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.


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. 



Can we do square operation in single temporary variable?

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


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 votes

So total 1+3+1+1+1 = 7 operations
by Active (2.2k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,841 questions
54,799 answers
80,664 users