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 pair

Solution 1:

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.

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

defcounter_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

    returncounter_to_poly(r)

(In fact, if you were to stick with the Counter representation throughout, you could just 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)

Solution 2:

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

Addition func

defaddpoly(p1,p2):
i=0
su=0
j=0
c=[]
iflen(p1)==0:
    #if p1 emptyreturn p2
iflen(p2)==0:
    #if p2 is emptyreturn p1
while i<len(p1) and j<len(p2):
    ifint(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+1elif p1[i][1]>p2[j][1]:
        c.append((p1[i]))
        i=i+1elif p1[i][1]<p2[j][1]:
        c.append((p2[j]))
        j=j+1if 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=0for 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 

Solution 3:

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

defaddpoly(p1,p2):
        for i inrange(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)
        returnsorted(p3)

and the second one:-

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