众所周知（），FFT凭借如下公式得以实现 现在来谈谈具体的实现问题。
一、单位根的计算
在FFT中，对于下标不同的单位根，可以不用重复计算。此处单位根下标 都是 的幂即 ，因此当 ，
，所以对于下标不同的单位根，有 所以我们仅需计算下标最大的单位根数组 来表示 ，并在需要用到 时使用 即可。
二、系数最终位置的确定
在FFT中，把多项式系数依据奇偶次幂分开进行分治。递归版的FFT中，在函数开头进行分组，每个系数的位置都变化了不止一次，但实际上我们可以一次性完成系数最终位置改变。
考虑第 个元素 表示 系数的数组
，我们进行一种修改，保留原本偶数项相对顺序，将偶数项移到数组左半边，作为一组；奇数项同样保留原本它们之间的相对顺序，移到右半边，作为另一组。然后再在组内进行此修改直至一组内仅有两个（或一个）元素。
那么对于初始的 ，以下用
代称其内容以防混淆，将 用二进制表示为 ，显然第
次修改时
若 （ 为偶数），则 将在组内的左半边
若 （ 为奇数），则 将在组内的右半边
可以得出，在第 ...
