快速 Fourier 变换

FFT 不是一种新的变换，而是利用单位根的对称性快速计算离散 Fourier 变换。从系数表示切换到单位根上的点值表示后，多项式乘法变成逐点乘法；把偶数次与奇数次系数拆开后，在 $n$ 次单位根上的两个半规模求值可复用，因为 ${\omega }_n^{k+n/2}=-{\omega }_n^k$，而单位根平方后又折半。递归由此把 $n^2$ 次直接求和降为 $n\log n$，本质是结构化线性变换的分治。

多项式乘法先把两个系数序列补零到长度至少 $n+m-1$ 的方便规模，分别做 DFT，逐点相乘，再做逆变换。长度 $4$ 时，偶系数多项式与奇系数多项式各只需在两个平方根单位点求值，再通过蝶形合并四个结果。

DFT 的代数定义与 FFT 的 $O(n\log n)$ 运算计数都以精确算术为基准；机器实现遵循标准浮点运算模型公理库浮点算术标准误差模型Standard floating-point arithmetic model以每次基本运算的小相对扰动和 gamma 记号组织多步浮点误差分析。时，每个蝶形还会引入舍入误差。整数卷积需四舍五入、拆位或改用满足单位根条件的数论变换（NTT）；补零长度不足以覆盖卷积结果次数时会得到循环卷积。经典 radix-2 实现要求长度为二次幂，其他长度可用 mixed-radix 或 Bluestein 等方法。DFT 定义中的正负号与归一化约定也必须前后一致。

FFT 结合序列公理库序列Sequence以自然数为定义域的函数。、复数公理库复数Complex number形如 a+bi 的数，按坐标规则构成实数域的二次扩张。与分治法公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。，用于快速多项式乘法、信号频谱、大整数乘法、生成函数算法和字符串相关计算；数论变换则在有限域中复现单位根结构，避免浮点误差。它计算的是有限循环群上的 DFT；Fourier 级数公理库Fourier 级数Fourier series · 傅里叶级数把周期函数投影到整数频率的正交指数基上所得的离散频谱展开。处理周期函数的无穷展开，Fourier 变换公理库Fourier 变换Fourier transform · 傅里叶变换把非周期函数分解为连续频率成分，并将卷积和平移不变算子转为频域乘法。处理非周期函数的连续频率积分，三者共享频率分解思想，却有不同的对象、归一化与收敛问题。

FFT 的卷积接口还通向子集卷积公理库子集卷积subset convolution · fast subset convolution对一个集合的互补子集划分求卷积，并用按秩 zeta 与 Möbius 变换加速全部子集答案。，但后者的“加法”发生在子集并分拆上，需 Möbius/zeta 变换，不能直接把数组下标卷积公式照搬。超比较整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。有时使用字级打包、多项式评估或卷积子程序；这不表示一般 FFT 排序，也不绕过任意比较键的决策树下界，模型仍须保留有限字长与整数操作。