FFT（快速傅里叶变换）

数学与数论 · 蝶形网络 · 多项式乘法的加速器

乘法为什么会快

两个多项式相乘，系数表示下是卷积——每项两两相乘，O(n²)。换个表示法：一个 n 次多项式由 n+1 个点值唯一确定（两点定一线的推广），而点值表示下乘法只要逐点相乘，O(n)！于是乘法变成三部曲：取点值（DFT）→ 逐点相乘 → 变回系数（IDFT）。瓶颈只剩「取点值」——随便取 n 个点各代入一次还是 O(n²)，好在取样点可以挑：FFT 挑的是单位根。

单位根与蝶形

ω = e^−2πi/n 的幂次均匀分布在单位圆上，自带对称：ω^k+n/2 = −ω^k。按奇偶次项把多项式劈成两半，n 点变换就折叠成两个 n/2 点变换加 O(n) 次合并——递归 log n 层。迭代版先做位反转重排（递归的偶奇分组层层展平后，第 i 个位置放的是下标「二进制倒着读」的元素），然后逐层跑蝶形：

蝶形单元：(u, v) → (u + ωv, u − ωv)——一次乘法同时产出「和」「差」两个点值。
第 1 层相邻配对（跨度 1）、第 2 层跨度 2、第 3 层跨度 4……每层配对跨度翻倍、共 log n 层、每层 n/2 个蝶形——总计 O(n log n)。下图连线旁的 ×ω 就是该蝶形的旋转因子。

多项式乘法的困境：系数表示下乘法是卷积 O(n²)；换成「点值表示」（在 n 个点上的取值）乘法只要逐点相乘 O(n)——贵在取点值（DFT）本身。FFT 的妙招：取样点用单位根 ω 的幂（ω = e^(-2πi/8)），它的对称性能把变换反复对折。输入：1+2x+3x²+4x³ 补零到 8 点

1function fft(a: Complex[]): Complex[] {
const n = a.length;                          // n 是 2 的幂
const A = new Array(n);
for (let i = 0; i < n; i++) A[i] = a[bitRev(i)];   // 位反转重排
for (let L = 2; L <= n; L *= 2) {
  const half = L / 2;
  const w0 = expI(-2 * Math.PI / L);         // 本层单位根 ω_L
  for (let st = 0; st < n; st += L) {
    let w = ONE;
    for (let k = 0; k < half; k++) {
      const u = A[st + k];
      const v = mul(A[st + k + half], w);
      A[st + k] = add(u, v);                 // 蝶形：和
      A[st + k + half] = sub(u, v);          // 蝶形：差
      w = mul(w, w0);
    }
  }
}
return A;                                    // O(n log n)
20}

输入: [1, 2, 3, 4, 0, 0, 0, 0]
目标: 8 点 DFT，只用 O(n log n)

从 FFT 到 NTT

逆变换（IDFT）用同一套蝶形，只把 ω 换成共轭、结果除以 n——所以整条乘法流水线就是「两次 FFT + 一次逐点乘」。浮点误差敏感的场景（大数乘法要精确整数）有孪生版 NTT：在模素数域里用原根替代单位根，蝶形结构一模一样。与快速幂的「平方折半」、双调排序的比较器网络（本页画布正来自它）一样，都是「分治对折」的形状——把 n 的问题反复对折到 log n 层，是这一族算法共同的骨架。