多项式乘法的递归误差

Question

两天来，我一直在用python中的Karatsuba方法计算多项式乘法

我正在使用这个算法步骤和这个辅助函数

1. 如果n=1或n=2，直接解决问题；否则：

2. 从X和Y中构造四个n/2-1次的半尺寸多项式a、b、c和d。将X分成a和b两部分，将Y分成c和d两部分，这样a和c的阶数就低了 X和Y以及b和d的系数（指数0到n/2-1）将 具有高阶系数（指数n/2到n-1）

3. 计算x'=a+b和y'=c+d之和——注意，x'和y'也是n/2-1次多项式

4. 计算温度=x'。y’递归地

5. 递归计算ac和bd

6. 设温度=温度-ac-bd

7. 将ac、bd和temp（它们都是n-1次多项式）组合成一个新的2n-1次多项式，将ac放在指数0中 通过n-1，bd在索引n到2n-1中，并将temp添加到 现在索引n/2到3n/2-1中的值。请注意 最高系数为0

def add(poly1, poly2):
    """Add two polynomials"""
    result = [0] * max(len(poly1), len(poly2))
    for i in range(len(result)):
        if i < len(poly1):
            result[i] += poly1[i]
        if i < len(poly2):
            result[i] += poly2[i]
    return result


def split(poly1, poly2):
    """Split each polynomial into two smaller polynomials"""
    mid = max(len(poly1), len(poly2)) // 2
    return  (poly1[:mid], poly1[mid:]), (poly2[:mid], poly2[mid:])


def increase_exponent(poly, n):
    """Multiply poly1 by x^n"""
    return [0] * n + poly

我的代码

def multiply_optimized(poly1, poly2):
    #step 1
    if len(poly1) <= 1 or len(poly2) <=1:
        return np.multiply(poly1,poly2).tolist()
    
    else:
        #spliting the polynomial into 4 half-size step 2
        A, B = split(poly1,poly2)
        a, b,= A
        c,d = B
        
        #recursively calculate ac,bd,and, (a + b, c + d)
        #step 5
        ac = multiply_optimized(a,c)
        bd = multiply_optimized(b,d)
        #step 3
        x,y = add(a,b),add(c,d)
        
        temp = multiply_optimized(x,y)
        
        print('This is ac: ',ac, 'This is bd',bd, 'This is temp:',temp)
        #step 6
        temp = temp-ac-bd

        
        return ac+bd,temp

poly1 = [2,3,9,4,5]
poly2 = [2,6,4,5,1,3]
multiply_optimized(poly1,poly2)

预期产量 [4, 18, 44, 84, 87, 100, 58, 56, 17, 15]

我想我在第3步、第4步和第6步都弄错了，结果是

TypeError                                 Traceback (most recent call last)
<ipython-input-116-d2448c352e3e> in <module>
----> 1 multiply_optimized(x,y)

<ipython-input-115-e5282c0d225a> in multiply_optimized(poly1, poly2)
     14 
     15         x,y = add(a,b),add(c,d)
---> 16         ac = multiply_optimized(a,c)
     17         bd = multiply_optimized(b,d)
     18 

<ipython-input-115-e5282c0d225a> in multiply_optimized(poly1, poly2)
     15         x,y = add(a,b),add(c,d)
     16         ac = multiply_optimized(a,c)
---> 17         bd = multiply_optimized(b,d)
     18 
     19         temp = multiply_optimized(x,y)

<ipython-input-115-e5282c0d225a> in multiply_optimized(poly1, poly2)
     20 
     21         print('This is ac: ',ac, 'This is bd',bd, 'This is temp:',temp)
---> 22         temp = temp-ac-bd
     23 
     24 

TypeError: unsupported operand type(s) for -: 'list' and 'list'

我理解这个错误的意思，但我就是不能为上面的步骤3,4,6找出最好的解决方案