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