通过求值相乘
令 为整数,写 、;零多项式可用只有一项的列表 表示。其乘积的系数为
直接对所有系数对求和需 次算术运算。另一种方法是在选定的点上分别求值、逐点相乘,再恢复系数。单位根可让这些求值共用计算。我们先使用精确复数运算;实际的浮点表现是另一个问题。
选择二的幂 ,在两个系数列表末尾补零至长度 。
定义 10.1.1
(离散 Fourier 变换)
令 ,它是本原 次单位根。对长度为 的列表 ,离散 Fourier 变换定义为
这些是多项式 在 处的值。我们采用正指数约定;下面的反变换使用相反的符号。
反变换与循环卷积
定理 10.1.2
(反变换公式)
对每个长度为 的列表 ,
证明
(消失的等比和)
对整数 ,有限等比和满足
若 ,每一项都是 。否则由 的本原性,公比 不等于一,但它的 次方等于一,所以等比和 为零。把 乘以 并对 求和,得
因为对 ,只有 这一项保留下来。
定义 10.1.3
(循环卷积)
对长度为 的列表 ,它们的循环卷积是长度为 的列表
定理 10.1.4
(逐点乘积给出循环卷积)
若 是 与 的循环卷积,则对每个 都有 。因此对逐点乘积作反变换就返回 。若 是 的系数列表并补零至长度 ,则 就是普通乘积的系数,后面接着零。
证明
(指数相加,而且没有项绕回)
。由于 ,指数只取决于 ,把 的项合并,便得 。再由反变换公式从这些值恢复 。
对补零后的列表,当 时 ,当 时 ,所以非零项满足 。于是对 , 就是 ,因此 时 ,更高的位置 。
概念视角结构
循环卷积即模 $x^n$ - 1 的乘法
同一些对象还有第二种描述。 个点 恰是 的全部互异根,而模 时 化为 。所以 与 的循环卷积就是 的系数列表,而变换是用这个余式在 个根处的值来记录它的映射。值的逐点相乘就是余式的乘法,反变换公式则说明次数低于 的余式由这 个值唯一确定。混叠就是取余式这一步本身:次数达到或超过 的乘积并不等于它的余式。
因此补零并非可有可无。
反例模式
补零不足会使乘积折叠
一个看似合理的捷径,是只按输入长度选 ,再相信反变换会给出普通乘积。取 、,普通乘积为 。 与自身的循环卷积有 及 ,给出列表 : 的系数绕回常数位置,也就是 。修正方法是选 ;这里 就能把三个系数分开。
把变换分为偶数与奇数下标
假设 且为二的幂。把系数列表分成偶数下标与奇数下标两部分,定义 和 ,则
由于 是本原 次单位根,递归地在它的幂处求两个长度为 的列表的值,所得变换分别记为 和 。
定理 10.1.5
(基二 FFT)
设 为二的幂,,则
按这些公式递归计算变换,当 时 ;若 的幂已给出,或每层以线性工作量生成,当 时需 次算术运算。
证明
(对规模作归纳,再解递推式)
时, 的变换是 。设 、,按下标奇偶拆开定义中的和:
其中两个内和是以 为根的半长度列表的变换,由归纳假设它们正确。对下标 ,有 ,并且因 而 ,由此得到第二条公式。
两个半规模的子问题加上 的合并工作,给出 ,其解在 时是 。
证明透视
两条合并公式依赖什么
这个证明用到 的三个性质,各有分工。 是本原 次单位根,使两个半规模的问题与原问题同类,归纳才能进行。等式 使同一对半规模的值只需一次乘以 就产生两个输出 与 ,工作量因此减半,这正是对数因子的来源。最后, 须为二的幂,这样对半分可以一直进行到 ,不会剩下奇数规模。反变换重用同一递归,因为 也是本原 次单位根,最后再按反变换公式除以 。所以两次正变换、逐点乘法及一次反变换共需 次算术运算。
四点例题
例题 10.1.6
(用四个点相乘 1 + 2x 与 1 + x + )
取 、。乘积的次数至多为三,所以 足够。取 ,在 处的求值为:
| 列表 | 在 处 | 在 处 | 在 处 | 在 处 |
|---|---|---|---|---|
| 3 | ||||
| 3 | 1 | |||
| 逐点乘积 | 9 |
对最后一行套用反变换公式得 ,所以 。例如 的系数为 。乘积的次数至多为三,所以这个长度为四的变换不会把非零的乘积项折回较低的系数。
例题 10.1.7
(对 1 + 2x 的变换做一轮蝶形运算)
把 补零为 ,、。偶数项 与奇数项 以 做规模为二的变换:,。合并得
与上表第一行一致。两个半规模的值各被使用两次,一次用加号,一次用减号。
例题 10.1.8
(补零多于最低要求)
相乘 ,此时 ,。不小于 的最小二的幂是 ,而不是 。乘积为 ,所以反变换返回 ,后面有三个零。检验:, 处的逐点乘积是 ,而输出系数之和 。多出来的零没有坏处;只有输出太少才会使各项折叠。
成本与数值限制
算术运算次数的上界把复数加法与乘法视为常数成本。它不是任意大精确系数的比特复杂度界,也不保证浮点运算的结果精确。只有另有误差界保证每个计算出的实部系数与真实整数值相差不到 ,才能据此舍入来恢复整数系数;虚部的舍入误差也须处理。精确的模数变换或任意精度方法则需要各自的单位根、模数与重构条件。
常见错误
常见错误
(把正变换用两次,而不是求反变换)
把正变换公式直接拿来当反变换,既漏掉符号的改变,也漏掉因子 。对 ,列表 的变换是 。再套用一次正变换得 ,这是 的下标按模 反转后再乘以 ,并不是 。应使用 并除以 。
常见错误
(以为卷积必须用二的幂)
只要 ,反变换公式与循环卷积定理对每个 都成立。需要二的幂的,只是使变换变快的基二拆分。若 不是二的幂,定义仍然正确;只是上面的递归不能照原样套用。
练习
快速检查
(对 ,按正指数约定计算 的变换。)
取 ,使用 。
解答 · 答案
因 ,,所以变换为 。
快速检查
(解释为什么相乘次数至多为一及二的多项式时 足够,但 不一定足够。)
数一数乘积有多少个系数。
解答 · 答案
乘积的次数至多为 ,即四个系数,而 。若 ,次数为 和 的项会绕回次数 和 。对 ,长度为二的循环结果是 ,并不是乘积的系数。
快速检查
(若在四个单位根处 ,用反变换公式恢复 。哪个系数列表有此变换?)
对每个 计算 。
解答 · 答案
时,和为 。 时,它是 的非平凡幂的等比和,等于零。所以 ,即常数多项式 ,它在每个点处的值都是 。
快速检查
(用 的蝶形公式计算 的变换。)
偶数项是 ,奇数项是 。
解答 · 答案
偶数部分的变换是 ;奇数部分 在规模为二时变换为 。取 :、、、。所得列表 就是多项式 在四个单位根处的值。