The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
4.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 ______.
asked in Compiler Design by Veteran (106k points) | 4.7k views

5 Answers

+55 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$
answered by Loyal (8.3k points)
edited by
+2

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

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

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

answered by Boss (19.7k 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 ...
+8 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

answered by Veteran (363k points)
+2 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

answered by (421 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
we can not  write  t =t*t ...this is main reason
0 votes

Temp variable T assigned with value x^3.

Now new expression

T*X*X + 4*T + 6*X + 5

Total 7 arithmetic operations.

answered by Active (1.6k points)
Answer:

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

42,609 questions
48,608 answers
155,775 comments
63,775 users