多项式逆FFT实现异常：IFFT(FFT)未返回原序列问题排查

问题背景 #

实现了用于快速多项式乘法的FFT和IFFT算法，测试代码print(ifft(fft([1, 2, 3, 4])))期望得到原系数列表[1,2,3,4]，但忽略浮点精度问题后得到结果[(4+0j), (11-0j), (12+0j), (13+0j)]，需排查原因。

核心结论 #

你应该得到原序列，代码的问题出在IFFT的实现逻辑上。

错误分析 #

正确的逆傅里叶变换（IFFT）逻辑是：对输入序列执行FFT（使用共轭单位根），再将整个结果统一除以序列长度n。而你的代码存在两个关键错误：

1. 错误地将缩放因子1/n嵌入到递归的单位根中，导致每一层递归都应用了缩放，最终结果的缩放倍数完全错误。
2. 返回类型标注不符合实际，FFT和IFFT的输出是复数类型，而非整数类型。

修正后的代码 #

from typing import List
import numpy as np


def fft(p: List[int]) -> List[complex]:
    n = len(p)
    if n == 1:
        return [complex(x) for x in p]
    
    unity_root = np.exp(2j * np.pi / n)
    
    p_even = p[::2]
    p_odd = p[1::2]
    
    y_even = fft(p_even)
    y_odd = fft(p_odd)
    
    y = [0+0j] * n
    for j in range(n // 2):
        omega = np.power(unity_root, j)
        y[j] = y_even[j] + omega * y_odd[j]
        y[n // 2 + j] = y_even[j] - omega * y_odd[j]
    
    return y


def ifft(p: List[complex]) -> List[complex]:
    n = len(p)
    if n == 1:
        return p
    
    # IFFT使用共轭单位根，逻辑与FFT一致
    unity_root = np.exp(-2j * np.pi / n)
    
    p_even = p[::2]
    p_odd = p[1::2]
    
    y_even = ifft(p_even)
    y_odd = ifft(p_odd)
    
    y = [0+0j] * n
    for j in range(n // 2):
        omega = np.power(unity_root, j)
        y[j] = y_even[j] + omega * y_odd[j]
        y[n // 2 + j] = y_even[j] - omega * y_odd[j]
    
    # 最后统一除以n完成缩放
    return [x / n for x in y]

验证结果 #

运行测试代码print(ifft(fft([1, 2, 3, 4])))，忽略浮点精度误差后，结果为：

[(1+0j), (2+0j), (3+0j), (4+0j)]

与原序列完全一致。

补充说明 #

• 浮点精度误差是FFT计算的正常现象，可通过np.round或取实部后四舍五入得到整数结果。
• 原代码的返回类型标注错误，FFT和IFFT的输出必然包含复数，需修正为List[complex]。

内容的提问来源于stack exchange，提问作者Rami Hashan