C ++でbig intを実装する方法

StackOverflow https://stackoverflow.com/questions/269268

質問

プログラミング演習として、C ++でbig intクラスを実装したい<！>＃8212; long intより大きな数値を処理できるクラス。私はすでにいくつかのオープンソース実装が存在することを知っていますが、私は独自のものを書きたいです。正しいアプローチが何であるかを感じようとしています。

一般的な戦略では、数値を文字列として取得し、それをより小さい数値（たとえば、1桁）に分割し、配列に配置することを理解しています。この時点で、さまざまな比較演算子を実装するのは比較的簡単です。私の主な関心事は、加算や乗算などの実装方法です。

実際の作業コードではなく、一般的なアプローチとアドバイスを探しています。

役に立ちましたか？

解決

大きなintクラスで考慮すべきこと：

  1. 数学演算子：+、-、/、 *、％クラスがどちらかの側にあることを忘れないでください 演算子、演算子は チェーン、オペランドの1つ int、float、doubleなどです。

  2. I / O演算子：<！> gt; <！> gt;、<！> lt; <！> lt;これは 適切な方法を見つけた場所 ユーザー入力からクラスを作成し、出力用にフォーマットする方法。

  3. 変換/キャスト：把握する あなたの大きなint型/クラス クラスはに変換可能である必要があり、 適切に処理する方法 変換。クイックリストは doubleとfloatを含めます。 インクルードint（適切な境界を持つ 確認）および複雑（想定） 範囲を処理できます）。

他のヒント

楽しいチャレンジ。 ：）

私はあなたが任意の長さの整数が欲しいと仮定します。次のアプローチをお勧めします。

データ型<！> quot; int <！> quot;のバイナリの性質を考慮してください。単純なバイナリ演算を使用して、CPUの回路が何かを追加するときに実行する処理をエミュレートすることを検討してください。さらに詳しく知りたい場合は、半加算器と全加算器に関するこのウィキペディアの記事を読むことを検討してください。あなたはそれと似たようなことをするでしょう、しかしあなたはそれと同じくらい低いレベルに行くことができます-しかし、怠けているので、私はただ先を見て、さらに簡単な解決策を見つけるだろうと思いました。

しかし、加算、減算、乗算に関するアルゴリズムの詳細に入る前に、データ構造を見つけましょう。もちろん、単純な方法は、std :: vectorに物事を保存することです。 

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

固定サイズのベクトルを作成するかどうか、および事前に割り当てるかどうかを検討する必要があります。理由は、さまざまな操作のために、ベクトルの各要素-O（n）を通過する必要があるからです。操作がどれほど複雑になるかをすぐに知りたいと思うかもしれませんが、固定nはまさにそれを行います。

ただし、数値の操作に関するいくつかのアルゴリズムについて説明します。ロジックレベルで実行できますが、その魔法のCPUパワーを使用して結果を計算します。しかし、Half-およびFullAddersの論理図から引き継ぐのは、キャリーを扱う方法です。例として、 + =演算子の実装方法を検討してください。 BigInt <！> lt; <！> gt; :: value_の各数値に対して、それらを追加し、結果が何らかの形式のキャリーを生成するかどうかを確認します。ビット単位で行うのではなく、BaseTypeの性質（longまたはintまたはshortまたは何であれ）に依存します。オーバーフローします。

確かに、2つの数字を追加する場合、結果はそれらの数字の大きい方より大きくなければなりませんよね？そうでない場合、結果はオーバーフローしました。

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

他の算術演算も同様です。ちなみに、stl-functors std :: plusおよびstd :: minus、std :: timesおよびstd :: dividesを使用することもできますが、キャリーに注意してください。 :)プラス演算子とマイナス演算子を使用して乗算と除算を実装することもできますが、それは非常に遅いです。なぜなら、それは各反復で以前のプラスとマイナスの呼び出しですでに計算した結果を再計算するからです。この単純なタスクには、使用 wikipedia またはウェブ。

