大数乘法—多项式与快速傅里叶变换

2019-01-15 本文已影响0人 PrivateEye_zzy

本章涉及知识点：

1、多项式乘法的时间复杂度

2、多项式的表示：系数

3、多项式的表示：点值

4、复数的表示

5、单位复数根

6、单位复数根的性质—消去引理

7、单位复数根的性质—折半引理

8、离散傅里叶变换：DFT和IDFT

9、快速傅里叶变换：FFT

10、FFT求解多项式乘法的步骤

11、python编程实战FFT大数乘法

12、结果分析

一、多项式乘法的时间复杂度

数学中，我们可以将任意一个n位的数字写为一个n-1次多项式，如456可以写为

数字转为多项式

即可抽象定义出以x为变量的多项式函数A(x)

多项式函数

其中aj表示：长度为N-1位数字的第j为数字

例如要计算456 * 123 = ？，则我们用多项式A(x)和B(x)来分别表示其各自的数字，C(x)表示两个多项式的乘积

两个数字的多项式

由乘法的运算规则，两个数的每一位数字都要与另一个数的每一位相乘，最后相加同一位上所有的数字，得到乘积中该位的数字，即

多项式乘法

将x=10为基带入结果，即可以得到456 * 123 = 4 * 10**4 + 13 * 10**3 + 28 * 10**2 + 27 * 10 + 18 = 56088

我们可以归纳出乘积C(x)的每一位数字的计算关系为

乘积数位的计算

其中cj表示：乘积数中的第j位的数字

则乘积多项式C(x)可以写为

乘积多项式

至此我们可以看到，由于受限于乘法运算自身的规则，计算两个多项式乘积（将数字转换为多项式）的时间复杂度为： $O(n^{2})$ ，当n很大的时候复杂度将非常高

那么需要研究的问题就是：有没有方法可以高效的提高多项式乘法复杂度呢？

二、多项式的表示：系数

为了降低多项式乘法的复杂度，我们首先需要了解几个数学知识

从多项式函数的定义，我们将所有系数视为系数向量，而由全部系数组成的向量a叫做该多项式的系数表达

系数表达

PS：乘积多项式C(x)的系数向量cj，也称输入向量a和b的卷积，记为

卷积运算

从之前的分析可知，要计算出乘积C(x)的每一个系数向量cj，需要的时间复杂度为 $O(n^{2})$

三、多项式的表示：点值

我们任意选取n个不同的自变量x带入多项式函数A(x)进行求值运算，将得到n个不同数值的y，即

求值运算

则多项式的点值表达就是由这n个数值点组成的集合

点值表达

因为可以选取任意n个不同点所构成的集合，所有一个多项式可以有很多不同的点值表达

我们把任意n个点构成的集合叫做点值表达的基

从点值表达的基入手，选取适当的xk来优化多项式乘法效率，为此，我们选取单位复数根作为多项式的基

四、复数的表示

复数的定义：设a，b为实数，则形如 $z = a + bi$ 的数称为复数，其中a称为实部，b称为虚部

PS：当a=0时，复数为纯虚数；当b=0时，复数可视为实数

将复数的实部与虚部的平方和的正平方根值称为该复数的模，即

复数的模

五、单位复数根

任意一个复数w，其n次幂的结果为1，就称复数w是n次单位复数根，即

n次单位复数根

可以看到，n次单位复数根有n个，其几何意义为：n个单位复数根均匀的分布在以复平面原点为圆心的单位圆上

n次单位复数根的几何意义

在几何意义的单位圆中，我们将圆周角 $2\pi$ 均分成n份，则 $\frac{2\pi}{n}$ 叫做单位根的幅角

由欧拉公式得

欧拉公式

我们定义 $w_{n}$ 表示一个n次单位根，则

主n次单位根

$w_{n}$ 又被称为主n次单位根，而其余 $w_{n}^{1}$ 、 $w_{n}^{2}$ 等叫做n次单位根的幂次，记为： $w_{n}^{k}$ ，则

n次单位根的幂次

