大数乘法

后期需要实现分治算法，降低复杂度

//
// Created by krislyy on 2018/11/5.
//

#ifndef ALGORITHM_MUTIPLICATION_H
#define ALGORITHM_MUTIPLICATION_H


namespace Algorithm {
    /*这只是按照乘法法则实现的大数乘法，时间复杂度O(n^2),还可采用
     *分治法实现，时间复杂度为O(n^log2(3))
     * */
    static int* bigMul(int* bigX, int nX, int* bigY, int nY) {
        int k = nX + nY;
        int* res = new int[k];
        for (int i = 0; i < nX; ++i) {
            for (int j = 0; j < nY; ++j) {
                res[i+j] += bigX[i]*bigY[j];
            }
        }

        for (int l = 0; l < k; ++l) {
            if(res[l] >= 10) {
                res[l+1] += res[l]/10;
                res[l] = res[l]%10;
            }
        }
        return res;
    }

    //只是实现了分治法的思想，但是并不能直接运行大数
    #define SIGN(A) ((A > 0) ? 1 : -1)
    static int bigMul(int X, int Y, int n) {
        int sign = SIGN(X) * SIGN(Y);
        int x = abs((double)X);
        int y = abs((double)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 = bigMul(A, C, n / 2);
            int BD = bigMul(B, D, n / 2);
            int ABDC = bigMul((A - B), (D - C), n / 2) + AC + BD;
            return sign * (AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD);
        }
};

#endif //ALGORITHM_MUTIPLICATION_H

测试代码

int main() {
    //////////////////////////////////BigMul/////////////////////////////
    //模拟12345678998765 * 1234567 = ??
    int bigX[] = {5,6,7,8,9,9,8,7,6,5,4,3,2,1};
    int nX = sizeof(bigX)/ sizeof(int);
    int bigY[] = {7,6,5,4,3,2,1};
    int nY = sizeof(bigY)/ sizeof(int);
    int* res = Algorithm::bigMul(bigX, nX, bigY, nY);
    std::stringstream streamA;
    for (int j = nX - 1; j >= 0 ; --j) {
        streamA << bigX[j];
    }
    std::stringstream streamB;
    for (int j = nY - 1; j >= 0; --j) {
        streamB << bigY[j];
    }
    std::stringstream streamRes;
    int nRes = nY + nX;
    for (int j = nRes - 1; j >= 0; --j) {
        streamRes << res[j];
    }
    std::cout << streamA.str() << " * " << streamB.str()
              << " = " << streamRes.str() << std::endl;
    return 0;
}

输出结果： 12345678998765 * 1234567 = 015241567884468309755