The Gateway to Computer Science Excellence
+30 votes
5.7k 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 ______.
in Compiler Design by Veteran (105k points) | 5.7k views

5 Answers

+65 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
+3

why not 6 is answer here:evaluate x2 once

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

@Arjun sir  , @joshi_nitish

+1

your expression is not correct,

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

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

  

+6

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

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
+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)
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 ...
+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 (425k points)
+6 votes

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

by Junior (517 points)
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?

Please someone select this as best answer
0

Why is this answer incorrect? @Arjun

0
Please see the comments under best answer.
0

@Arjun 

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 votes
$x$($x^3$($x+4$)$+$$6$)$+5$

So total 1+3+1+1+1 = 7 operations
by Active (2.3k 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
50,647 questions
56,503 answers
195,502 comments
100,866 users