可以很容易知道

n次单位根的性质

下面我们证明n次单位根的两个性质

六、单位复数根的性质—消去引理

设d>0为任何一个整数，则

消去引理

七、单位复数根的性质—折半引理

由

折半引理

则可以得到

折半引理

至此，可以看到通过消去和折半引理，我们将n的规模降低到了原来的一半

八、离散傅里叶变换：DFT和IDFT

回顾之前我们的多项式函数

多项式函数

我们将n次单位根的幂次项： $w_{n}^{0}，w_{n}^{1}，w_{n}^{2}，...，w_{n}^{n-1}$ 依次带入A(x)，则得到

离散傅里叶正变换

记向量 $y = (y_{0}, y_{1},..., y_{n-1})$ 是系数向量 $a = (a_{0}, a_{1},..., a_{n-1})$ 的离散傅里叶变换，也称离散傅里叶正变换（DFT）

则对应的离散傅里叶逆变换（IDFT）为

离散傅里叶逆变换

可以看到：

（1）DFT对应着多项式求值

（2）IDFT对应着插值，即求多项式的系数

九、快速傅里叶变换：FFT

由DFT定义可知，将 $w_{n}^{0}，w_{n}^{1}，w_{n}^{2}，...，w_{n}^{n-1}$ 全部依次带入A(x)计算出多项式的时间复杂度仍然是 $O(n^{2})$

此时我们就需要利用之前所讲的n次单位复数根的知识，将A(x)中的偶数下标和奇数下标的系数，分别用两个新的多项式A1(x)和A2(x)来表示，即

偶数下标的多项式

奇数下标的多项式

注意：A(x)的次数界为n，A1(x)的次数界为n/2，A2(x)的次数界也为n/2

则可以得到A(x)和A1(x)、A2(x)的关系为

多项式函数关系

我们将 $x=w_{n}^{k}$ 带入得，其中 $k=0,1,2,...,\frac{n}{2} - 1$

快速傅里叶变换1

至此，我们就得到了在 $[0, \frac{n}{2} - 1]$ 之间 $w_{n}^{k}$ 的所有求值

下面还需要计算 $[\frac{n}{2} , n-1]$ 之间的 $w_{n}^{k}$ 的值，根据折半引理，我们将 $x = w_{n}^{k + \frac{n}{2}}$ 带入得

快速傅里叶变换2

至此，我们就得到了 $[\frac{n}{2} , n-1]$ 之间 $w_{n}^{k}$ 的所有求值

观察上面两个式子，不难发现：

（1） $A(w_{n}^{k})$ 和 $A(w_{n}^{k + \frac{n}{2}})$ 的计算式子里只有一个常数项互为相反数

（2）在 $[0, \frac{n}{2} - 1]$ 之间枚举出 $A(w_{n}^{k})$ 后，就可以在 $O(1)$ 的时间里得到 $[\frac{n}{2} , n-1]$ 的 $A(w_{n}^{k + \frac{n}{2}})$

（3）原问题的规模缩小了一半（分治法的思想）

至此，我们利用数学中n次单位复数根的性质，将DFT优化为FFT（快速傅里叶正变换），即

快速傅里叶正变换

十、FFT求解多项式乘法的步骤

通过以上的研究，我们可以总结出使用FFT计算多项式乘法的时间复杂度

FFT计算多项式乘法的时间复杂度

FFT利用n次单位复数根和分治法的思想，将多项式乘法的时间复杂度由 $O(n^{2})$ 降低到了 $O(n\lg n)$

最后我们可以总结出求解多项式乘法的高效算法步骤为：

（1）加倍次数界：由分治法的思想，将两个多项式的次数界补全为2的幂次

（2）求值：通过FFT计算出两个多项式的点值表达，即2n次单位复数根的多项式函数取值

（3）逐点相乘：将两个多项式的点值依次相乘，得到相乘结果的点值

（4）插值：通过IDFT计算相乘结果的点值，得到相乘结果的每一个系数

十一、python编程实战FFT大数乘法