Multiplying Polynomials

[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.

[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)
        )

[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.

[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)

[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.

[TrustyTony]

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

[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