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 x N の行列が必要です。

この追加をどこで行っており、どこに移行していますか?

あなたの質問では、500 x 500 の乗算と 500 x 500 の加算が必要です。O(N*N)

長所: 各桁の乗算は 1 バイトで実行できるため、コンパイラがコードをベクトル化し、一度に 16 桁から 32 桁を乗算できる桁の構造を変更できます (展開は非常に良好です)。

短所: 計算が多すぎる (500 桁あたり約 25 ～ 40 回の反復)

注: GPU を利用した計算では、約 40 倍の速度が得られます。OpenCL や Cuda など。

于 2012-09-14T18:59:25.653 に答える