有没有优化两个BigNums的乘法的好方法? [英] Is there a good way to optimize the multiplication of two BigNums?

问题描述

我有一个类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]);
    }
};

我正在尝试编写代码来将两个 BigNum 相乘.目前，我一直在使用传统的乘法方法，即将第一个数字乘以另一个数字的每个数字并将其添加到运行总数中.这是我的代码:

and I'm trying to write code to multiply two BigNums. Currently, I've been using the traditional method of multiplication, which is multiplying the first number by each digit of the other and adding it to a running total. Here's my code:

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 的阶乘大约需要一分钟.有没有更好的方法来乘以两个 BigNums?如果没有，是否有更好的方法来表示可以加速此代码的大数?

This code still works pretty slowly; it takes around a minute to calculate the factorial of 1000. Is there a better way to multiply two BigNums? If not, is there a better way to represent large numbers that will speed up this code?

推荐答案

如果你使用不同的基数，比如 2^16 而不是 10，乘法会快得多.

If you use a different base, say 2^16 instead of 10, the multiplication will be much faster.

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

But getting to print in decimal will be longer.

这篇关于有没有优化两个BigNums的乘法的好方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！