60 votes 60 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 ______. Compiler Design gatecse-2014-set3 compiler-design numerical-answers normal code-optimization + – go_editor asked Sep 28, 2014 go_editor 19.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 121 votes 121 votes $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$ jayendra answered Jan 7, 2015 edited Nov 25, 2017 by kenzou jayendra comment Share Follow See all 19 Comments See all 19 19 Comments reply Anu007 commented Nov 14, 2017 i edited by Anu007 Nov 14, 2017 reply Follow Share why not 6 is answer here:evaluate x2 once x((x2((x2)+4))+6)+5 @Arjun sir , @joshi_nitish 4 votes 4 votes joshi_nitish commented Nov 14, 2017 reply Follow Share your expression is not correct, it is equal to -> x5 + 10x + 5 1 votes 1 votes Anu007 commented Nov 14, 2017 reply Follow Share now check 0 votes 0 votes joshi_nitish commented Nov 14, 2017 reply Follow Share 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. 1 votes 1 votes Anu007 commented Nov 14, 2017 reply Follow Share i am not getting what is the meaning of using one temporary variable. 0 votes 0 votes Anu007 commented Nov 14, 2017 reply Follow Share 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 8 votes 8 votes joshi_nitish commented Nov 14, 2017 reply Follow Share 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. 10 votes 10 votes Chhotu commented Jan 1, 2018 reply Follow Share 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 1 votes 1 votes prayas commented Jan 2, 2018 reply Follow Share 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 votes 0 votes Puja Mishra commented Jan 12, 2018 reply Follow Share 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 ..... 74 votes 74 votes vishal chugh commented Apr 15, 2018 reply Follow Share @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 votes 0 votes Ambuj Mishra commented Sep 13, 2019 i edited by Ambuj Mishra Sep 19, 2019 reply Follow Share 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 9 votes 9 votes jiminpark commented Dec 10, 2021 reply Follow Share @Ambuj Mishra, your answer seems correct ! Did you find yet, if anything is wrong? 0 votes 0 votes pradeep_reddy commented Dec 13, 2021 reply Follow Share Someone please confirm what is wrong with Ambuj Mishra’s comment? 0 votes 0 votes Abhrajyoti00 commented Dec 25, 2022 reply Follow Share @Deepak Poonia Sir, Can’t it be done in this way? $T = x*x \ [x^2]$ $T = T+2 \ [x^2+2]$ $T = T*T \ [x^4+4x^2+4]$ $T = T+2 \ [x^4+4x^2+6]$ $T= T*x \ [x^5+4x^3+6x]$ $T = T+5\ [x^5+4x^3+6x+5]$ Why is this wrong? I’m getting $6$ operations 0 votes 0 votes sk91 commented Jan 8, 2023 reply Follow Share @Abhrajyoti00 There are only two variables $x$ and $T$ to store values After your first statement, $T$ = $x^{4}$ and var $x$ does not change In second statement, var $T$ cant be disturbed. So, assuming, var $x$ has to store $2 * (x^{2} + 2)$ In third statement, you need value of $x$ for computing $x^{4}$ but now var $x$ has $2 * (x^{2} + 2)$ So, I dont think you can proceed from here without storing value of $x$ in var $x$ restoration will take extra operations 0 votes 0 votes Alekhyo Banerjee commented Jan 9, 2023 reply Follow Share @Abhrajyoti00 regarding your first line, I think it will beT ← xT ← T * x 0 votes 0 votes Abhrajyoti00 commented Jan 9, 2023 reply Follow Share @Alekhyo Banerjee Why? It is not mentioned in the question that “arithmetic operations have to be done after storing them somewhere”? They just asked min no. of arithmetic operations reqd using 1 temp variable. So why should I store $x$ first then do $x^2$? We do like this if they ask : “min register reqd. or if it’s explicitly mentioned that operations can only be performed in integer” 0 votes 0 votes Hira Thakur commented Jan 31 reply Follow Share is the answer will change if number of temp variable is $\geq1$. 0 votes 0 votes Please log in or register to add a comment.
25 votes 25 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. Gate Keeda answered Oct 28, 2014 Gate Keeda comment Share Follow See all 2 Comments See all 2 2 Comments reply prayas commented Jan 2, 2018 reply Follow Share 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. 1 votes 1 votes Puja Mishra commented Jan 12, 2018 reply Follow Share can u explain 2nd and 3rd line ??? Temporary value T is getting lost during that time ... 0 votes 0 votes Please log in or register to add a comment.
17 votes 17 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 Arjun answered Oct 28, 2014 Arjun comment Share Follow See 1 comment See all 1 1 comment reply SomeEarth commented Jan 13, 2021 reply Follow Share @Arjun sir, That means 3 multiplication for (x^5 part) and one multiplication for (6*x part) right? 3 addition was pretty easy. (that can be guessed intuitively) 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 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 Avik10 answered Mar 4, 2017 Avik10 comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments toxicdesire commented Jun 15, 2019 reply Follow Share If the selected answer can do it, this answer can do it too. So, yes. 0 votes 0 votes srestha commented Jun 17, 2019 reply Follow Share @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 0 votes rupesh17 commented Oct 18, 2020 reply Follow Share @srestha see comments to best answer giving 3 address code …..there at second step same thing has been done This will be the code according to answer ... 1. T= x 2. T = T * T 0 votes 0 votes Please log in or register to add a comment.