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 Show 16 previous comments 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 Regina Phalange commented Mar 30, 2017 reply Follow Share This is wrong. (X2)2+2.2.X2+22 cannot be equal to (X2+2)2 It's 2.2.X^2 in middle term..not 2.2.X 0 votes 0 votes Avik10 commented Mar 31, 2017 reply Follow Share @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. 0 votes 0 votes Sanchita Ghosh commented May 21, 2017 reply Follow Share Why is this not the accepted answer? 1 votes 1 votes Regina Phalange commented Nov 2, 2017 reply Follow Share Got it.Thanks :) 0 votes 0 votes soumayan bandhu commented Jan 27, 2019 reply Follow Share Why this answer is so under rated? Please someone select this as best answer 0 votes 0 votes toxicdesire commented Jun 13, 2019 i edited by toxicdesire Jun 13, 2019 reply Follow Share Why is this answer incorrect? @Arjun 0 votes 0 votes Arjun commented Jun 13, 2019 reply Follow Share Please see the comments under best answer. 0 votes 0 votes toxicdesire commented Jun 13, 2019 i reshown by toxicdesire Jun 15, 2019 reply Follow Share @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. 1 votes 1 votes toxicdesire commented Jun 15, 2019 reply Follow Share @ankitgupta.1729 @srestha 0 votes 0 votes srestha commented Jun 15, 2019 reply Follow Share @toxicdesire Can we do square operation in single temporary variable? 0 votes 0 votes 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.