import numpy as np
from fft import dft,inv_dft,inv_fft,fft


def multiply(A, B):
    m=len(A)
    n=len(B)
    prod = [0] * (m + n - 1);
    for i in range(m):
        for j in range(n):
            prod[i + j] += A[i] * B[j];
    return prod;


#driver code
#Randomly generating the two coefficient arrays with size 4
param1 = list(np.random.randint(low = 0, high = 1000, size = 4))
param2 = list(np.random.randint(low = 0, high = 1000, size = 4))
#The result generated by "convolution for loop" method
print("The answer obtained by brute force multiplication: \n", multiply(param1,param2),"\n")

#degree bound extension
l = [0 for i in range(0,4)]
param1.extend(l)
param2.extend(l)

PA = fft(param1)
PB = fft(param2)

#pointwise multiply
C = []
for i in range(PA.shape[0]):
    C.append(PA[i]*PB[i])

#print the answer obtained by inverse fft
print("The answer obtained by calling inverse fft function \n",inv_fft(C),"\n")


