Member Avatar for JJHT7439

Hey, I have a homework problem in which I have to multiply two polynomials. I am assuming that the 2 polynomials can each be of any length so I am stuck as to how I am supposed to do that. My homework sheet derives how to do it like this (not sure how to write it in text, but the variable/number after a is under it):

p1 = anx^n + ... + a1x + a0
p1*p2 = (anx^n + ... + a1x + a0) * p2
      = (anx^n + ... + a1x) * p2 + a0 x p2
      = (anx^n + ... + a1) * (p2 * x) + a0 * p2
      = shiftRight(p1) * shiftLeft(p2) + constCoef(p1) * p2

(Explains that if you keep shifting right it will eventually be 0, and the answer is straight forward)

I also have some code already done that does the functions above. Also note that polynomials in this homework are put into lists, and reversed. Meaning that the polynomial 3x+2 = [2,3]

# Standardizes the polynomial (Gets rid of trailing 0s)
def standardize(lst):
    if lst[len(lst)-1] == 0:
        lst.pop()
    return lst

# Finds if the polynomial is 0
def isZeroPoly(lst):
    if lst == []:
        return True
    else:
        return False

# Adds 2 polynomials ([2,3],[4,5] => [6,8])
def addPoly(lst1,lst2):
    result = []
    if len(lst1) > len(lst2):
        for x in range(0,len(lst1)):
            if len(lst2)-1 < x:
                result.append(lst1[x])
            else:
                result.append(lst1[x] + lst2[x])
    else:
        for x in range(0,len(lst2)):
            if len(lst1)-1 < x:
                result.append(lst2[x])
            else:
                result.append(lst1[x] + lst2[x])
    standardize(result)
    return result

# Scales the polynomial by the scale variable ((3,[1,2,3]) => [3,6,9])
def scalePoly(scale,lst):
    for x in range(0,len(lst)):
        lst[x] = (lst[x] * scale)
    standardize(lst)
    return lst

# Gives the constant in the polynomial ([2,3,4] => [2])
def constCoef(lst):
    constant = lst[0]
    return constant

# Shifts the polynomial left ([2,3,4] => [0,2,3,4])
def shiftLeft(lst):
    newlst = []
    newlst.append(0)
    for x in range(0,len(lst)):
        newlst.append(lst[x])
    return newlst

# Shifts the polynomial right ([2,3,4] => [3,4])
def shiftRight(lst):
    lst.remove(lst[0])
    return lst

def mulPoly(lst1,lst2):
    result = []
    result1 = []
    for x in range(0,len(lst1)):
        for y in range(0,len(lst2)):
            result.append(lst1[x] * lst2[y])
    return result
    count = 0
    end = result.pop()
    result1 = []
    result1.append(result[0])
    for x in range(1,len(result),2):
        result1.append(result[x] + result[x+1])
    result1.append(end)
    return result1

The mulPoly function that I came up with quickly will only work with 2 2 term polynomials which is why I need help. Specifically I'm looking for either a different method or a way to make my method able to accept different sized polynomials and larger polynomials. Thanks for any help.

  • 3 Contributors
  • 6 Replies
  • 3K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Gribouillis

Dani AI

Generated

Nice catch by on avoiding in-place mutation and by about stripping all trailing zeros. With your reversed list representation, multiplication is just coefficient convolution: the coefficient of x^(i+j) is p[i] q[j] summed over all i,j. You can implement this iteratively without any shifting, which keeps it simple, fast (O(nm)), and side-effect free.

def _trim(poly):
    # remove all trailing zeros; never mutate caller's list
    poly = list(poly)
    while poly and poly[-1] == 0:
        poly.pop()
    return poly

def mul_poly(p, q):
    p = _trim(p)
    q = _trim(q)
    if not p or not q:          # zero polynomial
        return []
    res = [0] * (len(p) + len(q) - 1)
    for i, a in enumerate(p):
        if a == 0:
            continue
        for j, b in enumerate(q):
            if b == 0:
                continue
            res[i + j] += a * b
    return _trim(res)

