Polynomial Multiplication using divide and conquer-CodePudding

I'm trying to write code that performs polynomial multiplication using a divide and conquer method. It uses a trick to do only 3 multiplications instead of 4 multiplications, involving splitting each polynomial into two halves and factoring out an x^n/2 from one of the two halves. My code is returning the wrong answer with some test cases and I'm not sure what I'm doing wrong.

Edit: Adding naive multiply function and test cases.

Here's what I've tried so far:

class Polynom:
    """stores polynomial object"""

    def __init__(self, coefficients):
        """pass coefficient list in increasing order, i.e. x^0   x^1   x^2   ...   x^n"""
        self.coefficients = coefficients
        self.length = len(coefficients)
        self.nonZero = np.count_nonzero(self.coefficients)

    def __add__(self, other):
        for i in range(0,other.length):
            try:
                self.coefficients[i] = self.coefficients[i]   other.coefficients[i]
            except:
                self.coefficients.append(0)
                self.coefficients[i] = self.coefficients[i]   other.coefficients[i]
        self.length = len(self.coefficients)
        self.nonZero = np.count_nonzero(self.coefficients)
        return self

    def __sub__(self, other):
        for i in range(0,other.length):
            self.coefficients[i] = self.coefficients[i] - other.coefficients[i]
        self.length = len(self.coefficients)
        self.nonZero = np.count_nonzero(self.coefficients)
        return self

    def split(self):
        first_max_ind = int((self.length-1)/2)
        first_coefs = self.coefficients[:first_max_ind]
        first = Polynom(first_coefs)
        second_coefs = self.coefficients[first_max_ind:]
        second = Polynom(second_coefs)
        return first, second

def divideAndConquer(a,b):
    """simple divide and conquer algorithm for multiplication"""
    
    if a.nonZero == 2 and b.nonZero == 2:
        c = naiveMultiply(a,b)
        return c
    else:
        a0, a1 = a.split()
        b0, b1 = b.split()

        # calculate y, u, and z
        y = divideAndConquer(a0   a1, b0   b1)
        u = divideAndConquer(a0, b0)
        z = divideAndConquer(a1, b1)
        middleTerm = y - u - z
        
        NOver2 = int(max(a.length/2, b.length/2))
        lyst = [0] * int(NOver2   1)
        lyst[NOver2] = 1
        xNOver2 = Polynom(lyst)
        
        return u   naiveMultiply(middleTerm, xNOver2)   naiveMultiply(z, xNOver2)

def naiveMultiply(a,b):
    """takes two polynomials and multiplies using naive approach"""
    
    maxLength = a.length   b.length - 1
    coefficientList = [0] * maxLength
    
    for i in range(0,a.length):
        for j in range(0, b.length):
            power = i   j
            coefficient = a.coefficients[i] * b.coefficients[j]
            coefficientList[power]  = coefficient
    
    return Polynom(coefficientList)

a = Polynom([1,2,3,4,5])
b = Polynom([1,2,3,4,5])

naiveMultiply(a,b)
divideAndConquer(a,b)

The correct answer for test case: (1 2x 3x^2 4x^3 5x^4)^2 should be: 1 4x 10x^2 20x^3 35x^4 44x^5 46x^6 40x^7 25x^8

but I'm getting: 100 100x 25x^2 0x^3 0x^4 0x^5

CodePudding user response：

Your __add__ and __sub__ methods alter the self instance (note the assignments to self.coefficients).

Further down in the divideAndConquer method, I see that you are using a variable a0 in an expression a0 a1, which would alter the value of a0 to become a0 a1. You then use the same (altered) a0 variable in further expressions, possibly not aware that the variable now has a different value.

In general, overloaded operator methods should probably create a new instance instead of altering self, this will make them much safer to use.

in this case, for example, a safe implementation of __add__ would be

def __add__(self, other):
    coefficients = list(self.coefficients)
    for i in range(0,other.length):
        try:
            coefficients[i] = self.coefficients[i]   other.coefficients[i]
        except:
            coefficients.append(0)
            coefficients[i] = coefficients[i]   other.coefficients[i]
    return Polynom(coefficients)

CodePudding user response：

In addition to the Pyton-level implementation bugs, there are also math-level bugs here: the polynomials are split down their own middles, but that creates a problem when putting the pieces back together. Also the z piece shouldn't be scaled by the same amount as the middleTerm.

This already looks suspicious anyway:

    NOver2 = int(max(a.length/2, b.length/2))

The goal with the calculation of middleTerm is that the scaled middleTerm (after shifting it) is identical to a0 * b1 * scaleB a1 * scaleA * b0 (where scaleA corresponds to the size of a0, and scaleB corresponds to the size of b0). If scaleA == scaleB then that's no problem, multiply by the scale afterwards (by shifting - if you implement this scaling as a naiveMultiply then the algorithm isn't efficient). But in this code, the scales are not necessarily the same, they depend on the sizes of a and b. That's a problem.

The z piece is the products of two "upper halves", so it picks up two of those scale factors. So it should be multiplied by the square of the factor that the middle term is scaled by, or rather, shifted by twice as much as the middle term is shifted by.