利用快速傅里叶变换(FFT)计算多项式乘法
作者:宋振华
摘要
本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的时间复杂度降低为??nlog2n?,以便在计算机上高效计算多项式乘法.
关键词:快速傅里叶变换、多项式乘法
目录
一、引言 二、算法概述 三、引理
1、多项式的表示
(1)系数表达形式 (2)点值表达形式 (3)插值
2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式
(1)单位复数根
(2)离散傅里叶变换(DFT)
(3)通过快速傅里叶变换(FFT)计算向量y
3、利用FFT计算逆DFT,将结果的点值表达形式化为系数表达形式
(1)在单位复数根处插值 (2)利用FFT计算逆DFT
四、算法具体流程
五、算法的实际应用:计算大整数乘法 六、参考文献
一、引言
基于FFT的离散傅里叶变换(DFT)技术,是当今信息传输、频谱分析等领域中最重要的数学工具之一.在计算机编程中,我们经常需要计算两个多项式函数的乘积.对于两个n次多项式函数,计算其乘积最直接方法所需时间为?n2.本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的时间复杂度降低为??nlog2n?,以便在计算机上高效执行.
二、算法概述
通过FFT进行离散傅里叶变换,将两个多项式由系数表达形式转化为点值表达形式.将这2个点值表达形式的多项式相乘,得到结果的点值表达形式.最后利用FFT做DFT的逆,得到结果的系数表达形式.
三、引理
1、多项式的表示
(1)系数表达
对于次数为n的多项式A?x???aixi,其系数表达是一个由系数组成
i?0n??的向量a??a0,a1,...,an?.
T考虑用系数形式表示、次数为n的多项式A(x)、B(x)的乘法运算. 记C(x)?A(x)B(x)??cix. 有ci??ajbi?j.可以看出,采取逐个计
ii?02nij?0算ci(0?i?2n,i?N)的方式进行求解,其时间复杂度为?(n2). (2)点值表达 a.定义:
一个次数为n的多项式A(x)的点值表达就是由一个有n个点值对组成的集合{(xi,yi)|0?i?n,i?N,yi?A(xi)},使得对于k?0,1,2,...,n,所有的xk各不相同.
b.点值表达下多项式乘法
对于n次多项式A(x),B(x),设其点值表达式分别为:
A(x):{(x0,y0),(x1,y1),(x2,y2),?,(xn,yn)},
,，,,B(x):{(x0,y0),(x1,y1),(x2,y2),?,(xn,yn)}
设C(x)?A(x)B(x),
由于C(x)的次数为2n,因此必须对A(x)和B(x)的点值表达式进行扩展,使每个多项式都包含2n?1个点值对.给定A,B的扩展点值表达:
A(x):{(x0,y0),(x1,y1),(x2,y2),?,(x2n,y2n)},
,，,,B(x):{(x0,y0),(x1,y1),(x2,y2),?,(x2n,y2n)}.
则C(x)的点值表达形式为:
,，,,{(x0,y0y0),(x1,y1y1),(x2,y2y2),?,(x2n,y2ny2n)}.
因此,计算C(x)点值表达式的时间复杂度为?(n).
` (3)插值
求值运算的逆(从一个多项式的点值表达形式确定其系数表达形式)称为插值.下面将证明,n个点求值运算与插值运算是定义完备的互逆运算.
a.多项式的点值表达可以唯一确定多项式的系数表达形式.
多项式的点值表达等价于矩阵方程:
2n?1x0x0??a0??y0??x0??????2n?1x1x1?x1??a1??y1??1xx2?xn??a?=?y?. (3-1-3-a)
222??2??2????????????????2n??a??y?1xx?xnnn??n??n??
记系数矩阵为V,由Vandermonde行列式可知,V?0?i?j?n??x?x?.
ij而?i,j?N,0?i,j?n,i?j,有xi?xj,因此V?0,即V可逆.
因此对于给定点值表达,我们能够唯一确定系数表达式,且
a?V?1y.
b.对于次数为n的多项式函数A?x?,插值算法基于如下Lagrange公式:
?(x?x)A?x???y.
??x?x?njj?kkk?0kjj?k (3-1-3-b)
容易验证,Lagrange公式的计算复杂度为?(n2).
因此,n个点求值运算与插值运算是定义完备的互逆运算,它们将多项式的系数表达与点值表达进行相互转化.
2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式
(1)单位复数根
n次单位复数根是满足?n?1的复数?.n次单位复数根恰好有n个:对于k?0,1,...,n?1,这些根是e
i2?ni2?kn
.由Euler公式ei??cos????isin???可
知,这n个单位复数根均匀地分布在以复平面原点为圆心的单位圆圆周上.?n?e称为主n次单位根,所有其他n次单位根都是?n的幂次.
012n?1,?n,?n,...,?n在乘法意义下构成一个群,n个n次单位复数根?n该群与群?Zn,?n?同构.由此,可以得到如下推论:
a.?n?0,k?0,d?0,有?*dkdn?ei2?dkdn?ei2?knk. ??n
(3-2-1-a) (3-2-1-b)
b.?n?2k,k?N,???2??1.
n2n
ni2i2)|0?i?,i?N}. c.若n?2k,k?N*,{(?n)|0?i?n,i?N}={(?n/22(3-2-1-c)
对推论c的证明:
k2???nk//22.所以对于k?N,0?k?n由a可知,?k?N,??n,有
2k?n/222k?n2kn2kk2(?n)??n??n?n??n?(?n).得证.
n?1i?0kd.?n?N,k?N且k不能被n整除,有??n*??n?0. (3-2-1-d)
对推论d的证明:
????i?0n?1knnknnk(?n)?1(?n)?1(1)k?1???k?0. kk?n?1?n?1?n?1(2)离散傅里叶变换(DFT)
对于n次多项式A(x)??aixi,
i?0n其系数形式为a?(a0,a1,?,an)T.
knn
(3-2-2-1) (3-2-2-2)
ki设yk?A(?)??ai?n ?1,0?k?n,k?N,
i?0则向量y?(y0,y1,?,yn)T
(3-2-2-3)
就是系数向量a?(a0,a1,?,an)T的离散傅里叶变换. (3)通过快速傅里叶变换(FFT)计算向量y.
对于n次多项式A(x)??aixi,不妨假设n?1?2p,p?N.对于n?1i?0n不为2的整数次幂的情况类似,此处不再讨论.
FFT采取了分治策略,采用A(x)中偶数下标与奇数下标的系数,分别定义两个新的
?0?n次多项式: 22n-12A(x)?a0?a2x?a4x???an?1x
?1?n-12, (3-2-3-1)
A(x)?a1?a3x?a5x???anx2. (3-2-3-2)
注意到A?0?(x)包含A所有偶数下标的系数,A?1?(x)包含A中所有奇数下标的系数,于是有:
A(x)?A?0?(x2)?xA[1](x2).
(3-2-3-3)
01n所以,求A(x)在?n?1,?n?1,...,?n?1处的值的问题转化为:
a.求次数为
n0212的多项式A[0](x),A[1](x)在点(?n?1),(?n?1),..., 2n2(?n?1)处的取值.
b.根据(2-2-3-3)综合结果.
根据(2-2-1-c),式(2-2-3-3)不是由n?1个不同值组成,而是仅由n?1n?1个次单位复数根所组成,每个根正好出现2次.因此,我们递归22n?1n?1n?1地对次数为的多项式A[0](x),A[1](x)在个次单位复数根处
222进行求值.这些子问题与原始问题形式相同,但规模变为一半.
下面确定DFT过程的时间复杂度.注意到除了递归调用外,每次调用需要枚举a?(a0,a1,?,an)T中所有元素,将a划分为a?0??{a0,a2,?an}、
a?1??{a1,a3,a5,?,an?1},分别与多项式A[0](x),A[1](x)相对应.其时间复杂度为?(n).
利用快速傅里叶变换(FFT)计算多项式乘法
