AC. 梦想

frank_c1

FFT初遇印象

发布于2015年12月12日 | 暂无评论 | 1,201阅读 | FFT,高等数学

快速傅里叶变换(Fast Fourier Transform),是一种极为著名的算法,以其巧妙、高效著称。在OI领域的应用主要是多项式乘法(特殊形式是高精度乘法)。多项式乘法似乎还与组合数学有很大的联系,所以对于OI选手,是一种非常有用的必备法宝。

为什么FFT做多项式乘法更快呢?FFT原是一种信号处理算法,可以将时域数据转换为频域数据。时域乘积,频域卷积;时域卷积,频域乘积。两者互相对称。多项式乘法是两个序列的卷积,如果将其转换到频域下做乘法,再转换回来,是不是可以更快一点呢?幸运的是,这确实可以。FFT包括DFT(离散傅里叶变换)和IDFT(逆离散傅里叶变换)两部分,两者均可以用O(N\log N)的时间复杂度实现。

首先给出DFT的公式:{X_k} = \sum\limits_{n = 0}^{N - 1} {{x_n} \cdot {e^{ - i2\pi kn/N}}} (k = 0,1,2...N - 1)

不要被复杂的数学描述吓到,我们来一步步分解。令{W_N} = {e^{ - i2\pi /N}},在N确定时,它是一个常数。那么DFT的公式可以改写为{X_k} = \sum\limits_{n = 0}^{N - 1} {{x_n} \cdot W_N^{nk}} 。观察一下,DFT实质上是一个N \times N的系数矩阵与长度为N的向量x的矩阵乘法,得到一个长度为N的向量X。那么根据公式就得到最朴素的O({N^2})算法。

公式中还有许多神奇的性质。首先普及一个常用的公式:{e^{i\theta }} = \cos \theta  + i\sin \theta ,这个公式解决了虚数指数幂的运算障碍。其次根据公式可以推导得{e^{2\pi i}} = 1。下面开始探究{W_N}的性质:

性质1:周期性 - W_N^{nk} = W_N^{n(N + k)}

性质2:对称性 - W_N^{nk} = W_N^{ - nk} ,证明只需要将式子展开后即可得到。

接下来是FFT的核心步骤:

{X_k} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_N^{2mk} + } \sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_N^{(2m + 1)k}}

用上述性质进行进一步化简,可以得到:

{X_k} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_{N/2}^{mk} + } W_N^k\sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_{N/2}^{mk}}


{X_{N/2 + k}} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_{N/2}^{mk} - } W_N^k\sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_{N/2}^{mk}}

这样就把原问题等价转化为两个子问题,是FFT中体现的分治策略。最后是将频域转回时域,IDFT公式:{X_k} = \frac{1}{N}\sum\limits_{n = 0}^{N - 1} {{x_n} \cdot {e^{i2\pi kn/N}}}

UOJ上有一道模板题。具体实现如下:

[BZOJ 2179] 高精度乘法模板~~

[BZOJ 2194] 卷积模板~~