C++ 中的大数乘法

Question

我正在寻找 C++ 中的快速大数乘法算法。我尝试过类似的方法，但我认为我创建了太多字符串对象。

string sum(string v1, string v2)
{
    string r;
    int temp = 0, i, n, m;
    int size1 = v1.size(), size2 = v2.size();
    n = min(size1, size2);
    m = max(size1, size2);
    if ((v1 == "0" || v1 == "") && (v2 == "0" || v2 == "")) return "0";
    r.resize(m, '0');
    for (i = 0; i < n; i++)
    {
        temp += v1[size1 - 1 - i] + v2[size2 - 1 - i] - 96;
        r[m - 1 - i] = temp % 10 + 48;
        temp /= 10;
    }
    while (i < size1)
    {
        temp += v1[size1 - 1 - i] - 48;
        r[m - 1 - i] = (char)(temp % 10 + 48);
        temp /= 10;
        ++i;
    }
    while (i < size2)
    {
        temp += v2[size2 - 1 - i] - 48;
        r[m - 1 - i] = (char)(temp % 10 + 48);
        temp /= 10;
        ++i;
    }
    if (temp != 0) 
        r = (char)(temp + 48) + r;
    return r;
}

string multSmall(string v1, int m)
{
    string ret = "0";
    while(m)
    {
        if (m & 1) ret = sum(ret, v1);
        m >>= 1;
        if (m) v1 = sum(v1, v1);
    }
    return ret;
}

string multAll(string v1, string v2)
{
    string ret = "0", z = "", pom;
    int i, size;
    if (v1.size() < v2.size())
        std::swap(v1, v2);
    size = v2.size();
    for (i = 0; i < size; i++)
    {
        pom = multSmall(v1, v2[size - 1 - i] - 48);
        pom.append(z);
        ret = sum(ret, pom);
        z.resize(i + 1, '0');
    }
    return ret;
}

我不想使用任何外部库。我应该怎么做？也许我应该使用 char 数组而不是字符串？但是我不确定为数组重新分配内存是否比创建字符串对象更快。

Answer 1

快速大数乘法是个大工程。一个非常大的项目，具体取决于您要相乘的数字有多大。

然而，可能最简单的重要事情是您希望从 CPU 的本机指令中获得尽可能多的里程数。 64 位数字的加法比 8 位数字的加法强 8 倍，比十进制数字的加法强 19 倍以上。但是您的计算机加 64 位数字的速度可能与加 8 位数字的速度一样快，而且比您编写的任何加法十进制数字的代码都要快得多。

乘法更加戏剧化；将两个 64 位数字相乘以产生 128 位结果的指令比将两个 8 位数字相乘以产生 16 位结果的指令所做的工作大约多 64 倍——但是你的 CPU 可以可能以相同的速度进行，或者后者的速度是前者的两倍。

因此，您确实希望围绕尽可能多地使用这些更强大的指令的想法来调整您的数据结构和基本案例算法。

如果需要，您可以将其视为以 2^64 为基数进行算术运算。（或者可能以 2^32 为基数，如果你不能或不想使用 64 位算法）

C++ 中的大数乘法

Large numbers multiplication in C++

c++

arrays

string

multiplication