算法之大整数乘法.docx
- 文档编号:16857066
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:10
- 大小:129.45KB
算法之大整数乘法.docx
《算法之大整数乘法.docx》由会员分享,可在线阅读,更多相关《算法之大整数乘法.docx(10页珍藏版)》请在冰点文库上搜索。
算法之大整数乘法
大整数乘法
通常,在分析一个算法的计算复杂性时,都将加法和乘法运算当作是基本运算来处理,即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。
然而大整数的算术运算。
请设计一个有效的算法,可以进行两个n位大整数的乘法运算。
大整数的乘法
问题描述
参考解答
设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。
我们可以用小学所学的方法来设计一个计算乘积XY的算法,但是这样做计算步骤太多,显得效率较低。
如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要作O(n2)步运算才能求出乘积XY。
下面我们用分治法来设计一个更有效的大整数乘积算法。
图6-3大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(为简单起见,假设n是2的幂),如图6-3所示。
由此,X=A2n/2+B,Y=C2n/2+D。
这样,X和Y的乘积为:
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD
(1)
如果按式
(1)计算XY,则我们必须进行4次n/2位整数的乘法(AC,AD,BC和BD),
以及3次不超过n位的整数加法(分别对应于式
(1)中的加号),此外还要做2次移位(分别对应于式
(1)中乘2n和乘2n/2)。
所有这些加法和移位共用O(n)步运算。
设T(n)是2个n位整数相乘所需的运算总数,则由式
(1),我们有:
(2)
由此可得T(n)=O(n2)。
因此,用
(1)式来计算X和Y的乘积并不比小学生的方法更有效。
要想改进算法的计算复杂性,必须减少乘法次数。
为此我们把XY写成另一种形式:
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
虽然,式(3)看起来比式
(1)复杂些,但它仅需做3次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次加、减法和2次移位。
由此可得:
(4)
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。
利用式(3),并考虑到X和Y的符号对结果的影响,我们给出大整数相乘的完整算法MULT如下:
functionMULT(X,Y,n);{X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}
begin
S:
=SIGN(X)*SIGN(Y);{S为X和Y的符号乘积}
X:
=ABS(X);
Y:
=ABS(Y);{X和Y分别取绝对值}
ifn=1then
if(X=1)and(Y=1)thenreturn(S)
elsereturn(0)
elsebegin
A:
=X的左边n/2位;
B:
=X的右边n/2位;
C:
=Y的左边n/2位;
D:
=Y的右边n/2位;
ml:
=MULT(A,C,n/2);
m2:
=MULT(A-B,D-C,n/2);
m3:
=MULT(B,D,n/2);
S:
=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
下面的例子演示了算法的计算过程。
设X=314l,Y=5327,用上述算法计算XY的计算过程可列表如下,其中带'号的数值是在计算完成AC,BD,和(A-B)(D-C)之后才填入的。
X=3141 A=31 B=41 A-B=-10
Y=5327 C=53 D=27 D-C=-26
AC=(1643)'
BD=(1107)'
(A-B)(D-C)=(260)'
XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'
=(16732107)'
A=31 A1=3 B1=1 A1-B1=2
C=53 C1=5 D1=3 D1-C1=-2
A1C1=15 B1D1=3 (A1-B1)(D1-C1)=-4
AC=1500+(15+3-4)10+3=1643
B=41 A2=4 B2=1 A2-B2=3
D=27 C2=2 D2=7 D2-C2=5
A2C2=8 B2D2=7 (A2-B2)(D2-C2)=15
BD=800+(8+7+15)10+7=1107
|A-B|=10 A3=1 B3=0 A3-B3=1
|D-C|=26 C3=2 D3=6 D3-C3=4
A3C3=2 B3D3=0 (A3-B3)(D3-C3)=4
(A-B)(D-C)=200+(2+0+4)10+0=260
如果将一个大整数分成3段或4段做乘法,计算复杂性会发生会么变化呢?
是否优于分成2段做的乘法?
这个问题请大家自己考虑。
4.7Strassen矩阵乘法
设
,
要做8次数乘。
1969年strassen提出了只做7次数乘的算法,很有启发性。
则
P,Q,R,S,T各用2次,U,V各用1次。
上面的strassen乘法可以推广,将其中的数看作是小矩阵。
时间复杂度:
乘法次数分析
设
,
为2个
阶方阵相乘所需做的数乘的次数。
常规的乘法次数为
加法次数分析
设
为加法的次数,则
常规的加法次数为
空间复杂度:
常规方法:
2个N阶方阵,加一行N个存储单元
A的第一行与B的各列做内积之后不必保存,可以用来存C的第一行,故需要
个单元
Strassen方法:
矩阵乘法是线性代数中最常见的运算之一,它在数值计算中有广泛的应用。
若A和B是2个n×n的矩阵,则它们的乘积C=AB同样是一个n×n的矩阵。
A和B的乘积矩阵C中的元素C[i,j]定义为:
若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i,j],需要做n个乘法和n-1次加法。
因此,求出矩阵C的n2个元素所需的计算时间为0(n3)。
60年代末,Strassen采用了类似于在大整数乘法中用过的分治技术,将计算2个n阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.18)。
首先,我们还是需要假设n是2的幂。
将矩阵A,B和C中每一矩阵都分块成为4个大小相等的子矩阵,每个子矩阵都是n/2×n/2的方阵。
由此可将方程C=AB重写为:
(1)
由此可得:
C11=A11B11+A12B21
(2)
C12=A11B12+A12B22 (3)
C21=A21B11+A22B21 (4)
C22=A21B12+A22B22 (5)
如果n=2,则2个2阶方阵的乘积可以直接用
(2)-(3)式计算出来,共需8次乘法和4次加法。
当子矩阵的阶大于2时,为求2个子矩阵的积,可以继续将子矩阵分块,直到子矩阵的阶降为2。
这样,就产生了一个分治降阶的递归算法。
依此算法,计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。
2个n/2×n/2矩阵的加法显然可以在c*n2/4时间内完成,这里c是一个常数。
因此,上述分治法的计算时间耗费T(n)应该满足:
这个递归方程的解仍然是T(n)=O(n3)。
因此,该方法并不比用原始定义直接计算更有效。
究其原因,乃是由于式
(2)-(5)并没有减少矩阵的乘法次数。
而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。
要想改进矩阵乘法的计算时间复杂性,必须减少子矩阵乘法运算的次数。
按照上述分治法的思想可以看出,要想减少乘法运算次数,关键在于计算2个2阶方阵的乘积时,能否用少于8次的乘法运算。
Strassen提出了一种新的算法来计算2个2阶方阵的乘积。
他的算法只用了7次乘法运算,但增加了加、减法的运算次数。
这7次乘法是:
M1=A11(B12-B22)
M2=(A11+A12)B22
M3=(A21+A22)B11
M4=A22(B21-B11)
M5=(A11+A22)(B11+B22)
M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
做了这7次乘法后,再做若干次加、减法就可以得到:
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
以上计算的正确性很容易验证。
例如:
C22=M5+M1-M3-M7
=(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11-A21)(B11+B12)
=A11B11+A11B22+A22B11+A22B22+A11B12
-A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12
=A21B12+A22B22
由
(2)式便知其正确性。
至此,我们可以得到完整的Strassen算法如下:
procedureSTRASSEN(n,A,B,C);
begin
ifn=2thenMATRIX-MULTIPLY(A,B,C)
elsebegin
将矩阵A和B依
(1)式分块;
STRASSEN(n/2,A11,B12-B22,M1);
STRASSEN(n/2,A11+A12,B22,M2);
STRASSEN(n/2,A21+A22,B11,M3);
STRASSEN(n/2,A22,B21-B11,M4);
STRASSEN(n/2,A11+A22,B11+B22,M5);
STRASSEN(n/2,A12-A22,B21+B22,M6);
STRASSEN(n/2,A11-A21,B11+B12,M7);
;
end;
end;
其中MATRIX-MULTIPLY(A,B,C)是按通常的矩阵乘法计算C=AB的子算法。
Strassen矩阵乘积分治算法中,用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。
由此可知,该算法的所需的计算时间T(n)满足如下的递归方程:
按照解递归方程的套用公式法,其解为T(n)=O(nlog7)≈O(n2.81)。
由此可见,Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。
有人曾列举了计算2个2阶矩阵乘法的36种不同方法。
但所有的方法都要做7次乘法。
除非能找到一种计算2阶方阵乘积的算法,使乘法的计算次数少于7次,按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。
但是Hopcroft和Kerr(197l)已经证明,计算2个2×2矩阵的乘积,7次乘法是必要的。
因此,要想进一步改进矩阵乘法的时间复杂性,就不能再寄希望于计算2×2矩阵的乘法次数的减少。
或许应当研究3×3或5×5矩阵的更好算法。
在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。
目前最好的计算时间上界是O(n2.367)。
而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n2)。
因此到目前为止还无法确切知道矩阵乘法的时间复杂性。
关于这一研究课题还有许多工作可做。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 整数 乘法
![提示](https://static.bingdoc.com/images/bang_tan.gif)