引言
多项式乘法是信号处理、密码学、大整数运算中的基础操作。朴素的 O(n²) 算法在多项式次数较高时效率低下。快速傅里叶变换（Fast Fourier Transform, FFT）通过巧妙地将系数表示转换为点值表示，再利用分治策略在 O(n log n) 时间内完成乘法，是算法史上最重要的突破之一。本文将用 Java 完整实现 FFT，并演示多项式乘法的加速过程。
核心思想
1. 多项式的两种表示
- 系数表示：
A(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ - 点值表示：
n+1个不同点(x₀, A(x₀)), (x₁, A(x₁)), ...唯一确定多项式
点值表示下的乘法仅需 O(n)：对应点相乘即可！
2. 单位复根
选择特殊的 n 次单位复根 ωₙ = e^(2πi/n) 作为求值点，其具有消去引理和折半引理，使分治成为可能：
ωₙ^(k + n/2) = -ωₙ^k(ωₙ^k)² = ωₙ/2^k
3. FFT 与 IFFT
- FFT：将系数表示转为点值表示（求值），
O(n log n) - IFFT：将点值表示转回系数表示（插值），
O(n log n)
完整 Java 实现
/**
* FFT 快速傅里叶变换实现
* 支持多项式乘法（卷积）
*/
public class FFT {
/**
* 复数类
*/
static class Complex {
double real, imag;
Complex(double real, double imag) {
this.real = real;
this.imag = imag;
}
Complex add(Complex o) {
return new Complex(real + o.real, imag + o.imag);
}
Complex sub(Complex o) {
return new Complex(real - o.real, imag - o.imag);
}
Complex mul(Complex o) {
return new Complex(
real * o.real - imag * o.imag,
real * o.imag + imag * o.real
);
}
Complex div(double d) {
return new Complex(real / d, imag / d);
}
@Override
public String toString() {
return String.format("%.2f%+.2fi", real, imag);
}
}
/**
* 位逆序置换：将数组按二进制位反转重新排列
* 例如 n=8 时，索引 3 (011) -> 6 (110)
*/
private static void bitReverseSwap(Complex[] a, int n) {
int j = 0;
for (int i = 1; i < n; i++) {
int bit = n >> 1;
for (; j >= bit; bit >>= 1) {
j -= bit;
}
j += bit;
if (i < j) {
Complex temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
/**
* FFT 核心：迭代实现 Cooley-Tukey 算法
* @param a 复数数组（会被原地修改）
* @param n 长度（必须是 2 的幂）
* @param invert true 表示 IFFT（逆变换）
*/
public static void fft(Complex[] a, int n, boolean invert) {
bitReverseSwap(a, n);
for (int len = 2; len <= n; len <<= 1) {
// 单位复根：ω_len = e^(2πi/len)
double angle = 2 * Math.PI / len * (invert ? -1 : 1);
Complex wlen = new Complex(Math.cos(angle), Math.sin(angle));
for (int i = 0; i < n; i += len) {
Complex w = new Complex(1, 0);
for (int j = 0; j < len / 2; j++) {
Complex u = a[i + j];
Complex v = a[i + j + len / 2].mul(w);
a[i + j] = u.add(v); // 蝴蝶操作：上分支
a[i + j + len / 2] = u.sub(v); // 蝴蝶操作：下分支
w = w.mul(wlen); // 递推计算 ω 的幂
}
}
}
// IFFT 时需要除以 n
if (invert) {
for (int i = 0; i < n; i++) {
a[i] = a[i].div(n);
}
}
}
/**
* 多项式乘法（卷积）：计算 a * b
* @param a 多项式 A 的系数数组
* @param b 多项式 B 的系数数组
* @return 结果多项式的系数数组
*/
public static long[] multiply(int[] a, int[] b) {
int need = a.length + b.length - 1;
int n = 1;
while (n < need) n <<= 1; // 找到最小的 2 的幂
Complex[] fa = new Complex[n];
Complex[] fb = new Complex[n];
for (int i = 0; i < n; i++) {
fa[i] = new Complex(i < a.length ? a[i] : 0, 0);
fb[i] = new Complex(i < b.length ? b[i] : 0, 0);
}
// FFT: 系数 -> 点值
fft(fa, n, false);
fft(fb, n, false);
// 点值相乘
for (int i = 0; i < n; i++) {
fa[i] = fa[i].mul(fb[i]);
}
// IFFT: 点值 -> 系数
fft(fa, n, true);
// 四舍五入取整（处理浮点精度误差）
long[] result = new long[need];
for (int i = 0; i < need; i++) {
result[i] = Math.round(fa[i].real);
}
return result;
}
/**
* 大整数乘法：利用 FFT 实现
* 将数字按位拆分为多项式系数，相乘后再处理进位
*/
public static String bigMultiply(String num1, String num2) {
int n1 = num1.length(), n2 = num2.length();
int[] a = new int[n1];
int[] b = new int[n2];
// 反转存储（低位在前）
for (int i = 0; i < n1; i++) {
a[i] = num1.charAt(n1 - 1 - i) - '0';
}
for (int i = 0; i < n2; i++) {
b[i] = num2.charAt(n2 - 1 - i) - '0';
}
long[] prod = multiply(a, b);
// 处理进位
long carry = 0;
for (int i = 0; i < prod.length; i++) {
long cur = prod[i] + carry;
prod[i] = cur % 10;
carry = cur / 10;
}
// 处理最高位进位
StringBuilder sb = new StringBuilder();
while (carry > 0) {
sb.append(carry % 10);
carry /= 10;
}
// 去除前导零，逆序输出
int idx = prod.length - 1;
while (idx > 0 && prod[idx] == 0) idx--;
for (int i = idx; i >= 0; i--) {
sb.append(prod[i]);
}
return sb.toString();
}
public static void main(String[] args) {
// 测试多项式乘法
int[] a = {1, 2, 3}; // 1 + 2x + 3x²
int[] b = {4, 5}; // 4 + 5x
long[] res = multiply(a, b);
System.out.print("多项式乘法结果: ");
for (long x : res) System.out.print(x + " ");
System.out.println(); // 4 13 22 15 -> 4 + 13x + 22x² + 15x³
// 验证：
// (1 + 2x + 3x²)(4 + 5x) = 4 + 5x + 8x + 10x² + 12x² + 15x³
// = 4 + 13x + 22x² + 15x³ ✓
// 测试大整数乘法
String num1 = "123456789";
String num2 = "987654321";
String product = bigMultiply(num1, num2);
System.out.println("大整数乘法: " + num1 + " * " + num2 + " = " + product);
System.out.println("验证: " + (Long.parseLong(num1) * Long.parseLong(num2)));
}
}
复杂度分析
| 操作 | 朴素算法 | FFT 算法 | 加速比 |
|---|---|---|---|
| 多项式乘法 | O(n²) | O(n log n) | ~n / log n 倍 |
| 大整数乘法 | O(n²) | O(n log n) | ~n / log n 倍 |
当 n = 10^5 时，FFT 仅需约 10^5 × 17 ≈ 170万 次运算，而朴素算法需要 10^10 次运算，差距超过 5000 倍。
关键理解：蝴蝶操作
FFT 的核心是蝴蝶操作（Butterfly Operation）：
a[i+j] = u + v
a[i+j+len/2] = u - v
其中 u 和 v 分别来自上、下两半部分。这种结构像蝴蝶翅膀一样对称，使得分治的合并过程可以在原地完成，无需额外数组。
数值稳定性
由于涉及浮点运算，IFFT 后需要进行四舍五入。对于整数系数多项式，只要中间值不超过 2^53（Java double 的精确整数范围），结果就是准确的。对于更大的数，应使用 NTT（数论变换）替代。
应用场景
- 信号处理：时域卷积 ↔ 频域乘积
- 大整数乘法：Karatsuba 和 Toom-Cook 的进阶替代
- 字符串匹配：带通配符的模式匹配
- 概率分布：两个独立随机变量之和的分布（卷积）
- 图像处理：快速卷积滤波
总结
FFT 将多项式乘法从 O(n²) 降至 O(n log n)，其威力源于三个关键洞察：点值表示的乘法简洁性、单位复根的特殊代数性质、以及分治合并的蝴蝶操作。掌握 FFT，意味着你掌握了处理大规模卷积问题的核武器，也是深入理解现代信号处理与密码学的必备基石。
