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)。下图连线旁的 ×ω 就是该蝶形的旋转因子。
第 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[] {
2 const n = a.length; // n 是 2 的幂
3 const A = new Array(n);
4 for (let i = 0; i < n; i++) A[i] = a[bitRev(i)]; // 位反转重排
5 for (let L = 2; L <= n; L *= 2) {
6 const half = L / 2;
7 const w0 = expI(-2 * Math.PI / L); // 本层单位根 ω_L
8 for (let st = 0; st < n; st += L) {
9 let w = ONE;
10 for (let k = 0; k < half; k++) {
11 const u = A[st + k];
12 const v = mul(A[st + k + half], w);
13 A[st + k] = add(u, v); // 蝶形：和
14 A[st + k + half] = sub(u, v); // 蝶形：差
15 w = mul(w, w0);
16 }
17 }
18 }
19 return A; // O(n log n)
20}
输入[1, 2, 3, 4, 0, 0, 0, 0]
目标8 点 DFT，只用 O(n log n)
1 / 9
从 FFT 到 NTT
逆变换（IDFT）用同一套蝶形，只把 ω 换成共轭、结果除以 n——所以整条乘法流水线就是「两次 FFT + 一次逐点乘」。浮点误差敏感的场景（大数乘法要精确整数）有孪生版 NTT：在模素数域里用原根替代单位根，蝶形结构一模一样。 与快速幂的「平方折半」、双调排序的比较器网络（本页画布正来自它）一样，都是「分治对折」的形状——把 n 的问题反复对折到 log n 层，是这一族算法共同的骨架。