在从多项式乘法到快速傅里叶变换中我们介绍了快速傅立叶变换的算法。由于在计算多项式乘法或者大整数乘法时,我们所使用的都是实数,而快速傅立叶变换并不仅适用于实序列,对于复序列也是可以计算的,这让我们考虑是否可以利用虚部来保存额外的信息而减少计算的次数。
事实上,对于实序列,其DFT是共轭对称的,也就是
,如果将两个实数序列
和
合并称为新的
,对其进行FFT,我们可以从中复原出分别对两个序列进行FFT的结果。也就是,可以通过两次FFT就进行多项式乘法的计算(原先是需要三次的)。
沿用其中的记号,先回忆一下离散傅里叶变换的公式。
考虑长度为的序列
及其
点离散傅里叶变换
\begin{equation} X(n) = \sum_{k=0}^{N - 1} x(k)\cdot\omega_N^{kn},~ n = 0, 1, \cdots, N - 1 \end{equation}
其中,即
次单位根。
现在来考虑和
之间的关系,我们用
或
来表示
的共轭
\begin{equation} X^*(n) = \sum_{k=0}^{N - 1} x^*(k)\cdot\omega_N^{-kn} = \sum_{k=0}^{N - 1} x^*(k)\cdot\omega_N^{k(N-n)} \end{equation}
这是因为
那么,对于实序列,,我们可以得到
。也就是说,实序列的DFT是共轭对称的。
现在来考虑两个实序列和
,其对应的DFT为
和
,定义新的序列
,其对应DFT为
,那么
\begin{equation} Z(n) = \dft{x(n) + i\cdot y(n)} = X(n) + i\cdot Y(n) \end{equation}
注意这里和
本身并不是一个实数,因此它们也不是
的实部和虚部,我们设
的实部和虚部分别为
和
。
\begin{equation} \begin{aligned} \overline{X(N - n) + i\cdot Y(N - n)} &= \overline{A(N - n) + i\cdot B(N - n)} \\ \Rightarrow X(n) - i\cdot Y(n) &= A(N - n) - i\cdot B(N - n) \end{aligned} \end{equation}
这样就可以得到
\begin{equation} \begin{aligned} 2X(n) &= [A(n) + A(N - n)] + i[B(n) - B(N - n)] \\ 2Y(n) &= [B(n) + B(N - n)] - i[A(n) - A(N - n)] \end{aligned} \end{equation}
这样,对于两个实序列的DFT可以只利用一次FFT以及一点额外的运算进行计算而不必分别计算两次FFT。
下面来考虑一个长度为 的实序列
。我们将其按照下标的奇偶分解为两个长度为
的序列
\begin{equation} \begin{aligned} x_1(n) &= x(2n)\\ x_2(n) &= x(2n + 1) \end{aligned} \end{equation}
现在可以利用刚刚的方法通过一次N点的FFT来计算它们分别的DFT序列和
,通过类似于FFT的办法将其合并
\begin{equation} \begin{aligned} X_1(n) + \omega_{2N}^n X_2(n) &= \sum_{k=0}^{N-1}x_1(k)\omega_N^{kn}+\omega_{2N}^n\sum_{k=0}^{N-1}x_2(k)\omega_N^{kn} \\ &= \sum_{k=0}^{N-1}x(2k)\omega_{2N}^{2kn}+\sum_{k=0}^{N-1}x(2k + 1)\omega_{2N}^{(2k+1)n} \\ &= X(n) \end{aligned} \end{equation}
这里只有前项,对于其余项可以利用共轭对称这个性质直接计算。
对于大整数乘法,我们也可以利用两个实序列DFT的快速算法进行计算,这样只需要两次FFT即可,下面我提供一个多项式乘法的代码(UOJ#34),FFT的模板是很久以前写的就别看了,可以看看下面处理的部分。