{"id":26203,"date":"2017-10-26T20:25:37","date_gmt":"2017-10-26T14:55:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26203"},"modified":"2017-10-26T20:25:37","modified_gmt":"2017-10-26T14:55:37","slug":"c-programming-multiply-two-polynomials","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-multiply-two-polynomials\/","title":{"rendered":"C++ Programming &#8211; Multiply two polynomials"},"content":{"rendered":"<p>Given two polynomials represented by two arrays, write a function that multiplies given two polynomials.<span id=\"more-132532\"><\/span><\/p>\n<p>Example:<\/p>\n<pre>Input:  A[] = {5, 0, 10, 6} \r\n        B[] = {1, 2, 4} \r\nOutput: prod[] = {5, 10, 30, 26, 52, 24}\r\n\r\nThe first input array represents \"5 + 0x^1 + 10x^2 + 6x^3\"\r\nThe second array represents \"1 + 2x^1 + 4x^2\"<\/pre>\n<p>A simple solution is to one by one consider every term of first polynomial and multiply it with every term of second polynomial. Following is algorithm of this simple method.<\/p>\n<pre><strong>multiply(A[0..m-1], B[0..n01])<\/strong>\r\n1) Create a product array prod[] of size m+n-1.\r\n2) Initialize all entries in prod[] as 0.\r\n3) Travers array A[] and do following for every element A[i]\r\n...(3.a) Traverse array B[] and do following for every element B[j]\r\n          prod[i+j] = prod[i+j] + A[i] * B[j]\r\n4) Return prod[].<\/pre>\n[ad type=\u201dbanner\u201d]\n<p>The following is C++ implementation of above algorithm.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Simple%20C%2B%2B%20program%20to%20multiply%20two%20polynomials%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%5B%5D%20represents%20coefficients%20of%20first%20polynomial%0A%2F%2F%20B%5B%5D%20represents%20coefficients%20of%20second%20polynomial%0A%2F%2F%20m%20and%20n%20are%20sizes%20of%20A%5B%5D%20and%20B%5B%5D%20respectively%0Aint%20*multiply(int%20A%5B%5D%2C%20int%20B%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20int%20*prod%20%3D%20new%20int%5Bm%2Bn-1%5D%3B%0A%20%0A%20%20%20%2F%2F%20Initialize%20the%20porduct%20polynomial%0A%20%20%20for%20(int%20i%20%3D%200%3B%20i%3Cm%2Bn-1%3B%20i%2B%2B)%0A%20%20%20%20%20prod%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%2F%2F%20Multiply%20two%20polynomials%20term%20by%20term%0A%20%0A%20%20%20%2F%2F%20Take%20ever%20term%20of%20first%20polynomial%0A%20%20%20for%20(int%20i%3D0%3B%20i%3Cm%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%2F%2F%20Multiply%20the%20current%20term%20of%20first%20polynomial%0A%20%20%20%20%20%2F%2F%20with%20every%20term%20of%20second%20polynomial.%0A%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3Cn%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20prod%5Bi%2Bj%5D%20%2B%3D%20A%5Bi%5D*B%5Bj%5D%3B%0A%20%20%20%7D%0A%20%0A%20%20%20return%20prod%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20polynomial%0Avoid%20printPoly(int%20poly%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20cout%20%3C%3C%20poly%5Bi%5D%3B%0A%20%20%20%20%20%20%20if%20(i%20!%3D%200)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22x%5E%22%20%3C%3C%20i%20%3B%0A%20%20%20%20%20%20%20if%20(i%20!%3D%20n-1)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20%22%20%2B%20%22%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20The%20following%20array%20represents%20polynomial%205%20%2B%2010x%5E2%20%2B%206x%5E3%0A%20%20%20%20int%20A%5B%5D%20%3D%20%7B5%2C%200%2C%2010%2C%206%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20The%20following%20array%20represents%20polynomial%201%20%2B%202x%20%2B%204x%5E2%0A%20%20%20%20int%20B%5B%5D%20%3D%20%7B1%2C%202%2C%204%7D%3B%0A%20%20%20%20int%20m%20%3D%20sizeof(A)%2Fsizeof(A%5B0%5D)%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(B)%2Fsizeof(B%5B0%5D)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22First%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(A%2C%20m)%3B%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSecond%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(B%2C%20n)%3B%0A%20%0A%20%20%20%20int%20*prod%20%3D%20multiply(A%2C%20B%2C%20m%2C%20n)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnProduct%20polynomial%20is%20%5Cn%22%3B%0A%20%20%20%20printPoly(prod%2C%20m%2Bn-1)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output<\/p>\n<p>First polynomial is<br \/>\n5 + 0x^1 + 10x^2 + 6x^3<br \/>\nSecond polynomial is<br \/>\n1 + 2x^1 + 4x^2<br \/>\nProduct polynomial is<br \/>\n5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5<br \/>\nTime complexity of the above solution is O(mn). If size of two polynomials same, then time complexity is O(n2).<\/p>\n<p>Can we do better?<br \/>\nThere are methods to do multiplication faster than O(n2) time. These methods are mainly based on divide and conquer. Following is one simple method that divides the given polynomial (of degree n) into two polynomials one containing lower degree terms(lower than n\/2) and other containing higher degree terns (higher than or equal to n\/2)<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Let the two given polynomials be A and B.<br \/>\nFor simplicity, Let us assume that the given two polynomials are of<br \/>\nsame degree and have degree in powers of 2, i.e., n = 2i<\/p>\n<p>The polynomial \u2018A\u2019 can be written as A0 + A1*xn\/2<br \/>\nThe polynomial \u2018B\u2019 can be written as B0 + B1*xn\/2<\/p>\n<p>For example 1 + 10x + 6\u00d72 \u2013 4\u00d73 + 5\u00d74 can be<br \/>\nwritten as (1 + 10x) + (6 \u2013 4x + 5\u00d72)*x2<\/p>\n<p>A * B = (A0 + A1*xn\/2) * (B0 + B1*xn\/2)<br \/>\n= A0*B0 + A0*B1*xn\/2 + A1*B0*xn\/2 + A1*B1*xn<br \/>\n= A0*B0 + (A0*B1 + A1*B0)xn\/2 + A1*B1*xn<br \/>\nSo the above divide and conquer approach requires 4 multiplications and O(n) time to add all 4 results. Therefore the time complexity is T(n) = 4T(n\/2) + O(n). The solution of the recurrence is O(n2) which is same as the above simple solution.<\/p>\n<p>The idea is to reduce number of multiplications to 3 and make the recurrence as T(n) = 3T(n\/2) + O(n)<\/p>\n<p>How to reduce number of multiplications?<br \/>\nThis requires a little trick similar to Strassen\u2019s Matrix Multiplication. We do following 3 multiplications.<\/p>\n<p>X = (A0 + A1)*(B0 + B1) \/\/ First Multiplication<br \/>\nY = A0B0 \/\/ Second<br \/>\nZ = A1B1 \/\/ Third<\/p>\n<p>The missing middle term in above multiplication equation A0*B0 + (A0*B1 +<br \/>\nA1*B0)xn\/2 + A1*B1*xn can obtained using below.<br \/>\nA0B1 + A1B0 = X \u2013 Y \u2013 Z<br \/>\nSo the time taken by this algorithm is T(n) = 3T(n\/2) + O(n)<br \/>\nThe solution of above recurrence is O(nLg3) which is better than O(n2).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C++ Programming Multiply two polynomials &#8211; Mathematical Algorithms &#8211; A simple solution is to one by one consider every term of first polynomial and multiply<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,74058],"tags":[77780,77772,70840,77751,77752,76710,77754,7382,77777,77764,77630,77758,77770,76149,77631,77759,77776,77768,77773,77766,72928,74837,74835,75068,70828,74832,77761,77771,77105,77775,77750,76066,77756,77755,77769,77767,77765,77781,77779,77016,77774,77778,77753,77749,77760,77782,77757,75430,77763,77762],"class_list":["post-26203","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-mathematical-algorithms","tag-adding-polynomials-calculator","tag-addition-of-polynomials","tag-addition-program-in-c","tag-algorithm-for-polynomial-addition-using-linked-list-in-data-structure","tag-bisection-method-c-program","tag-c","tag-c-addition-program","tag-c-code","tag-c-language-addition-program","tag-c-language-programs-pdf","tag-c-program-for-addition","tag-c-program-quadratic-equation","tag-c-programming-addition","tag-c-programming-examples-pdf","tag-c-programming-exercises","tag-c-programming-exercises-with-solutions-pdf","tag-c-programming-functions","tag-c-programming-pdf","tag-c-programming-problems-and-solutions-pdf","tag-c-programs-using-functions","tag-divide-and-conquer-algorithm","tag-function-c-programming","tag-function-in-c-programming-examples","tag-function-program-in-c","tag-functions-in-c-programming","tag-functions-in-c-programming-with-examples","tag-ing","tag-introduction-to-numerical-analysis-pdf","tag-math-functions-in-c","tag-multiplication-of-polynomials","tag-multiplication-program-in-c","tag-multiplication-table","tag-multiplying-polynomials","tag-numerical-analysis-book-pdf-free-download","tag-numerical-analysis-pdf","tag-numerical-recipes","tag-numerical-recipes-in-c","tag-polynomial-addition-algorithm-in-data-structure","tag-polynomial-addition-in-data-structure-pdf","tag-polynomial-addition-using-array-in-c","tag-polynomial-calculator","tag-polynomial-calculator-with-steps","tag-polynomial-in-standard-form-calculator","tag-polynomial-multiplication","tag-product-of-polynomials","tag-product-of-polynomials-formula","tag-sample-c-programs-pdf","tag-simple-addition-program-in-c","tag-simple-c-programming-exercises","tag-w3schools-c-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26203","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=26203"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26203\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}