我有 FFT 和 IFFT 函数。我知道
A*B = IFFT(FFT(A)*FFT(B))
在哪里
FFT(A) FFT(B)=[q w for q,w in zip(A,B)]
但是当我输入： 10 10 => 输出： [(0.5+0j), (0.5+0j)] 我做错了什么？这是我的代码：
from cmath import exp,pi
def FFT(X):
n = len(X)
w = exp(-2*pi*1j/n)
if n > 1:
X = FFT(X[::2]) + FFT(X[1::2])
for k in range(n//2):
xk = X[k]
X[k] = xk + w**k*X[k+n//2]
X[k+n//2] = xk - w**k*X[k+n//2]
return X
def IFFT(X):
n = len(X)
w = exp(2*pi*1j/n)
if n > 1:
X = IFFT(X[::2]) + IFFT(X[1::2])
for k in range(n//2):
xk = X[k]
X[k] = (xk + w**k*X[k+n//2])/n
X[k+n//2] = ((xk - w**k*X[k+n//2]))/n
return X
s = input().split()
a1 = s[0]
b1 = s[1]
a = [int(x) for x in a1]
b = [int(x) for x in b1]
if (len(a)>len(b)):
n = len(a)
b.reverse()
while (len(b)<n):
b.extend([0])
b.reverse()
else:
n = len(b)
a.reverse()
while(len(a)<n):
a.extend([0])
a.reverse()
c = [q*w for q,w in zip(a,b)]
print (IFFT(c))