{"id":26114,"date":"2017-10-26T19:52:19","date_gmt":"2017-10-26T14:22:19","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26114"},"modified":"2017-10-26T19:52:19","modified_gmt":"2017-10-26T14:22:19","slug":"c-programming-horners-method-polynomial-evaluation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-horners-method-polynomial-evaluation\/","title":{"rendered":"C Programming &#8211; Horner\u2019s Method for Polynomial Evaluation"},"content":{"rendered":"<p>Given a polynomial of the form c<sub>n<\/sub>x<sup>n<\/sup> + c<sub>n-1<\/sub>x<sup>n-1<\/sup> + c<sub>n-2<\/sub>x<sup>n-2<\/sup> + \u2026 + c<sub>1<\/sub>x + c<sub>0<\/sub> and a value of x, <span id=\"more-129372\"><\/span>find the value of polynomial for a given value of x. Here c<sub>n<\/sub>, c<sub>n-1<\/sub>, .. are integers (may be negative) and n is a positive integer.<\/p>\n<p>Input is in the form of an array say <em>poly[]<\/em> where poly[0] represents coefficient for x<sup>n<\/sup> and poly[1] represents coefficient for x<sup>n-1<\/sup> and so on.<\/p>\n<p><strong>Examples:<\/strong><\/p>\n<pre>\/\/ Evaluate value of 2x<sup>3<\/sup> - 6x<sup>2<\/sup> + 2x - 1 for x = 3\r\nInput: poly[] = {2, -6, 2, -1}, x = 3\r\nOutput: 5\r\n\r\n\/\/ Evaluate value of 2x<sup>3<\/sup> + 3x + 1 for x = 2\r\nInput: poly[] = {2, 0, 3, 1}, x = 2\r\nOutput: 23<\/pre>\n<p>A naive way to evaluate a polynomial is to one by one evaluate all terms. First calculate xn, multiply the value with cn, repeat the same steps for other terms and return the sum. Time complexity of this approach is O(n2) if we use a simple loop for evaluation of xn. Time complexity can be improved to O(nLogn) if we use O(Logn) approach for evaluation of xn.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>Horner\u2019s method can be used to evaluate polynomial in O(n) time. To understand the method, let us consider the example of 2&#215;3 \u2013 6&#215;2 + 2x \u2013 1. The polynomial can be evaluated as ((2x \u2013 6)x + 2)x \u2013 1. The idea is to initialize result as coefficient of xn which is 2 in this case, repeatedly multiply result with x and add next coefficient to result. Finally return result.<\/p>\n<p>Following is C++ implementation of Horner\u2019s Method.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C Program<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">#include &lt;iostream&gt;<br\/>using namespace std;<br\/> <br\/>\/\/ returns value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]<br\/>int horner(int poly[], int n, int x)<br\/>{<br\/>    int result = poly[0];  \/\/ Initialize result<br\/> <br\/>    \/\/ Evaluate value of polynomial using Horner&#039;s method<br\/>    for (int i=1; i&lt;n; i++)<br\/>        result = result*x + poly[i];<br\/> <br\/>    return result;<br\/>}<br\/> <br\/>\/\/ Driver program to test above function.<br\/>int main()<br\/>{<br\/>    \/\/ Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3<br\/>    int poly[] = {2, -6, 2, -1};<br\/>    int x = 3;<br\/>    int n = sizeof(poly)\/sizeof(poly[0]);<br\/>    cout &lt;&lt; &quot;Value of polynomial is &quot; &lt;&lt; horner(poly, n, x);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>Value of polynomial is 5<\/pre>\n<p>Time Complexity: O(n)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C Programming Horner\u2019s Method for Polynomial Evaluation &#8211; Mathematical Algorithms &#8211; Input is in form of array say poly[] where poly[0] represent coefficient<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1,74058],"tags":[77003,76993,77009,77015,77000,77001,76991,77002,75517,77023,76992,76994,77034,76995,76999,77013,77033,76996,77026,77008,77035,77029,77018,77030,77032,77036,77012,77014,10131,76997,77005,77004,77025,77007,77016,77021,77028,76990,76414,77027,77006,77019,77020,76998,77011,77022,77031,77010,77024,77017],"class_list":["post-26114","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-mathematical-algorithms","tag-algorithm-and-flowchart-for-bubble-sort-in-c","tag-algorithm-and-flowchart-for-palindrome-number","tag-bisection-method-example","tag-bisection-method-in-c","tag-bisection-method-solved-examples","tag-bisection-method-solved-examples-pdf","tag-c-language-lab-manual","tag-c-poly","tag-c-program-for-student-details-using-structure","tag-c-program-for-taylor-series","tag-c-program-to-convert-decimal-to-binary","tag-c-program-to-find-sine-series","tag-c-programming-flowchart-pdf","tag-c-programming-lab-manual-pdf","tag-c-programs-for-practice","tag-c4learn-c","tag-computer-programming-lab-manual","tag-dynamic-array-in-c","tag-evaluate-the-polynomial-calculator","tag-flowchart-for-bubble-sort-program-in-c","tag-flowchart-for-functions-in-c-programming","tag-fortran-call","tag-fortran-code-example","tag-fortran-example","tag-fundamentals-of-computers-by-reema-thareja","tag-fval","tag-honor-5x","tag-honor-x","tag-honor4x","tag-methods-of-evaluation","tag-numerical-methods-bisection-method","tag-numerical-methods-pdf","tag-numerical-methods-problems-and-solutions","tag-polynomial","tag-polynomial-addition-using-array-in-c","tag-polynomial-root-calculator","tag-polynomials-in-python","tag-program-of-bisection-method-in-c-language","tag-programming-examples","tag-reema-thareja-computer-fundamentals-and-programming-in-c","tag-reema-thareja-programming-in-c-pdf-free-download","tag-root-finder","tag-roots-of-equation-calculator","tag-secant-method-example-solved","tag-secant-method-formula","tag-square-root-finder","tag-subroutine-fortran","tag-synthetic-division-examples","tag-taylor-series-in-c-programming","tag-tricky-c-programs"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26114","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26114"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26114\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}