多项式乘法

nullnull 张家琳 复旦大学附属中学引言引言 多项式是最基本的数学工具之一，由于其形式简单，且易于用计算机对其进行各种计算，在当今的社会中应用越来越广。不仅在像Maple这样的数学软件中有着举足轻重的作用，在、信息等诸多领域中都有着广阔的应用。 下面我们给出几个多项式逼近的例子：多项式的基本运算多项式的基本运算 加法运算 求值运算 乘法运算 普通的多项式乘法运算普通的多项式乘法运算 多项式乘法是一个很常见的问题，在通常的算法中，两个 次多项式的乘法需要用 的时间才能完成。 让我们先来看一看这样的算法是如何进行的： null. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .null 在上面的过程中，似乎我们觉得这个算法并没有做任何多余的事情，因为我们必须考虑每一组 ,它们的乘积对最终的结果都会产生影响。而且我们不能通过调整计算顺序从根本上降低算法时间复杂度，至多只能使其常数因子稍小一些。 如果我们不能跳出以上思维的局限，我们就不可能在根本上降低算法的时间复杂度。 让我们首先换一个角度来考察多项式。多项式的点值表示法 多项式的点值表示法 首先让我们来看多项式的另一种表示方法：点值表示法,即用 （其中， 互不相同）来表示一个不超过 次多项式。 给定一个多项式，要给出n组点值对最简单的方法是任选 n个互不相同的xi，依次求出多项式在这n个点的值。 用n个点值对也可以唯一确定一个不超过n-1次多项式，这个过程称之为插值。引理1（多项式插值的唯一性） 引理1（多项式插值的唯一性） 对于任意n个点值对组成的集合, 其中 互不相同，则存在唯一的次数不超过n-1的多项式 ，满足 continuenull存在性：已知不妨记为XA=YX是范德蒙矩阵，利用行列式的变换可得该矩阵的行列式的值为 因此X有逆矩阵 。null唯一性： 若两个函数次数不超过n-1次的多项式 均符合题意，则多项式 有n个根， 且 为不超过n-1次的多项式，所以 , 即 。 back点值多项式的乘法 点值多项式的乘法 因此： 适当的利用点值表示可以使多项式的乘法可以在线性时间内完成！null 因为f(x)g(x)的次数为n-1，r(x)的次数为2n-2,因此确定r(x)需要2n-1个点值对，而现在我们只有n个点值对。 我们可以通过对f(x)与g(x)的点值对个数的 扩充来解决这个问题，即将f(x),g(x）的点值对在一开始就取为2n-1。利用点值表示法改善多项式系数表示法的乘法 利用点值表示法改善多项式系数表示法的乘法 下面让我们来看一看我们是否能够利用点值表示法在计 算多项式乘法时的线性时间来提高系数表示法的多项式乘 法的速度。 为了做到这一点，我们需要做： 将多项式由系数表示法转化为点值表示法(点值过程） 利用点值表示法完成多项式乘法 将点值表示法再转化为系数表示法（插值过程） 其中第二步只需要线性时间。问题的关键转化为第一 第三步。continue2continue1continue31.由系数表示法转化为点值表示法。（点值过程） 1.由系数表示法转化为点值表示法。（点值过程） 注意！x0,x1,…,xn-1是由我们自己选择的，我们可以充分利用这一点通过适当的选择使转化过程降为O(n log n)。 这里我们选择1的n次单位根作为x0,x1,…,xn-1，即 其中引理2：对任何整数n>=0,k>=0,j>0,成立：引理2：对任何整数n>=0,k>=0,j>0,成立： 证明： 折半定理null 注意到， 中包含了f中所有偶下标的系数，而 中包含了f中所有奇下标的系数。并记求 与 在点 的值。 问题：求设n为偶数（否则可以通过添加高次零项使n化为偶数）。null另一方面，由折半定理： 并不是n个不同的数，而是仅由1的n/2次单位根组成，每个根恰好出现2次。 由此可以看到子问题与原问题形式相同，但规模缩小一半，这启示我们可以利用分治的思想通过递归来解决这个问题。 递归算法的具体实现过程递归算法的具体实现过程递归边界条件Function transform(a:atype):y:ytype；if n=1 then return a0递归预处理    if odd(n) then begin inc(n);an-1:=0;end; 递归过程For k:=0 to n-1 do 利用计算可以证明，以上计算方法的时间复杂度为O(n log n)。back2．将点值表示法再转化为系数表示法。（插值过程） 2．将点值表示法再转化为系数表示法。（插值过程） 点值过程所解决的问题可以等效为一个矩阵方程： 插值过程是点值过程的逆运算。这个问题比前一个问题看起来更复杂，但事实上，通过适当的转化可以把这个问题转化为前一个问题。记为nullYA点值过程插值过程如果存在引理3引理3null利用引理3，我们就可以很容易的解决插值的问题。 YA可等效为矩阵方程： 因此，我们可以充分利用点值过程的方法求出多项式的系数表达。 null递归边界条件Function transform( a:atype ):y:ytype ；if n=1 then return a0递归预处理    if odd(n) then begin inc(n); an-1:=0; end; 递归过程For k:=0 to n-1 do 利用计算backa:atypey:ytypey0yn-1:=0;递归结束后再将a中每一个数除以n。多项式乘法的算法流程 多项式乘法的算法流程 问题：f(x),g(x)是两个n-1次的多项式，已知f(x)g(x)的系数表示，求出r(x)=f(x)*g(x)的系数表示。  算法流程：1. 预处理：通过加入n-1个值为0的高价次数，使f(x)g(x)的次数增加到2n-2。这是为了使点值对的个数足够能够唯一确定r(x)。2. 点值：利用分治的方法，通过函数transform求出f(x)与g(x)在1的2n-1次单位根处的值。 3. 点乘：将f(x),g(x)在各点的值逐点相乘，计算出r(x)在各点的值。 4.  插值：互换a与y的作用，再利用函数transform求r(x)的系数表示，并注意要将结果除以次数作为最后结果。以上第1、第3步的执行时间都是O(n)，第2、第4步的执行时间都是O(n log n)。 算法改进 算法改进 在函数transform中，我们是用递归的方式来求解，我们对n=8的情况来具体演示一下递归调用的过程。 null 但是递归的方法对空间的要求很高，从函数transform中可以看到每次递归调用时都需要新的系数数组传入递归过程内部。而通过刚才的演示，我们发现我们也可以用从底向上迭代的方法来进行。迭代算法的具体实现过程迭代算法的具体实现过程初始化预处理通过增加高次零项使将多项式的次数增加到2的幂次。Function transform_better (a:atype):y:ytype;y:=a;迭代过程For k:=1 to lg n do 对数组进行恰当的合并并将结果放到数组恰当的位置。nullyyyybacknull 下面我们将本文介绍的方法与普通的多项式乘法做一个比较。测试环境：PIII 500 128M RAM FreePascal 1.0.4