我已经编写了自己的 FFT，但想知道是否有办法将 Cooley 和 Turkey 方法结合起来。到目前为止，我已经获得了 N/2 log N 实数乘法来转换实数信号。

我当前的实现有 N log N 乘法（多一点，因为我没有优化 0 弧度的复杂正弦曲线的情况），但我有一个优化，可以将乘法次数减少 50%。

注意：这绝对不是功课，我写了这个算法，因为我发现 Cooley/Turkey 方法的解释太复杂了，同时我希望能够选择我在 FFT 和 IFFT 中处理的 bin以及能够将IFFT输出到多个通道。所以我只是决定找出我自己的 radix-2，同时理解变换的工作原理和原因（我有）。

原始问题（为清楚起见而编辑）---

示例代码：kfft.c

我想知道是否有与我类似的 FFT 算法。

我基本上通过从第一个信号的后半部分递归地减去信号的后半部分来分解计算来执行 FFT，这意味着 x[n] 只需在持续时间的一半内乘以复数正弦曲线，从而得到 N/2 log N 实数乘法（如下所示）。求和信号用于与作为采样周期倍数的复数正弦曲线相乘。例如组 {2, 6} 是 2 的倍数，因此具有 4 个样本的周期。

// For bins { 1, 3, 5 and 7 }

x1[0] = x0[0] - x0[4]
x1[1] = x0[1] - x0[5]
x1[2] = x0[2] - x0[6]
x1[3] = x0[3] - x0[7]
// Calculate sum (required for the next level of bins)
x0[0] = x0[0] + x0[4]
x0[1] = x0[1] + x0[5]
x0[2] = x0[2] + x0[6]
x0[3] = x0[3] + x0[7]

// For bins { 2 and 6 }

x2[0] = x0[0] - x0[2]
x2[1] = x0[1] - x0[3]
// Calculate sum (required for the next level of bins)
x0[2] = x0[0] + x0[2]
x0[3] = x0[1] + x0[3]

// For bin { 4 }
x3[0] = x0[0] - x0[1]
x3[1] = x0[0] + x0[1] // <-- This is the 0hz bin (sum)