有没有优化两个 BigNums 的乘法的好方法？

Question

我有一个 class 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。目前，我一直在使用传统的乘法方法，即将第一个数字乘以另一个数字的每个数字，然后将其加到总数运行中。这是我的代码：

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 相乘？如果不是，是否有更好的方法来表示可以加快此代码速度的大数？

Answer 1

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

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

Answer 2

获取现成的 bignum 库。这些往往被优化到死，一直到特定的 CPU 模型，必要时进行组装。

GMP and MPIR 是两个流行的。后者更 Windows 友好。

Answer 3

一种方法是使用大于十的基数。在时间和 space 上都是巨大的浪费，使用一个 int，能够保存大约 40 亿的值（无符号变体）并用它来存储个位数。

您可以做的是使用 unsigned int/long 个值作为开始，然后选择一个底数，使该底数的平方适合该值。所以，比如说，最大的32位的平方根unsigned int是65000多一点所以你选择10000作为底数。

所以 "bigdigit"（我将使用该术语表示以 10,000 为基数的方案中的数字，实际上等于四位十进制数字（从这里开始只是数字），这有几个影响：

更少 space 占用（大约 space 的 1/1,000）；
四位数相乘仍然不会溢出
更快的乘法，一次计算四位数而不是一个；和
仍然很容易打印，因为它是十进制格式。

最后两点战争运行没有一些解释。

在倒数第二个，它应该快 sixteen 倍，因为要乘以 1234 和 5678，第一个中的每个数字必须与第二个中的每个数字相乘。对于一个普通数字，这是十六次乘法，而对于一个大数字，它只是一次。

由于bigdigits正好是四位数，所以输出还是比较容易的，大概是这样的：

printf("%d", node[0]);
for (int i = 1; i < node_count; ++i) {
    printf("%04d", node[0]);
}

除此之外，正常的 C++ 优化（如传递 const 引用而不是复制所有对象），您可以检查 MPIR 和 GMP 使用的相同技巧。我自己倾向于避免使用它们，因为它们有（或在某些时候确实有）一个相当讨厌的习惯，当它们运行内存不足时就猛烈退出程序，我发现在通用库中这是不可原谅的。无论如何，随着时间的推移，我已经建立了例程，虽然远不及 GMP ，但肯定比我需要的更多（并且在许多情况下使用相同的算法）。

乘法的技巧之一是 Karatsuba 算法（老实说，如果 GMP/MPIR 使用这个，我肯定但是，除非他们有更好的东西，我怀疑他们会的）。

它基本上涉及将数字分成几部分，以便 a = a1a0是第一个，b = b1b0。换句话说：

a = a1 x Bp + a0
b = b1 x Bp + b0

Bp 只是您正在使用的实际基础的一些积分功率，通常可以是最接近的值较大数字的平方根（大约是数字的一半）。

然后你锻炼：

c2 = a1 x b1
c0 = a0 x b0
c1 = (a1 + a0) x (b1 + b0) - c2 - c0

最后一点很棘手，但已经在数学上得到证明。我建议，如果您想深入到那种程度，我不是这份工作的最佳人选。在某些时候，即使是我这种完美的"don't believe anything you can't prove yourself"类型，也将专家意见视为事实:-)

然后你使用一些 add/shift 魔法（乘法 看起来 涉及但是，因为它是乘以基数的幂，所以它实际上只是一个移位的问题剩余值）。

c = c2 x B2p + c1 x Bp + c0

现在您可能想知道为什么三次乘法比一次乘法更好，但您需要考虑到这些乘法使用的位数比原来少得多。如果你还记得我上面关于从 base-10 切换到 base-10,000 时进行一次乘法而不是十六次乘法的评论，你会发现数字乘法的数量与 square[=119 成正比=] 的位数。

这意味着执行三个 更小的 乘法可能会更好，即使有一些额外的移位和加法。这个解决方案的美妙之处在于，你可以递归地将它应用于较小的数字，直到你到达你只是乘以两个 unsigned int 值的地步。

我可能还没有完全理解这个概念，你确实需要注意并调整 c1 变为负数的情况，但是，如果你想要原始速度，这就是你需要做的事情我得看看。

而且，正如我更高级的数学伙伴会告诉我的（经常），如果你不愿意让你的整个脑袋爆炸，你可能不应该做数学:-)

有没有优化两个 BigNums 的乘法的好方法？

Is there a good way to optimize the multiplication of two BigNums?

c++

struct

bignum