1
У меня есть функции FFT и IFFT. И я знаю, чтоFFT Multiplication Python 3.4.3
A * B = ОБПФ (FFT (A) * FFT (B))
Где
FFT (A) FFT (B) = [ д ш при д, ш, в молнии (А, в)]
Но когда я вход: 10 10 => выход: [(0,5 + 0j), (0,5 + 0j)] Что i`m делать не так? Вот мой код:
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))
Я не уверен, что получил вашу мысль. Но A * B = IFFT (FFT (A) * FFT (B)) не кажется мне правдоподобным, оно скорее идет как A \ ast B = IFFT (FFT (A) * FFT (B)), где \ ast продукт свертки. Проверьте [эту страницу в Википедии] (http://en.wikipedia.org/wiki/Convolution_theorem). – Tony
Я думал, что FFT (A * B) = FFT (A) * FFT (B). Это означает, что IFFT (FFT (A * B)) = IFFT (FFT (A) * FFT (B)), и это A * B = IFFT (FFT (A) * FFT (B)) – Reodont
Я не думаю, что FFT (A * B) = FFT (A) * FFT (B) является правильным. Вы можете проверить предыдущую ссылку. – Tony