Fast Fourier Transform算法单符号错误导致与在线计算器结果不一致

你遇到的虚部符号相反的问题，本质是FFT的旋转因子符号约定差异导致的，不属于代码错误。

• DFT（离散傅里叶变换）有两种广泛使用的定义：
  1. 信号处理领域通用约定：正向变换的旋转因子为 exp(-2 * π * i * k / n)，你使用的在线计算器采用的就是该约定，输出结果符合绝大多数信号处理工具的默认设置。
  2. 你参考的伪代码采用的是多项式乘法场景常用的约定：正向变换的旋转因子为 exp(2 * π * i * k / n)，和你当前代码的实现一致，该版本在多项式快速乘法场景下不需要额外调整符号，使用更便捷。
• 如果需要和在线计算器的输出对齐，仅需要修改代码中omega的计算行，将指数部分改为负号即可：

# 修改前
omega = cmath.exp((2 * cmath.pi * 1j)/n)
# 修改后
omega = cmath.exp((-2 * cmath.pi * 1j)/n)

• 两种实现均符合数学定义，没有对错区别，仅需要根据你的使用场景选择即可：如果是做多项式相关计算，原有代码无需修改；如果是做信号频域分析，建议修改为负号版本和通用工具的输出保持一致。

内容的提问来源于stack exchange，提问作者Simon Balfe