算法设计与分析 习题2-5

1、习题习题2-5 在用分治法求两个n位大整数u和v的乘积时，将u和v都分割为长度为n/3的3段。证明可以用5次n/3位整数的乘法求得uv的值。按此思想设计一个求两个大整数乘积的分治方法，并分析算法的计算复杂性。（提示：n位的大整数除以一个常数k可以在（n）时间完成。符号 所隐含的常数可能依赖于k）分析：这个题目要求对大整数3等分，我们先讨论对于这个 问 题更一般性的解答，即将n位的大整数m等分，可以用(2m-1)次n/m位的整数的乘法求得两个大整数的乘积。 设x=2n/m，可以将u和v及其乘积w=uv表示为： U=U0+U1X+U2X2+Um-1Xm-1 V=V0+V1X+V2X2+Vm-1Xm

2、-1 W=UV=W0+W1X+W2X2+W2m-2X2m-2 将U,V和W都看作关于变量X的多项式，并取2m-1个不同的数x1，x2，x2m-1代入多项式可得 U(Xi)=U0+U1Xi+U2Xi2+Um-1Xim-1 V(Xi)=V0+V1Xi+V2Xi2+Vm-1Xim-1 W(Xi)=U(Xi) V(Xi)=W0+W1Xi+W2Xi2+W2m-2Xi2m-2 可以用矩阵表示为：可以用矩阵表示为： W(x1) 1 x1 x12 x12m-2 w0 W(x2) 1 x2 x22 x22m-2 w1 . . . . . . . . = . . . . . . . . . . . . . W(x

3、2m-1) 1 x2m-1 x2m-1 . x2m-12m-2 w2m-2设设 1 x1 x12 x12m-2 1 x2 x22 x22m-2 . . . . . B = . . . . . . . . . . 1 x2m-1 x2m-12 x2m-12m-2 则则 w0 w(x1) w1 w(x2) . . . = B-1 . . . w2m-2 w(2m-2) 式中，多项式W(xi)=U(xi)V(xi)是两个n/m位数的乘法运算，共有2m-1个乘法，其余均为加减法或数乘运算。下面我们来看m=3的具体算法：解：设x=2n/3，那么U，V及其乘积W=UV可以表示为： U=U0+U1X+U2X

4、2 V=V0+V1X+V2X2 W=UV=W0+W1X+W2X2 +W3X3+W4X4 取5个数x1，x2，x5,它们的值为： x1=0，x2=1，x3=-1，x4=2，x5=-2代入多项式，得a=W(0)=U0V0b=W(1)=(U0+U1+U2)(V0+V1+V2)c=W(-1)=(U0-U1+U2)(V0-V1+V2)d=W(2)=(U0+2U1+4U2)(V0+2V1+4V2)e=W(-2)=(U0-2U1+4U2)(V0-2V1+4V2) a 1 0 0 0 0 W0 b 1 1 1 1 1 W1 c = 1 -1 1 -1 1 W2 d 1 2 4 8 16 W3 e 1 -2 4

5、 -8 16 W4 W0 1 0 0 0 0 -1 a W1 1 1 1 1 1 b W2 = 1 -1 1 -1 1 c W3 1 2 4 8 16 d W4 1 -2 4 -8 16 e解得： W0= a W1= b+c-4(d+e)+6a 24 W2= -b+c+2(d-e) 12 W3= -b-c+16(d+e)-30a 24 W4= b-c-8(d-e) 12 程序的实现流程： 1. 用数组获取两个(n+1)位的大整数U，V. 第一位为符号位。 2. 计算符号位。 3.将U，V 3等分，计算出U0 ，U1 ，U2及V0，V1，V2的值。 4.计算出a，b，c，d，e的值。 5.计算出W0， W1 ， W2， W3， W4的值。 6.移位，计算出乘积W的值。算法复杂度分析： 按照此算法计算大整数乘积需要5次n/3位整数乘法。大整数分割，移位，加减法和数乘运算时间为O(n)。