算法合集之多项式乘法课件.ppt

1、引言引言 多项式是最基本的数学工具之一，由于其形式简单，且易于多项式是最基本的数学工具之一，由于其形式简单，且易于用计算机对其进行各种计算，在当今的社会中应用越来越广。不用计算机对其进行各种计算，在当今的社会中应用越来越广。不仅在像仅在像MapleMaple这样的数学软件中有着举足轻重的作用，在工程、这样的数学软件中有着举足轻重的作用，在工程、信息等诸多领域中都有着广阔的应用。信息等诸多领域中都有着广阔的应用。 2341ln(1)( 1)234nnxxxxxxn 35721sin( 1)3!5!7!(21)!nnxxxxxxn 2462cos1(1)2 !4 !6 !(2)!nnxxxxxn

2、下面我们给出几个多项式逼近的例子：下面我们给出几个多项式逼近的例子：多项式的基本运算多项式的基本运算 加法运算2012( )nnf xaa xa xa x0121*(*(*(* ) )nnaxaxaxax a 求值运算 乘法运算普通的多项式乘法运算普通的多项式乘法运算 多项式乘法是一个很常见的问题，在通常多项式乘法是一个很常见的问题，在通常的算法中，两个的算法中，两个 次多项式的乘法需要用次多项式的乘法需要用 的时间才能完成。的时间才能完成。n2()O n 让我们先来看一看这样的算法是如何进行的：让我们先来看一看这样的算法是如何进行的： 1110.nnnna xaxa xa1110.nnnnb

3、 xbxb xb*101 01 00 0.nnnna b xa b xab x a b121111110.nnnna b xab xa b xa b x. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2110.nnnnnnna b xa b xa b x2111 00 10010.()nnnnnnnnkkn kkkka b xab xab xa ba b xa b 在上面的过程中，似乎我们觉得这个算法并没有做任何多在上面的过程中，似乎我们觉得这个算法并没有做任何多余的事情，因为我们必须考虑每一组余的事情，

4、因为我们必须考虑每一组 , ,它们的乘积对最终它们的乘积对最终的结果都会产生影响。而且我们不能通过调整计算顺序从根本的结果都会产生影响。而且我们不能通过调整计算顺序从根本上降低算法时间复杂度，至多只能使其常数因子稍小一些。上降低算法时间复杂度，至多只能使其常数因子稍小一些。ija b 如果我们不能跳出以上思维的局限，我们就不可能在根本如果我们不能跳出以上思维的局限，我们就不可能在根本上降低算法的时间复杂度。上降低算法的时间复杂度。 让我们首先换一个角度来考察多项式。让我们首先换一个角度来考察多项式。多项式的点值表示法多项式的点值表示法 首先让我们来看多项式的另一种表示方法：点值表示法首先让我们

5、来看多项式的另一种表示方法：点值表示法, ,即用即用 （其中，（其中， 互不互不相同）来表示一个不超过相同）来表示一个不超过 次多项式。次多项式。 00112,211( ,),( , ),(),.,(,)nnx yx yx yxy( ),iiif xy x1n 给定一个多项式，要给出给定一个多项式，要给出n n组点值对最简单的方法是任组点值对最简单的方法是任选选 n n个互不相同的个互不相同的x xi i，依次求出多项式在这，依次求出多项式在这n n个点的值。个点的值。 用用n n个点值对也可以唯一确定一个不超过个点值对也可以唯一确定一个不超过n-1n-1次多项式，次多项式，这个过程称之为这个

6、过程称之为插值插值。引理引理1 1（多项式插值的唯一性）（多项式插值的唯一性） 对于任意对于任意n n个点值对组成的集合个点值对组成的集合, , 其中其中 互不互不相同，则存在唯一的次数不超过相同，则存在唯一的次数不超过n-1n-1的多的多项式项式 ，满足，满足 001111(,),( ,),.(,)nnx yx yxy011,.,nxxx( )A x()kkyA x0,1,.,1kncontinue210121( ).nnA xaa xa xax(),(0,1,.,1)kkA yxkn210000021111112111111111nnnnnnnnayxxxayxxxayxxx 存在性存在性

7、：已知已知不妨记为不妨记为XA=Y1AX Y1?XX X是范德蒙矩阵，利用行列式的变换可得是范德蒙矩阵，利用行列式的变换可得该矩阵的行列式的值为该矩阵的行列式的值为 ()0kjjkxx因此因此X X有逆矩阵有逆矩阵 。1X唯一性：唯一性： 若两个函数次数不超过若两个函数次数不超过n-1n-1次的多项式次的多项式 均符合题意，则多项式均符合题意，则多项式 有有n n个根，个根， 且且 为不超过为不超过n-1n-1次的多项式，所以次的多项式，所以 , , 即即 。 ( ), ( )f x g x( )( )( )r xf xg x( )r x( )0r x ( )( )fxg xback点值多项式

8、的乘法点值多项式的乘法 ( )( )* ( )r xf xg x)(*)()(iiixgxfxr因此：因此： 适当的利用点值表示可以使适当的利用点值表示可以使多项式的乘法可以在线性时间内完成！多项式的乘法可以在线性时间内完成！( , )iix r( ,)iixf( ,)iix g*iiirfg 因为因为f(x)g(x)f(x)g(x)的次数为的次数为n-1n-1，r(x)r(x)的次的次数为数为2n-2,2n-2,因此确定因此确定r(x)r(x)需要需要2n-12n-1个点值对，个点值对，而现在我们只有而现在我们只有n n个点值对。个点值对。 我们可以通过对我们可以通过对f(x)f(x)与与g

9、(x)g(x)的点值对个数的点值对个数的的 扩充来解决这个问题，即将扩充来解决这个问题，即将f(x),g(xf(x),g(x）的）的点值对在一开始就取为点值对在一开始就取为2n-12n-1。利用点值表示法改善多项式系数利用点值表示法改善多项式系数表示法的乘法表示法的乘法 下面让我们来看一看我们是否能够利用点值表示法在计下面让我们来看一看我们是否能够利用点值表示法在计 算多项式乘法时的线性时间来提高系数表示法的多项式乘算多项式乘法时的线性时间来提高系数表示法的多项式乘 法的速度。法的速度。 为了做到这一点，我们需要做：为了做到这一点，我们需要做： 将多项式由系数表示法转化为点值表示法将多项式由系

10、数表示法转化为点值表示法( (点值过程）点值过程） 利用点值表示法完成多项式乘法利用点值表示法完成多项式乘法 将点值表示法再转化为系数表示法将点值表示法再转化为系数表示法（插值过程）（插值过程） 其中第二步只需要线性时间。问题的关键转化为第一其中第二步只需要线性时间。问题的关键转化为第一 第三步。第三步。continue2continue1continue31.1.由系数表示法转化为点值表示法。由系数表示法转化为点值表示法。（点值过程）（点值过程） ( )iixf x12310( )(.()*).)*inininif xaxaxaaxa 注意！注意！x x0 0,x,x1 1, ,x,xn-1

11、n-1是由我们自己选择的，我们可以充是由我们自己选择的，我们可以充分利用这一点通过适当的选择使转化过程降为分利用这一点通过适当的选择使转化过程降为O(n log n)O(n log n)。 这里我们选择这里我们选择1 1的的n n次单位根作为次单位根作为x x0 0,x,x1 1, ,x,xn-1n-1，即即 011,.,nnnn222cossin.kiknnkkeinn其中其中(0,1,.,1)in引理引理2 2：对任何整数：对任何整数n=0,k=0,j0,n=0,k=0,j0,成立：成立：22kknn证明：证明：222 *22 *222cossincossin22kknnkkkkiinnn

12、n折半定理折半定理注意到，注意到， 中包含了中包含了f f中所有偶下标的系数，而中所有偶下标的系数，而 中包含了中包含了f f中所有奇下标的系数。中所有奇下标的系数。12220 0.)(nnxaxaaxf12131 1 .)(nnxaxaaxf0f1f)(*)()(2 1 20 xfxxfxf并记并记求求 与与 在点在点 的值。的值。 )(0 xf)(1xf212120)(,.,)( ,)(nnnn1011().()kkknnnnnfaaa问题：问题：求求0,1,.,1kn设设n n为偶数（否则可以通过添加高次零项使为偶数（否则可以通过添加高次零项使n n化为偶数）。化为偶数）。另一方面，由折

13、半定理：另一方面，由折半定理：02121 2011/2/2/2() ,() ,.,(),.,nnnnnnnn01/2 10/2 1/2/2/2/2/2,.,.,nnnnnnn 并不是并不是n n个不同的数，而个不同的数，而是仅由是仅由1 1的的n/2n/2次单位根组成，每个根恰好出现次单位根组成，每个根恰好出现2 2次次。 212120)(,.,)( ,)(nnnn 由此可以看到子问题与原问题形式相同，但由此可以看到子问题与原问题形式相同，但规模缩小一半，这启示我们可以利用分治的思想规模缩小一半，这启示我们可以利用分治的思想通过递归来解决这个问题。通过递归来解决这个问题。 递归算法的具体实现过

14、程递归算法的具体实现过程递归边界条件递归边界条件Function transform(a:atype):y:ytypeFunction transform(a:atype):y:ytype；if n=1 then return a0递归预处理递归预处理 if odd(n) then begin inc(n);an-1:=0;end; 0022: ( ,.,);naa aa1131: ( ,.,);naa aa);(:00atransformy);(:11atransformy递归过程递归过程For k:=0 to n-1 do 利用利用0212( )( )*( )f xfxx fx计算计算01

15、/2/2()()*()kkkknnnnyyy可以证明，以上计算方法的时间复杂度为可以证明，以上计算方法的时间复杂度为O(n log n)O(n log n)。back2 2将点值表示法再转化为系数表示法将点值表示法再转化为系数表示法。（插值过程）（插值过程） 点值过程所解决的问题可以等效为一个矩阵方程：点值过程所解决的问题可以等效为一个矩阵方程： 00231112462(1)223693(1)3312(1)3(1)(1)(1)11111111111nnnnnnnnnnnnnnnnnnnnnnnnnnyayayayaya 插值过程是点值过程的逆运算。这个问题比前一个问题插值过程是点值过程的逆运算

16、。这个问题比前一个问题看起来更复杂，但事实上，通过适当的转化可以把这个问题看起来更复杂，但事实上，通过适当的转化可以把这个问题转化为前一个问题。转化为前一个问题。nYV A记为记为YA点值过程点值过程插值过程插值过程如果如果1nV存在存在1nAVY1nVnYV A引理引理3 3123(1)2462(1)13693(1)(1)2(1)3(1)(1)(1)1111111111nnnnnnnnnnnnnnnnnnnnnnnnnVn2312462(1)3693(1)12(1)3(1)(1)(1)111111111nnnnnnnnnnnnnnnnnnnnnnnnnV利用引理利用引理3 3，我们就可以很容

17、易的解决插值的问题，我们就可以很容易的解决插值的问题。 YA 可等效为矩阵方程：可等效为矩阵方程：00123(1)112462(1)223693(1)33(1)2(1)3(1)(1)(1)111111111111nnnnnnnnnnnnnnnnnnnnnnnnnnayayayaynay 因此，我们可以充分利用点值过程的方法求出多因此，我们可以充分利用点值过程的方法求出多项式的系数表达。项式的系数表达。 递归边界条件递归边界条件Function Function transform( a:atype transform( a:atype ):y:ytype ):y:ytype ；if n=1 t

18、hen return a0递归预处理递归预处理 if odd(n) then begin inc(n); an-1:=0; end; 0022: ( ,.,);naa aa1131: ( ,.,);naa aa);(:00atransformy);(:11atransformy递归过程递归过程For k:=0 to n-1 do 利用利用0212( )( )*( )f xfxx fx计算计算01/2/2()()*()kkkknnnnyyybacka:atypea:atypey:ytypey:ytypey0yn-1:=0;0022: (,.,);nyy yy1131: ( ,.,);nyy yy

19、00:();atransform y11:();atransform y01/2/2()()*()kkkknnnnaaa递归结束后再将递归结束后再将a a中每一个数除以中每一个数除以n n。多项式乘法的算法流程多项式乘法的算法流程问题：问题：f(x),g(x)f(x),g(x)是两个是两个n-1n-1次的多项式，已知次的多项式，已知f(x)g(x)f(x)g(x)的系数表示，求出的系数表示，求出r(x)=f(x)r(x)=f(x)* *g(x)g(x)的系数表示。的系数表示。算法流程：算法流程：1.1. 预处理：通过加入预处理：通过加入n-1n-1个值为个值为0 0的高价次数，使的高价次数，使

20、f(x)g(x)f(x)g(x)的次的次数增加到数增加到2n-22n-2。这是为了使点值对的个数足够能够唯一确定。这是为了使点值对的个数足够能够唯一确定r(x)r(x)。2. 2. 点值：利用分治的方法，通过函数点值：利用分治的方法，通过函数transformtransform求出求出f(x)f(x)与与g(x)g(x)在在1 1的的2n-12n-1次单位根处的值。次单位根处的值。 3. 3. 点乘：将点乘：将f(x),g(x)f(x),g(x)在各点的值逐点相乘，计算出在各点的值逐点相乘，计算出r(x)r(x)在各在各点的值。点的值。 4.4. 插值：互换插值：互换a a与与y y的作用，再

21、利用函数的作用，再利用函数transformtransform求求r(x)r(x)的系的系数表示，并注意要将结果除以次数作为最后结果。数表示，并注意要将结果除以次数作为最后结果。以上第以上第1 1、第、第3 3步的执行时间都是步的执行时间都是O(n)O(n)，第，第2 2、第、第4 4步的执行时间都步的执行时间都是是O(n log n)O(n log n)。 算法改进算法改进 在函数在函数transformtransform中，我们是用递归的方式来求解，中，我们是用递归的方式来求解，我们对我们对n=8n=8的情况来具体演示一下递归调用的过程。的情况来具体演示一下递归调用的过程。 0123456

22、7(,)a a a a a a a a1357(,)a a a a3()a1()a37(,)a a15(,)a a5()a7()a0246(,)a a a a2()a26(,)a a04(,)a a0()a6()a4()a3()a1()a37(,)a a15(,)a a5()a7()a2()a26(,)a a04(,)a a0()a6()a4()a 但是递归的方法对空间的要求很高，从函数但是递归的方法对空间的要求很高，从函数transformtransform中可以看到每次递归调用时都需要新的系数数组传入递归中可以看到每次递归调用时都需要新的系数数组传入递归过程内部。而通过刚才的演示，我们发现

23、我们也可以用从过程内部。而通过刚才的演示，我们发现我们也可以用从底向上迭代的方法来进行。底向上迭代的方法来进行。01234567(,)a a a a a a a a0246(,)a a a a1357(,)a a a a迭代算法的具体实现过程迭代算法的具体实现过程初始化初始化预处理预处理通过增加高次零项使将多项式的次数增加到通过增加高次零项使将多项式的次数增加到2 2的幂次。的幂次。Function transform_better (a:atype):y:ytype;y:=a;迭代过程迭代过程For k:=1 to lg n do 对数组进行恰当的合并并将结果放到数组恰对数组进行恰当的合并并

24、将结果放到数组恰当的位置。当的位置。01234567(,)a a a a a a a a1357(,)a a a a3()a1()a37(,)a a15(,)a a5()a7()a0246(,)a a a a2()a26(,)a a04(,)a a0()a6()a4()ay yy yy yy yback0122,01010101010101010122,0122,0122,01234444, 01234444, 0123456788888888, 下面我们将本文介绍的方法与普通的多项式乘法做下面我们将本文介绍的方法与普通的多项式乘法做一个比较。一个比较。多项式次数多项式次数n=100n=1000n=10000n=20000n=30000普通方法普通方法时间时间(s)0.020.075.0218.0630点值方法点值方法时间时间(s)0.050.502.462.883.36精度精度(real)1011位1011位910位89位89位测试环境：测试环境：PIII 500 128M RAM FreePascal 1.0.4