Day: April 25, 2015

概述

计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是 $\mathcal O(n^2)$ 的，还有一种分治乘法，需要新东西吗？play daisy slots 测试您的数学能力。 可以做到 $\mathcal O(n^{\log_23})$ 时间计算（可以看这里）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT）如何在 $\mathcal O(n\log n)$ 的时间内计算出两个多项式的乘积。另外，存在只需要两次快速傅立叶变换就可以计算大整数乘法的方法，具体见实序列离散傅里叶变换的快速算法

准备知识

这里介绍一些后面可能会用到的知识（主要是关于多项式、卷积以及复数的），如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧

多项式

简单来说，形如 $a_0+a_1X+a_2X^2+\cdots+a_nX^n$ 的代数表达式叫做多项式，可以记作$P(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^n$，$a_0, a_1, \cdots, a_n$ 叫做多项式的系数，$X$ 是一个不定元，不表示任何值，不定元在多项式中最大项的次数称作多项式的次数

多项式的系数表示法

像刚刚我们提到的那些多项式，都是以系数形式表示的，也就是将 $n$ 次多项式 $A(x)$ 的系数 $a_0, a_1, \cdots, a_n$ 看作 $n+1$ 维向量 $\vec a=(a_0,a_1,\cdots,a_n)$，其系数表示（coefficient representation）就是向量 $\vec a$

多项式的点值表示法

如果选取 $n+1$ 个不同的数 $x_0, x_1, \cdots, x_n$ 对多项式进行求值，得到 $A(x_0), A(x_1), \cdots, A(x_n)$，那么就称 $\{\left(x_i, A(x_i)\right) : 0 \leq i \leq n, i \in \mathbb Z\}$ 为多项式 $A(x)$ 的点值表示（point-value representation）

多项式 $A(x)$ 的点值表示不止一种，你只要选取不同的数就可以得到不同的点值表示，但是任何一种点值表示都能唯一确定一个多项式，为了从点值表示转换成系数表示，可以直接通过插值的方法

复数

后面提到的 $i$，除非作为 $\sum$ 求和的变量，其余的都表示虚数单位 $\sqrt{-1}$

单位根

$n$ 次单位根是指能够满足方程 $z^n=1$ 的复数，这些复数一共有 $n$ 个它们都分布在复平面的单位圆上，并且构成一个正 $n$ 边形，它们把单位圆等分成 $n$ 个部分

根据复数乘法相当于模长相乘，幅角相加就可以知道，$n$ 次单位根的模长一定是 $1$，幅角的 $n$ 倍是 $0$

这样，$n$ 次单位根也就是

$$e^{\frac{2\pi ki}{n}}, k = 0, 1, 2, \cdots, n - 1$$

再根据欧拉公式

$$e^{\theta i}=\cos\theta + i\sin\theta$$

就可以知道 $n$ 次单位根的算术表示

如果记 $\omega_n=e^{\frac{2\pi i}{n}}$，那么 $n$ 次单位根就是 $\omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1}$

多项式的乘法

给定两个多项式 $A(x), B(x)$

$$A(x) = \sum_{i=0}^na_ix^i = a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 \\ B(x) = \sum_{i=0}^nb_ix^i = b_nx^n+b_{n-1}x^{n-1}+\cdots+b_1x+b_0$$

将这两个多项式相乘得到 $C(x) = \sum_{i=0}^{2n}c_ix^i$，在这里

$$c_i=\sum_{j+k=i,0\leq j,k\leq n}a_jb_kx^i$$

如果一个个去算 $c_i$ 的话，要花费 $\mathcal O(n^2)$ 的时间才可以完成，但是，这是在系数表示下计算的，如果转换成点值表示，知道了 $A(x), B(x)$ 的点值表示后，由于只有 $n+1$ 个点，就可以直接将其相乘，在 $\mathcal O(n)$ 的时间内得到 $C(x)$ 的点值表示

如果能够找到一种有效的方法帮助我们在多项式的点值表示和系数表示之间转换，我们就可以快速地计算多项式的乘法了，快速傅里叶变换就可以做到这一点

Read More