大数的乘法问题

设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)=AC2^n+(AD+CB)2^(n/2)+BD             (1)
式中 2n/2 代表2的n/2次方。

如果按式(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(n^log3)=O(n^1.59)。利用式(3)，并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:

function MULT(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分别取绝对值}

if n=1 then

if (X=1)and(Y=1) then return(S)

else return(0)

else begin

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段做的乘法？这个问题请大家自己考虑。

大体算法如下（仍旧有很大问题）

package algorithm;

/**
 *

Title: algorithm

 *
 *

Description: my algorithmic program

 *
 *

Copyright: Copyright (c) 2008

 *
 *

Company:

 *
 * @author not attributable
 * @version 1.0 设X和Y都是n位二进制整数，现在要计算他们的乘积XY。
 */
public class BigInteger {
    public BigInteger() {
        super();
    }
    /*
    *计算谁入的位数
    */
    public int num(long x)
    {
        int result=0;
        long temp=x;
        while(temp>0)
        {
            temp=temp/2;
            result++;
        }
        return result;
    }
    /*
    *递归计算
    */
    public long mut(long x,long y,int n)
    {
        if(n==1)
        {
            return x*y;
        }
        else
        {
           
            long a=x;//取左半部分
            a>>=n/2;
            long b=(long)(x%Math.pow(2,n/2));//取右半部分
            long c=y;
            c>>=n/2;
            long d=(long)(y%Math.pow(2,n/2));;
            long m1=mut(a,c,n/2);
            long m2=mut(a-b,d-c,n/2);
            long m3=mut(b,d,n/2);
            long s=(long)(m1*Math.pow(2,n))+(long)((m2+m1+m3)*Math.pow(2,n/2))+m3;
            return s;
        }
    }
    public static void main(String[] args) {
        BigInteger biginteger = new BigInteger();
       System.out.print( biginteger.mut(37,10,4));
    }
}