时间戳

首页 > 解决方案 > 有没有优化两个 BigNum 相乘的好方法？

c++ - 有没有优化两个 BigNum 相乘的好方法？

问题描述

我有一堂课BigNum：

struct BigNum{
    vector <int> digits;
    
    BigNum(vector <int> data){
        for(int item : data){d.push_back(item);}
    }
    
    int get_digit(size_t index){
        return (index >= d.size() ? 0 : d[index]);
    }
};

我正在尝试编写代码来乘以两个BigNums。目前，我一直在使用传统的乘法方法，将第一个数字乘以另一个数字的每个数字，然后将其添加到运行总数中。这是我的代码：

BigNum add(BigNum a, BigNum b){ // traditional adding: goes digit by digit and keeps a "carry" variable
    vector <int> ret;

    int carry = 0;
    for(size_t i = 0; i < max(a.digits.size(), b.digits.size()); ++i){
        int curr = a.get_digit(i) + b.get_digit(i) + carry;

        ret.push_back(curr%10);
        carry = curr/10;
    }

    // leftover from carrying values
    while(carry != 0){
        ret.push_back(carry%10);
        carry /= 10;
    }

    return BigNum(ret);
}

BigNum mult(BigNum a, BigNum b){
    BigNum ret({0});

    for(size_t i = 0; i < a.d.size(); ++i){
        vector <int> row(i, 0); // account for the zeroes at the end of each row

        int carry = 0;
        for(size_t j = 0; j < b.d.size(); ++j){
            int curr = a.d[i] * b.d[j] + carry;

            row.push_back(curr%10);
            carry = curr/10;
        }

        while(carry != 0){ // leftover from carrying
            row.push_back(carry%10);
            carry /= 10;
        }

        ret = add(ret, BigNum(row)); // add the current row to our running sum
    }

    return ret;
}

这段代码仍然运行得很慢；计算 1000 的阶乘大约需要一分钟。有没有更好的方法将两个 BigNum 相乘？如果没有，是否有更好的方法来表示可以加速此代码的大量数字？

标签： c++structbignum

解决方案

如果您使用不同的基数，例如 2^16 而不是 10，则乘法会快得多。

但是以十进制打印会更长。

推荐阅读