そしてもちろん、operator<<などの標準演算子を実装する必要があります（value =の各値をnビットだけ左にシフトし、value_.size()-1 ...で始まり、キャリーを覚えてください：）、<= >-ここで少し最適化することもできます。最初にoperator<で大まかな桁数を確認します。等々。次に、befriendig std :: ostream size()を使用して、クラスを有用にします。

このアプローチが役立つことを願っています！

これに関する完全なセクションがあります：[コンピュータプログラミングの技術、第2巻：半数値アルゴリズム、セクション4.3多重精度算術、pp。265-318（ed.3）]。他の興味深い資料は、第4章「算術演算」で見つけることができます。

別の実装を実際に見たくない場合は、学習することを検討していますか？なすべき間違いは無数にあり、それらを発見することは有益であり、危険でもあります。重要な計算経済を特定し、深刻なパフォーマンスの問題を回避するための適切なストレージ構造を持つことにも課題があります。

あなたへのチャレンジ質問：実装をどのようにテストし、算術が正しいことを実証することをどのように提案しますか？

別の実装をテストする必要があるかもしれませんが（どのように実行するかを見ずに）、テストの厳しいレベルを期待せずに一般化できるようになるには、それ以上のものが必要になります。失敗モード（メモリ不足の問題、スタック不足、実行時間が長すぎるなど）を考慮することを忘れないでください。

楽しんでください！

追加は、おそらく標準線形時間アルゴリズムで行う必要があります
乗算するには、 http://en.wikipedia.org/wiki/Karatsuba_algorithm

配列に数値の数字が入ったら、手書きのように加算と乗算を正確に行うことができます。

数字として0-9に制限する必要がないことを忘れないでください。つまり、数字（0-255）としてバイトを使用し、10進数の場合と同じように長い手計算を行うことができます。長い配列を使用することもできます。

文字列を使用するのが正しい方法だとは確信していません-自分でコードを書いたことはありませんが、基本数値型の配列を使用する方が良い解決策になると思います。アイデアは、CPUが1ビットを整数に拡張するのと同じ方法で、既に得ているものを単純に拡張するというものです。

たとえば、構造がある場合

typedef struct {
    int high, low;
} BiggerInt;

各<！> quot; digits <！> quot;でネイティブ操作を手動で実行できます。 （この場合は高低）、オーバーフロー条件に注意してください：

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

これは少し単純化した例ですが、使用しているベース数値クラスの変数の数が可変である構造に拡張する方法はかなり明白なはずです。

他の人が言ったように、昔ながらのロングハンドのやり方でやりましょう。しかし、これをすべて10進数でやるのは避けてください。

1年生から4年生で学んだアルゴリズムを使用します。
1の列から始めて、10の列、というように続きます。

ターゲットアーキテクチャが数値のBCD（バイナリコード10進数）表現をサポートしている場合、必要なロングハンド乗算/加算のハードウェアサポートを取得できます。コンパイラーにBCD命令を発行させることは、読み進める必要があるものです...

Motorola 68Kシリーズチップにはこれがありました。私が苦いというわけではありません。

最初は、任意のサイズの整数の配列を使用し、31ビットと32n'dをオーバーフローとして使用します。

スターターopはADDであり、2の補数を使用したMAKE-NEGATIVEです。その後、減算は簡単に流れ、add / subを取得すると、他のすべてが実行可能になります。

おそらくもっと洗練されたアプローチがあります。しかし、これはデジタルロジックからの単純なアプローチです。

次のようなものを実装してみてください：

http://www.docjar.org/html/ api / java / math / BigInteger.java.html

1桁の0〜9に必要なのは4ビットだけです

したがって、Int値はそれぞれ最大8桁を許可します。文字の配列に固執することにしたので、メモリを2倍使用しますが、私にとっては1回しか使用されていません。

すべての数字を単一のintに格納する場合も複雑になり、速度が低下する可能性があります。

速度テストはありませんが、BigIntegerのJavaバージョンを見ると、非常に多くの作業を行っているようです。

私は以下を行います

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

整数の文字列から48を減算し、印刷して大きな数字を取得します。 次に、基本的な数学演算を実行します。    それ以外の場合は、完全なソリューションを提供します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top