2

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

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

我的问题是，如何进行乘法运算。

我将在这里详细说明它是如何处理 cin 和 cout 的。

对于cin，它将整数保存到value[500]，例如50将保存到value[498]和value[499]。但不是 value[0] 和 value[1]

对于 cout，它将从 value[0] 到 value[499] 扫描第一个非零值，然后从该非零值输出到末尾。此外，如果它没有找到非零值，它将输出 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位的数字。

4

1 回答 1

6

让我们从简单的乘法（长乘法）开始：

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。

于 2012-09-14T18:59:25.653 回答