Why this helps your thread:

  • No shifting or recursion, so you avoid the aliasing pitfall that bit shiftRight and the empty-list base case highlighted.
  • _trim mirrors ’s point: use a loop to remove all trailing zeros so [1,0,0] becomes [1], and [0,0] becomes [].
  • Works for any lengths, including edge cases like empty lists and leading zeros in inputs.

Quick check you can run: (x + 1) * (x^2 + 2) uses [1,1] * [2,0,1] and should return [2,2,1,1]. If you prefer the recursive style from your sheet, you can still keep helpers non-destructive and use _trim at boundaries to normalize zero consistently.

Recommended Answers

All 6 Replies

Member Avatar for Gribouillis

Why don't you try the algorithm explained above ? I would write

def mulPoly(lst1, lst2):
    if isZeroPoly(lst1):
        return []
    else:
        return addPoly(
            mulPoly(shiftRight(lst1), shiftLeft(lst2),
            scalePoly(constCoef(lst1), lst2)
        )
Member Avatar for JJHT7439

Why don't you try the algorithm explained above ? I would write

def mulPoly(lst1, lst2):
    if isZeroPoly(lst1):
        return []
    else:
        return addPoly(
            mulPoly(shiftRight(lst1), shiftLeft(lst2),
            scalePoly(constCoef(lst1), lst2)
        )

I did try it like that at first but I couldn't quite understand what it wanted and it kept giving me an error. And the code that you posted does not work either (I assume you forgot to close the first mulPoly arguments, so I fixed that). The code you have always gives me an error saying that the lst[0] of the constCoef is out of range. I don't understand how it could be though because it always checks at the start if the list doesn't have any items.

Member Avatar for Gribouillis

I did try it like that at first but I couldn't quite understand what it wanted and it kept giving me an error. And the code that you posted does not work either (I assume you forgot to close the first mulPoly arguments, so I fixed that). The code you have always gives me an error saying that the lst[0] of the constCoef is out of range. I don't understand how it could be though because it always checks at the start if the list doesn't have any items.

The error is in the shiftRight() function which modifies the list instead of returning a new list. So in the expression addPoly(mulPoly(shiftRight(lst1), shiftLeft(lst2)), scalePoly(constCoef(lst1), lst2)) , the first shiftRight transforms say [3] into [] and then constCoef finds an empty list.

The solution is that shiftRight returns a new list instead of modifying its argument. I changed your code so that none of the functions modifies the lists passed as arguments.

The program runs, it remains to check that it actually computes the product of 2 polynomials

# Standardizes the polynomial (Gets rid of trailing 0s)
def standardize(lst):
    lst = list(lst) # make a copy
    if lst[len(lst)-1] == 0:
        lst.pop()
    return lst

# Finds if the polynomial is 0
def isZeroPoly(lst):
    if lst == []:
        return True
    else:
        return False

# Adds 2 polynomials ([2,3],[4,5] => [6,8])
def addPoly(lst1,lst2):
    result = []
    if len(lst1) > len(lst2):
        for x in range(0,len(lst1)):
            if len(lst2)-1 < x:
                result.append(lst1[x])
            else:
                result.append(lst1[x] + lst2[x])
    else:
        for x in range(0,len(lst2)):
            if len(lst1)-1 < x:
                result.append(lst2[x])
            else:
                result.append(lst1[x] + lst2[x])
    result = standardize(result)
    return result

# Scales the polynomial by the scale variable ((3,[1,2,3]) => [3,6,9])
def scalePoly(scale,lst):
    lst = list(lst)
    for x in range(0,len(lst)):
        lst[x] = (lst[x] * scale)
    lst = standardize(lst)
    return lst

# Gives the constant in the polynomial ([2,3,4] => [2])
def constCoef(lst):
    constant = lst[0]
    return constant

# Shifts the polynomial left ([2,3,4] => [0,2,3,4])
def shiftLeft(lst):
    newlst = []
    newlst.append(0)
    for x in range(0,len(lst)):
        newlst.append(lst[x])
    return newlst

# Shifts the polynomial right ([2,3,4] => [3,4])
def shiftRight(lst):
    #lst.remove(lst[0])
    return lst[1:]

def mulPoly(lst1, lst2):
    print lst1, lst2
    if isZeroPoly(lst1):
        return []
    else:
        return addPoly(
            mulPoly(shiftRight(lst1), shiftLeft(lst2)),
            scalePoly(constCoef(lst1), lst2)
        )
        
P = [1, 2, 3]
Q = [4, 5, 6]
print mulPoly(P, Q)
Edited by Gribouillis because: n/a
Member Avatar for JJHT7439

The error is in the shiftRight() function which modifies the list instead of returning a new list. So in the expression addPoly(mulPoly(shiftRight(lst1), shiftLeft(lst2)), scalePoly(constCoef(lst1), lst2)) , the first shiftRight transforms say [3] into [] and then constCoef finds an empty list.

The solution is that shiftRight returns a new list instead of modifying its argument. I changed your code so that none of the functions modifies the lists passed as arguments.

The program runs, it remains to check that it actually computes the product of 2 polynomials

# Standardizes the polynomial (Gets rid of trailing 0s)
def standardize(lst):
    lst = list(lst) # make a copy
    if lst[len(lst)-1] == 0:
        lst.pop()
    return lst

# Finds if the polynomial is 0
def isZeroPoly(lst):
    if lst == []:
        return True
    else:
        return False

# Adds 2 polynomials ([2,3],[4,5] => [6,8])
def addPoly(lst1,lst2):
    result = []
    if len(lst1) > len(lst2):
        for x in range(0,len(lst1)):
            if len(lst2)-1 < x:
                result.append(lst1[x])
            else:
                result.append(lst1[x] + lst2[x])
    else:
        for x in range(0,len(lst2)):
            if len(lst1)-1 < x:
                result.append(lst2[x])
            else:
                result.append(lst1[x] + lst2[x])
    result = standardize(result)
    return result

# Scales the polynomial by the scale variable ((3,[1,2,3]) => [3,6,9])
def scalePoly(scale,lst):
    lst = list(lst)
    for x in range(0,len(lst)):
        lst[x] = (lst[x] * scale)
    lst = standardize(lst)
    return lst

# Gives the constant in the polynomial ([2,3,4] => [2])
def constCoef(lst):
    constant = lst[0]
    return constant

# Shifts the polynomial left ([2,3,4] => [0,2,3,4])
def shiftLeft(lst):
    newlst = []
    newlst.append(0)
    for x in range(0,len(lst)):
        newlst.append(lst[x])
    return newlst

# Shifts the polynomial right ([2,3,4] => [3,4])
def shiftRight(lst):
    #lst.remove(lst[0])
    return lst[1:]

def mulPoly(lst1, lst2):
    print lst1, lst2
    if isZeroPoly(lst1):
        return []
    else:
        return addPoly(
            mulPoly(shiftRight(lst1), shiftLeft(lst2)),
            scalePoly(constCoef(lst1), lst2)
        )
        
P = [1, 2, 3]
Q = [4, 5, 6]
print mulPoly(P, Q)

Wow thanks, I completely overlooked the destructive changes that were being made. Thanks for your help, Its working perfectly now.

Member Avatar for TrustyTony

For me looks like line 4 should be while not if, from the comment, so it can remove more than one trailing zero.

commented: True! the logic is wrong. +4
Member Avatar for Gribouillis

For me looks like line 4 should be while not if, from the comment, so it can remove more than one trailing zero.

Yes, there are many possible improvements. For example isZeroPoly could be the one liner return not lst

Edited by Gribouillis because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.