FFT

前置知识

首先要知道关于 多项式 的一些知识。

其次要对复数有一些了解。

点值表示法

多项式 中,
已经知道了多项式乘法的朴素算法时间复杂度为 $ O(n^2) $ 。
原因在于多项式是用系数表示法定义的。

重新定义 n 次多项式 a 为满足
$ \forall k \in [0, n), a(x_k) = y_k $
的多项式,于是可以用 n 个点 $ (x_k, y_k) $ 表示这个多项式 a ,
这种表示方法叫点值表示法。

点值表示法有什么优点呢?

考虑用点值表示法的 n 次多项式 a, b 相乘的积 c ,满足:

$$ \forall k \in [0, n), cy_k = c(cx_k) = a(ax_k) * b(bx_k) = ay_k * by_k $$

发现这样按定义计算 c 的复杂度为 O(n) 。

于是 FFT 的基本思路诞生了:
把系数表示法的多项式 a, b 转换成点值表示法,
在点值表示法的定义下求出 a, b 的积 c ,
最后将 c 转换为系数表示法。

DFT

将系数表示法转换成点值表示法的方法就是 DFT 。

设要转换的是 $ n = 2^m $ 次多项式 A (次数不足用 0 补)。
利用到单位根的性质,
目标是求出 n 个形如 $ (w_n^k, A(w_n^k)) $ 的点值
( $ w_n $ 表示 n 次单位根)。

$ w_n^k $ 的性质:
在复平面里对应的向量的倾斜角 x 为 $ 2 \pi \frac{k}{n} $ ,
根据欧拉公式,其值为

$$ w_n^k = e^{x i} = cos(x) + i * sin(x) \;, \; x = 2 \pi \frac{k}{n} $$

考虑按次数的奇偶将 A 分成两个多项式 A1, A2 。

$$ A1(x) = \sum_{k=0}^{n/2} a_{2k+1} x^{2k+1} = x \sum_{k=0}^{n/2} a_{2k+1} x^k = x S1(x^2) $$

$$ A2(x) = \sum_{k=0}^{n/2} a_{2k} x^{2k} = \sum_{k=0}^{n/2} a_{2k} x^k = S2(x^2) $$

那么有 $ A(x) = A1(x) + A2(x) = x S1(x^2) + S2(x^2) $ 。

考虑分治处理,假设已经分治求出 S1, S2 在 $ w_{n/2}, w_{n/2}^2, w_{n/2}^3, …, w_{n/2}^{n/2}$
的点值。那么根据 A 与 S1, S2 的关系可以求出 A 在
$ w_{n/2}^{1/2}, w_{n/2}^{2/2}, w_{n/2}^{3/2}, …, w_{n/2}^{n/4} $ 的点值。

根据单位根的性质有 $ w_{n/2}^k = w_n^{2k} $ ,
那么相当于直接求出了 A 在
$ w_n, w_n^2, w_n^3, …, w_n^{n/2} $ 的点值:

$$ A(w_n^k) = w_n^k S1(w_{n/2}^k) + S2(w_{n/2}^k) $$

这只解决了一半,也就是 k 在 1 到 n / 2 的点值,
考虑 用奇技淫巧 求出 k 在 n / 2 + 1 到 n 的点值。
单位根的性质可以给出一个奇技淫巧:
$ w_n^{n/2+k} = -w_n^k $ ,那么就有:

$$ A(w_n^{n/2+k}) = w_n^{n/2+k} S1(w_{n/2}^{n/2+k}) + S2(w_{n/2}^{n/2+k}) = – w_n^k S1(w_{n/2}^k) + S2(w_{n/2}^k) $$

Ojbk, 分治过程完成。

IDFT

将点值表示法转换成系数表示法的方法就是 IDFT 。

贴个结论:
IDFT 的过程相当于 DFT 的过程中把所有单位根沿 x 轴对称得出的结果在最后除以 n 。

原因不详
可以去膜拜一下 Miskcoo


2 条评论

zrz · 2019年8月18日 下午4:52

公式炸了

多项式运算 – Kewth's blog · 2019年1月28日 下午10:01

[…] $ O(n cdot log_2n) $ 的 FFT 或 NTT […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注