python中numpy函数fft_Python中使用内置Numpy的FFT多项式乘法。

我想用python快速乘法两个多项式。因为我的多项式是相当大的(超过100000)个元素，所以我必须将它们相乘很多。下面，你会找到我的方法from numpy.random import seed, randint

from numpy import polymul, pad

from numpy.fft import fft, ifft

from timeit import default_timer as timer

length=100

def test_mul(arr_a,arr_b): #inbuilt python multiplication

c=polymul(arr_a,arr_b)

return c

def sb_mul(arr_a,arr_b): #my schoolbook multiplication

c=[0]*(len(arr_a) + len(arr_b) - 1 )

for i in range( len(arr_a) ):

for j in range( len(arr_b) ):

k=i+j

c[k]=c[k]+arr_a[i]*arr_b[j]

return c

def fft_test(arr_a,arr_b): #fft based polynomial multuplication

arr_a1=pad(arr_a,(0,length),'constant')

arr_b1=pad(arr_b,(0,length),'constant')

a_f=fft(arr_a1)

b_f=fft(arr_b1)

c_f=[0]*(2*length)

for i in range( len(a_f) ):

c_f[i]=a_f[i]*b_f[i]

return c_f

if __name__ == '__main__':

seed(int(timer()))

random=1

if(random==1):

x=randint(1,1000,length)

y=randint(1,1000,length)

else:

x=[1]*length

y=[1]*length

start=timer()

res=test_mul(x,y)

end=timer()

print("time for built in pol_mul", end-start)

start=timer()

res1=sb_mul(x,y)

end=timer()

print("time for schoolbook mult", end-start)

res2=fft_test(x,y)

print(res2)

#########check############

if( len(res)!=len(res1) ):

print("ERROR");

for i in range( len(res) ):

if( res[i]!=res1[i] ):

print("ERROR at pos ",i,"res[i]:",res[i],"res1[i]:",res1[i])

下面是我的详细方法，

1首先，我尝试了一个简单的教科书实现，复杂度为O(n^2)。但正如你所料，结果是非常缓慢的。在第二，我在Numpy库中认识了polymul。这个函数比前一个函数快得多。但我意识到这也是一个O(n^2)的复杂性。你可以看到，如果你增加长度k，时间会增加k^2倍。

我的第三种方法是使用内置的FFT函数尝试基于FFT的乘法。我遵循了众所周知的方法，也描述了here，但我不能让它工作。

现在我的问题是我在基于FFT的方法中哪里出错了？你能告诉我怎么修吗？

我所观察到的polymul函数具有O(n^2)复杂度，这是正确的吗？

如果你有任何问题，请告诉我。

提前谢谢。在