アルゴリズムの拾い直しの道——大数乗算

出典を明記してください.http://blog.csdn.net/lttree********************************************
再帰と分治に属する
説明:XとYはnビット10進数の整数であるとし、それらの積XYを計算します.
素朴法:小学生の頃に習った方法で、アナログ乗をすると、計算手順が多すぎて効率が低く、時間の複雑さがO(n^2)に達します.
分治法:nを10進数整数に2つのセグメントに分け、各セグメントの長さはn/2ビットで、以下に示す.

したがって、X=A*10^(n/2)+BY=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
このように計算すると,n/2ビット整数の乗算を4回行い,AC,AD,BC,BDおよび2 nビットを超えない整数の加算を3回行い,またシフトを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
これにより、点が複雑に見えますが、1回の乗算操作(いくつかの乗算が同じ)が減少するため、その複雑さは次のとおりです.
T(n)=O(1)n=1
3*T(n/2)+O(n)n>1
容易に求めるT(n)=O(n^log 3)=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 );
}

もちろんこれは2つのセグメントに分かれているだけで、分治の特徴を正確に体現していない.
出典を明記してください.http://blog.csdn.net/lttree********************************************