How to calculate sum of two polynomials?

For instance 3x^4 - 17x^2 - 3x + 5. Each term of the polynomial can be represented as a pair of integers (coefficient,exponent). The polynomial itself is then a list of such pairs like
[(3,4), (-17,2), (-3,1), (5,0)] for the polynomial as shown.

[(3,4), (-17,2), (-3,1), (5,0)]

Zero polynomial, 0, is represented as the empty list , since it has no terms with nonzero coefficients.

I want to write two functions to add and multiply two input polynomials with the same representation of tuple (coefficient, exponent):

addpoly(p1, p2)

multpoly(p1, p2)

Test Cases:

addpoly([(4,3),(3,0)], [(-4,3),(2,1)])

should give [(2, 1),(3, 0)]

addpoly([(4,3),(3,0)], [(-4,3),(2,1)])

[(2, 1),(3, 0)]

addpoly([(2,1)],[(-2,1)])

should give

addpoly([(2,1)],[(-2,1)])

multpoly([(1,1),(-1,0)], [(1,2),(1,1),(1,0)])

should give [(1, 3),(-1, 0)]

multpoly([(1,1),(-1,0)], [(1,2),(1,1),(1,0)])

[(1, 3),(-1, 0)]

Here is something that I started with but got completely struck!

def addpoly(p1, p2):
(coeff1, exp1) = p1
(coeff2, exp2) = p2
if exp1 == exp2:
coeff3 = coeff1 + coeff2


4: 3, 2: 17, 1: 3, 0: 5

collections.Counter

addpoly

3 Answers
3

As suggested in the comments, it is much simpler to represent polynomials as multisets of exponents.

In Python, the closest thing to a multiset is the Counter data structure. Using a Counter (or even just a plain dictionary) that maps exponents to coefficients will automatically coalesce entries with the same exponent, just as you'd expect when writing a simplified polynomial.

Counter

You can perform operations using a Counter, and then convert back to your list of pairs representation when finished using a function like this:

Counter

def counter_to_poly(c):
p = [(coeff, exp) for exp, coeff in c.items() if coeff != 0]
# sort by exponents in descending order
p.sort(key = lambda pair: pair[1], reverse = True)
return p


To add polynomials, you group together like-exponents and sum their coefficients.

def addpoly(p, q):
r = collections.Counter()

for coeff, exp in (p + q):
r[exp] += coeff

return counter_to_poly(r)


(In fact, if you were to stick with the Counter representation throughout, you could just return p + q).

return p + q

To multiply polynomials, you multiply each term from one polynomial pairwise with every term from the other. And furthermore, to multiply terms, you add exponents and multiply coefficients.

def mulpoly(p, q):
r = collections.Counter()

for (c1, e1), (c2, e2) in itertools.product(p, q):
r[e1 + e2] += c1 * c2

return counter_to_poly(r)


I have come up with a solution but I'm unsure that it's optimized!

def addpoly(p1,p2):
for i in range(len(p1)):
for item in p2:
if p1[i][1] == item[1]:
p1[i] = ((p1[i][0] + item[0]),p1[i][1])
p2.remove(item)
p3 = p1 + p2
for item in (p3):
if item[0] == 0:
p3.remove(item)
return sorted(p3)


and the second one:-

def multpoly(p1,p2):
for i in range(len(p1)):
for item in p2:
p1[i] = ((p1[i][0] * item[0]), (p1[i][1] + item[1]))
p2.remove(item)
return p1


This python code worked for me,hope this works for u too..

Addition func

def addpoly(p1,p2):
i=0
su=0
j=0
c=
if len(p1)==0:
#if p1 empty
return p2
if len(p2)==0:
#if p2 is empty
return p1
while i<len(p1) and j<len(p2):
if int(p1[i][1])==int(p2[j][1]):
su=p1[i][0]+p2[j][0]
if su !=0:
c.append((su,p1[i][1]))
i=i+1
j=j+1
elif p1[i][1]>p2[j][1]:
c.append((p1[i]))
i=i+1
elif p1[i][1]<p2[j][1]:
c.append((p2[j]))
j=j+1
if p1[i:]!=:
for k in p1[i:]:
c.append(k)
if p2[j:]!=:
for k in p2[j:]:
c.append(k)
return c


Multiply func

def multipoly(p1,p2):
p=
s=0
for i in p1:
c=
for j in p2:
s=i[0]*j[0]
e=i[1]+j[1]
c.append((s,e))
p=addpoly(c,p)
return p


Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.