大整数乘法(C)请设计一个有效的算法,可以进行两个n位大整数的乘法运算。 设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法,但是这样做计算步骤太多,显得效率较低。如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要作O(n^2)步运算才能求出乘积XY。
打问号处个人感觉有问题,不过乘法肯定是主要运算,移位操作一定小于 n(n-1)次,加法操作小于n(n-1)次, O( 3 n^2) = O( n^2).
下面我们用分治法来设计一个更有效的大整数乘积算法。 我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(为简单起见,假设n是2的幂),如图6-3所示。
省略了作标记处的运算过程 , 关键是前一个的指数是 log4,后一个是 log3 = 1.59.
补充一些文字解释:
由此,X=A2^(n/2)+B,Y=C2^(n/2)+D。这样,X和Y的乘积为:
XY=(A2^(n/2)+B)(C2^(n/2)+D)=AC2^n+(AD+CB)2^(n/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),我们有:
T(n) = O(1) n=1
4T(n/2)+O(n) n>1
由此可得T(n)=O(n2)。因此,用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性,必须减少乘法次数。为此我们把XY写成另一种形式: XY=AC2^n+(((A-B)(D-C)+AC+BD)2^(n/2)+BD (2) 虽然,式(2)看起来比式(1)复杂些,但它仅需做3次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次加、减法和2次移位。由此可得:
T(n) = O(1) n=1
3T(n/2)+O(n) n>1
T(n)=O(nlog3) =O(n1.59)
暂时没有详细检查过这些链接
http://blog.csdn.net/wangyangkobe/article/details/6447195
http://blog.csdn.net/louistech/article/details/8890717
JAVA版 http://blog.csdn.net/nizhou1/article/details/12710741
1、如果将一个大整数分成3段或4段做乘法,计算复杂性会发生会么变化呢?是否优于分成2段做的乘法?这个问题请大家自己考虑。
分的段数越多, 效率越低. 极端情况, 直接按位计算,相当于分为N段, 就回到了这个文章开始提出的原始算法了. (这个似乎与前文矛盾了,但是个人觉得这种解释是有道理的。)
请自行查阅