Python3实现FFT/IFFT结果与numpy.fft不一致问题求助

问题1：FFT结果虚部符号与numpy完全相反 #

该问题本质是FFT旋转因子的符号约定不匹配：

• 主流数值计算库（包括numpy）的FFT正变换采用的单位根定义为 ω = e^(-2πik/n)，如果你的实现中FFT正变换用的是 ω = e^(2πik/n)，输出结果就会是numpy结果的共轭，自然出现实部一致、虚部符号完全相反的情况。
• 修复方案：将FFT正变换的旋转因子指数符号改为负，即可和numpy输出对齐。如果不需要对齐numpy，只要保证FFT和IFFT的符号配对，也可以正常完成大整数乘法计算。

问题2：IFFT输出完全无规律错误 #

该问题通常由以下几类逻辑错误导致，按优先级排查即可：

• 旋转因子配对逻辑错误：如果FFT用了e^(-2πik/n)作为单位根，IFFT必须对应使用e^(2πik/n)作为单位根，符号完全相反，不能写错。
• 归一化时机/操作错误：IFFT的归一化（除以序列长度n）必须在所有蝶形运算完成后统一执行，不要在中间运算步骤做除法，也不要漏做除法。
• 位反转置换遗漏/错误：FFT和IFFT运算前都需要对输入序列做位反转重排，很多实现会漏掉IFFT的重排步骤，直接运算就会得到完全混乱的结果。
• 蝶形运算幂次计算错误：检查不同迭代层级下旋转因子的幂次步长是否和当前分组大小匹配，不要出现幂次索引越界、步长计算颠倒的问题。

快速验证方法 #

完成修改后可按如下逻辑验证正确性：

1. 输入任意长度为2的整数次幂的实数序列，用自己实现的FFT计算结果，再用自己实现的IFFT计算逆变换，结果和输入序列的误差在1e-10以内即为实现正确。
2. 若要对齐numpy输出，直接对比相同输入下的FFT、IFFT结果即可。

内容的提问来源于stack exchange，提问作者L.J.Zeng