小编Ala*_*tif的帖子

我正在尝试实现多项式乘法的分而治之算法.这是演讲笔记中给出的伪代码:

其中A, B是每个多项式的系数列表,n是问题的大小(程度-1),并且a_l, b_l是感兴趣的系数的索引.

这是我尝试使用Python3实现它:

def poly_mult_dc_naive(A, B, n, a, b):
  n = int(n)
  a = int(a)
  b = int(b)
  C = [None] * int(2*n - 1)

  if n == 1:
    C[0] = A[a] * B[b]
    return C[0]

  C[0:n-1] = poly_mult_dc_naive(A, B, n//2, a, b)
  C[n:2*n-1] = poly_mult_dc_naive(A, B, n//2, a + (n // 2), b + (n // 2))

  W = poly_mult_dc_naive(A, B, n/2, a, b + (n // …