FFT 乘法 Python 3.4.3

Question

我有一个 FFT 和 IFFT 函数。我知道

A*B = IFFT(FFT(A)*FFT(B))

哪里

FFT(A)FFT(B)=[qw 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))

Answer 1

您实际上应该将 FFT 应用于您的输入序列 a 和 b。大量填充程序后似乎出现了疏忽。

c = IFFT( [ q*w for q,w in zip( FFT(a), FFT(b) ) ] )

您所做的可以通过多种方式之一解释为执行

的多项式乘法

a[0]+a[1]*z+...+a[n-1]*z^(n-1)  mod (z^n-1)

和

b[0]+b[1]*z+...+b[n-1]*z^(n-1)  mod (z^n-1)

通过首先在单位圆上的 n 个等距点处求值，将点值相乘，然后从相乘值内插结果多项式。 1/n 因子到 IFFT 的实现，尤其是分配符合此过程。

FFT 乘法 Python 3.4.3

FFT Multiplication Python 3.4.3

python

math

fft

multiplication

ifft