算法重拾之路——大数乘法

***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

隶属于递归与分治

描述：设X与Y都是n位十进制的整数，现在要计算它们的乘积XY。

朴素法：用小学时候学过的方法，模拟乘，这样计算步骤太多，效率很低，时间复杂度达到了O（n^2）的地步。

分治法：将n为十进制整数分为两段每段长为n/2位，如下所示：

所以，X= A*10^(n/2)+B ? Y=C*10^(n/2)+D

X*Y = ( A*10^(n/2) + B ) * ( C*10^(n/2) + D ) = A*C*10^n + ( A*D + B*C )*10^(n/2) + B*D

如果这样计算，必须进行4次 n/2 位整数的乘法，AC,AD,BC,BD 以及3次不超过2n位整数加法，此外还要做2次移位。所有这些加法和移位共用O（n）步运算。设T（n）是2个n位整数相乘所需要的运算总数，则有：

T(n) = ? ? O(1) ? ? ? ? ? ? ? ? ? ? ? ? ? ?当n=1

? ? ? ? ? ? ? ?4*T(n/2) + O(n) ? ? ? ? ?当n>1

由此可得T(n)=O(n^2) 因此，这种方法不比小学生方法更有效，所以可以把上面形式转换为下面这种形式：

XY = A*C*10^n + ( (A-B)*(D-C)+A*C+B*D )*10^(n/2) + B*D

虽然这样看起来复杂了点，但是却减少了一次乘法操作（有几个乘法是相同），因此它的复杂度为：

T(n) =? O(1) ? ? ? ? ? ? ? ? ? ? ? ? ??当n=1

? ? ? ? ? ? ? ? ? ? ? 3*T(n/2) + O(n) ? ? ? ??当n>1

容易求得T(n) = O(n^log3)=O(n^1.59)?

程序：

long long int largeMul( long long int x,long long int y,int n )
{
    int i,k,hx,hy,lx,ly;
    long long int m1,m2,m3;
    i=0,k=1;
    while( i < n/2 )    {
        k*=10;
        ++i;
    }
    hx = x / k,lx = x % k;
    hy = y / k,ly = y % k;
    m1=hx*hy;
    m2=(hx-lx)*(ly-hy);
    m3=lx*ly;

    return (m1*k*k + ( m2+m1+m3 )*k + m3 );
}

********************************************