C++大数运算

Question

我正在开发一个用于大数算术的类，它现在知道如何做加法，处理cin和cout。

然而，它具有非常有限和基本的减法功能，并且不知道如何处理负片。但这很容易解决。

我的问题是，如何做乘法。

我将在这里详细介绍它如何处理cin和cout。

对于cin，它会将整数保存到value500，例如，50将保存到value498和value499。而不是value和value1

对于cout，它将扫描从value到value499的第一个非零值，然后从该非零值输出到末尾。此外，如果它没有找到非零值，它将输出0。

下面是我的代码：

#include <iostream>

using namespace std;

class largeNumber {
public:
    int value[500];
    largeNumber()
    {
        for ( int i = 0 ; i < 500 ; ++ i )
        {
            value[i] = 0;
        }
    }
    //below are arithmetic operations
    largeNumber operator+(const largeNumber &ln) const
    {
        largeNumber result;
        for ( int i = 0 ; i < 500 ; ++ i )
        {
            result.value[i] = value[i] + ln.value[i];
        }
        for ( int i = 499 ; i >= 0 ; -- i )
        {
            if ( result.value[i] >= 10 )
            {
                result.value[i - 1] += ( result.value[i] / 10 );
                result.value[i] %= 10;
            }
        }
        return result;
    }
    largeNumber operator-(const largeNumber &ln) const
    {
        largeNumber result;

        for ( int i = 0 ; i < 500 ; ++ i )
        {
            result.value[i] = value[i] - ln.value[i];
        }
        for ( int i = 499 ; i >= 0 ; -- i )
        {
            if ( result.value[i] < 0 )
            {
                --result.value[i - 1];
                result.value[i] += 10;
            }
        }
        return result;
    }
    largeNumber operator*(const largeNumber &ln) const
    {
        largeNumber result;
        for ( int x = 499 ; x >= 0 ; -- x )
        {
            for ( int y = 499 ; y >= 0 ; -- y )
            {
                int dx = 499 - x;
                int dy = 499 - y;
                int dr = dx + dy;
                int r = 499 - dr;
                if ( r >= 0 && r <= 499 )
                {
                    result.value[r] = value[x] * ln.value[y];
                }
            }
        }
        for ( int i = 499 ; i >= 0 ; -- i )
        {
            if ( result.value[i] >= 10 )
            {
                result.value[i - 1] += ( result.value[i] / 10 );
                result.value[i] %= 10;
            }
        }
        return result;
    }
    //below are cin, cout operators
    friend ostream& operator<<(ostream& out, const largeNumber& ln)
    {
        bool valueFound = false;
        for ( int i = 0 ; i < 500 ; ++ i )
        {
            if ( ln.value[i] != 0 )
            {
                valueFound = true;
            }
            if ( valueFound == true )
            {
                out << ln.value[i];
            }
        }
        if ( valueFound == false )
        {
            out << "0";
        }
        return out;
    }
    friend istream& operator>>(istream& in, largeNumber& ln) // input
    {
        string str;
        in >> str;
        int length = str.length();
        for ( int i = 500 - length ; i < 500 ; ++ i )
        {
            ln.value[i] = (str[length-(500-i)] - 48);
        }
        return in;
    }
};

int main()
{
    largeNumber a, b;
    string op;
    cin >> a >> op >> b;
    cout << a * b;
    return 0;
}

我已经包含了我做乘法的方法，但是它是有缺陷的。

顺便说一下，老师给出的数字承诺乘法的结果将是一个小于500位的数字。

Answer 1

让我们从简单的乘法(长乘法)开始：

112 * 301

          1     1     2
          3     0     1
          ______________
          1     1     2
     0    0     0
 3   3    6
 _______________________
 3   3    7     1     2

因此，这需要N×N矩阵作为行，并加上移位-n次。

你在哪里做这个加法，在哪里转移？

对于你的问题，它需要500 x 500乘法和500 x 500加法。O(N*N)

优点:每个数字乘法都可以在一个字节中完成，这样你就可以改变数字的结构，这样你的编译器就可以向量化代码，一次乘16到32位数字(展开得很好)。

缺点:计算量太大(每500位数近25-40次迭代)

注意:GPU驱动的微积分可以给它大约40倍的速度。例如OpenCL或Cuda。