I am trying to implement the divide-and-conquer algorithm for polynomial multiplication. Here is the pseudocode given in the lecture notes:
where A, B
are lists of coefficients of each polynomial, n
is the size of the problem (degree - 1) and a_l, b_l
are indices of the coefficients of interest.
Here is my attempt at implementing it using 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 // 2))
V = poly_mult_dc_naive(A, B, n/2, a + n/2, b)
C[n // 2:n + (n // 2) - 1] += W + V
return C
However I'm getting strange results. For example let A = [1,2,3,4] B = [4,3,2,1]
I get:
[4, None, 8, 3, 6, 12, None, 16, 9, 12, 2, None, 4, 1, 2, None, 8, 3, 4, None, None]
Correct answer is [4, 11, 20, 30, 20, 11, 4]
Could someone please point out where I've gone wrong and how it could be done?
Quick update: I think I've managed to debug my code my using a numpy array for C instead of a list. Here is the updated version:
import numpy as np
def poly_mult_dc_naive(A, B, n: int, a: int, b: int):
C = np.zeros(2*n - 1, dtype=int) # here I changed it from list to np array
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 // 2))
V = poly_mult_dc_naive(A, B, n/2, a + (n//2), b)
C[(n // 2) : (3*n // 2) - 1] += W + V
return C
BONUS QUESTION: Does anyone know of a better way I could keep the arguments n, a, and b as int types?
I just feel like having to write:
n = int(n)
a = int(a)
b = int(b)
might not be the most elegant way.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With