分治——大整数乘法

冷不防 2022-06-15 01:09 246阅读 0赞

**问题描述：**设X和Y是两个n位的二进制整数，现在要计算它们的乘积XY，传统方法计算每2个1位数乘法或加法都看作一步运算，这样需要O(n2)次位运算，代价太高，现在运用分治法设计一个更有效的大整数乘法算法。

当n=1时，计算X·Y就是一次位乘。现在对X、Y进行划分，把X和Y各分为两段，每段长为n/2(假设n=2k,k为正整数)，  
X=A·2n/2\+B  
Y=C·2n/2\+D

那么XY=(X=A·2n/2\+B)(Y=C·2n/2\+D)=AC2n\+(AC+BD)2n/2\+BD

这样计算需要4次n/2位整数乘法(AC,AD,BC和BD),3次n/2位的加法和2次移位合并成X·Y.  
T(n) = 4 T(n / 2) + θ(n) ,  
根据主项定理：T(n) =O(nlog24)=O(n2),  
代价并没有减小，可以通过减少乘法增加加法的方式减小时间复杂度，  
XY==AC2n\+((A-B)(D-C)+BD+AC)·2n/2\+BD

这样减少了一次n/2位的乘法，合并代价稍有增加，六次加减法、两次移位，仍为O(n)阶，  
现在的时间复杂度为：  
T(n) = 3 T(n / 2) + θ(n)，通过master定理求得，T(n) = O(nlog2 3) = O(n1.59 )

**C++实现代码**：

#include<cstdio>
    #include<cmath>
    
    using namespace std;
    
    #define SIGN(A) ((A > 0) ? 1 : -1) 
    int divideConquer(int X, int Y, int n){
        int sign = SIGN(X) * SIGN(Y);
        int x = abs(X);
        int y = abs(Y);
        if(x == 0 || y == 0){
            return 0;
        }else if(n == 1){
            return sign * x * y;
        }else{
            int A = (int) x / pow(10, (int)(n / 2));
            int B = x - A * pow(10, n / 2);
            int C = (int) y / pow(10, (int)(n / 2));
            int D = y - C * pow(10, n / 2);
            int AC = divideConquer(A, C, n / 2);
            int BD = divideConquer(B, D, n / 2);
            int ABDC = divideConquer((A - B), (D - C), n / 2) + AC + BD;
            return sign * (AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD); 
        }
    }
    
    int main(){
        int x, y, n;
        scanf("%d%d%d", &x, &y, &n);
        printf("x 和 y的乘积为：%d", divideConquer(x, y, n));
    }