81

プログラミング演習として、C++でbigintクラスを実装したいと思います。これは、longintよりも大きい数値を処理できるクラスです。すでにいくつかのオープンソースの実装があることは知っていますが、自分で書きたいと思います。私は正しいアプローチが何であるかを感じ取ろうとしています。

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

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

4

14 に答える 14

46

楽しいチャレンジ。:)

任意の長さの整数が必要だと思います。次のアプローチをお勧めします。

データ型「int」のバイナリの性質を考慮してください。単純な二項演算を使用して、CPU 内の回路が何かを追加するときに何をするかをエミュレートすることを考えてみてください。さらに詳しく知りたい場合は、半加算器と全加算器に関するこのウィキペディアの記事を読むことを検討してください。あなたはそれに似たようなことをしていますが、それと同じくらい低いレベルに行くこともできます.

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

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

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

しかし、ここで、数値を操作するいくつかのアルゴリズムについて説明します。ロジック レベルで実行することもできますが、その魔法の CPU パワーを使用して結果を計算します。しかし、Half-Adders と FullAdders の論理図から引き継ぐのは、キャリーを処理する方法です。例として、 += 演算子の実装方法を考えてみましょう。BigInt<>::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-functor std::plus と std::minus、std::times と std::divides を使用することもできますが、キャリーに注意してください。:) プラス演算子とマイナス演算子を使用して乗算と除算を実装することもできますが、それは非常に遅くなります。これは、反復ごとに以前のプラスとマイナスの呼び出しで既に計算した結果を再計算するためです。この単純なタスクには、ウィキペディアまたは Webを使用する ための優れたアルゴリズムがたくさんあります。

そしてもちろん、次のような標準演算子を実装する必要がありますoperator<<(value_ の各値を左に n ビットシフトするだけvalue_.size()-1です。... ああ、キャリーを覚えておいてoperator<ください :)、-ここで少し最適化して、おおよその桁数をsize()最初に付けます。等々。次に、 befriendig std::ostream によって、クラスを便利にしますoperator<<。

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

于 2008-11-06T20:59:34.097 に答える
37

大きなintクラスについて考慮すべきこと：

  1. 数学演算子：+、-、/、*、％クラスは演算子のいずれかの側にある可能性があり、演算子は連鎖可能であり、オペランドの1つはint、float、doubleなどである可能性があることを忘れないでください。

  2. I / O演算子：>>、<<ここで、ユーザー入力からクラスを適切に作成する方法と、出力用にクラスをフォーマットする方法を理解します。

  3. 変換/キャスト：big intクラスが変換可能である必要があるタイプ/クラス、および変換を適切に処理する方法を理解します。クイックリストにはdoubleとfloatが含まれ、int（適切な境界チェックを使用）とcomplex（範囲を処理できると仮定）が含まれる場合があります。

于 2008-11-06T16:18:47.063 に答える
29

これに関する完全なセクションがあります: [The Art of Computer Programming, vol.2: Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]。第 4 章「算術」で、他の興味深い資料を見つけることができます。

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

あなたへの挑戦的な質問: 実装をどのようにテストするつもりですか? また、その演算が正しいことをどのように実証することを提案しますか?

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

楽しむ！

于 2008-11-06T20:00:17.773 に答える
6

加算はおそらく標準の線形時間アルゴリズムで行う必要がありますが、乗算についてはhttp://en.wikipedia.org/wiki/Karatsuba_algorithm
を試すことができます。

于 2008-11-06T16:20:38.043 に答える
5

配列に数値の桁が入ったら、長い間行うのとまったく同じように加算と乗算を行うことができます。

于 2008-11-06T16:14:06.357 に答える
4

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

于 2008-11-06T16:15:47.053 に答える
3

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

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

typedef struct {
    int high, low;
} BiggerInt;

次に、オーバーフロー条件に注意しながら、各「桁」（この場合は高位と低位）に対して手動でネイティブ操作を実行できます。

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;
}

これは少し単純な例ですが、使用している基本数値クラスの変数番号を持つ構造に拡張する方法はかなり明白なはずです。

于 2008-11-06T16:22:03.873 に答える
2

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

于 2008-11-06T16:14:39.147 に答える
2

他の人が言ったように、昔ながらの長い道のりでそれを行いますが、これをすべてベース10で行うことは避けてください。すべてベース65536で行い、物事をロングの配列に格納することをお勧めします。

于 2008-11-06T16:19:49.760 に答える
1

ターゲットアーキテクチャが数値のBCD（2進化10進数）表現をサポートしている場合は、実行する必要のある長い乗算/加算のハードウェアサポートを取得できます。コンパイラにBCD命令を出力させることは、あなたが読まなければならないことです...

モトローラ68Kシリーズチップはこれを持っていました。私が苦いというわけではありません。

于 2008-11-06T16:20:45.670 に答える
0

私の出発点は、31ビットと32nをオーバーフローとして使用して、任意のサイズの整数の配列を作成することです。

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

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

于 2008-11-06T16:34:31.463 に答える
0

次のような実装を試すことができます。

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
于 2012-09-05T01:01:28.457 に答える
-1

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

于 2010-03-12T17:02:34.037 に答える