FFT优化疑问：离散傅里叶变换指数项预计算的实现原理是什么？

核心逻辑基于离散傅里叶变换旋转因子的周期性，具体解释如下：

1. 先明确指数项的本质 #

你代码中用到的复数指数项就是标准DFT的旋转因子：
你代码里用atan(1.0)/n * -8.0计算得到的虚部常数是-2π/n，因此嵌套循环里计算的cexp(z4)本质为：
$$e^{tmp \times k \times m} = e^{-j\frac{2\pi}{n} \times k \times m}$$
这个值在DFT中一般记作旋转因子$W_n^{km}$。

2. 旋转因子的周期性 #

旋转因子有个非常重要的固有特性：周期为$n$，推导很简单：
$$W_n^{x + n} = e^{-j\frac{2\pi(x+n)}{n}} = e^{-j\frac{2\pi x}{n}} \times e^{-j2\pi}$$
我们知道$e^{-j2\pi} = cos(-2\pi) + j sin(-2\pi) = 1$，所以可得：
$$W_n^{x + n} = W_n^x$$
简单说就是：只要两个指数的差值是$n$的整数倍，对应的旋转因子值完全相等。

3. 取模操作的作用 #

正是因为上述周期性，不管$km$的数值多大，比如你提到的1000*900=900000，只要计算$km \mod n$得到余数$p$，就有$W_n^{km} = W_n^p$。
你的优化代码里预计算的pre[p]刚好就是$W_n^p$的值，所以直接读取pre[p]就能得到和原慢速代码中调用cexp计算大指数完全一致的结果，把原来嵌套循环里开销极高的复数指数运算，替换成了一次低开销的取模运算+数组读取，性能自然会有明显提升。

额外注意 #

你当前的优化代码里预计算数组pre只固定分配了1024个复数的空间，仅支持$n \leq 1024$的输入，如果要适配任意$n$，可以把分配内存的代码改为：

pre = (COMPLEX *)malloc(sizeof(struct cpx)*n);

避免出现数组越界访问的问题。

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