14

オプションの割り当てとして、BigInteger クラスの独自の実装を作成することを考えています。ここでは、加算、減算、乗算などの独自のメソッドを提供します。

これは、数百桁の長さであっても、任意の長さの整数用です。

これらの数値の計算を行っている間、1 桁ずつ計算するのは難しくありません。私の「BigInteger」を表すのに最適なデータ構造は何だと思いますか?

最初は配列の使用を検討していましたが、大規模な加算または乗算の後、まだオーバーフロー (配列スロットが不足) する可能性があると考えていました。O（1）時間の複雑さで数字を追加できるので、これはリンクされたリストを使用する良いケースでしょうか?

リンクされたリストよりも適している他のデータ構造はありますか? 私のデータ構造が保持する型は、私が利用できる最小の整数型であるべきですか?

また、「キャリー」変数の保存方法に注意する必要がありますか? それ自体は、私の「BigInteger」タイプである必要がありますか?

4

10 に答える 10

3

David R. Hanson著のC Interfaces and Implementationsを参照してください。ベクトル構造、単語サイズ、および遭遇する可能性が高い他の多くの問題をカバーする主題に関する 2 つの章があります。

C 用に書かれていますが、そのほとんどは C++ や Java に適用できます。std::vectorまた、C++ を使用すると、配列の割り当てを管理するようなものを使用できるため、少し簡単になります。

于 2010-02-08T19:08:39.010 に答える
1

うわー、いくつか… 興味深い答えがあります。この矛盾したアドバイスをすべて整理しようとするよりも、本を読むことをお勧めします。

とはいえ、C/C++ もこのタスクには適していません。big-integer は一種の拡張精度数学です。ほとんどの CPU は、通常の演算と同等または同じ速度 (命令あたりのビット数) で拡張精度の演算を処理するための命令を提供します。2^32+2^32 を加算すると、答えは 0 になりますが、プログラムが読み取って使用できるプロセッサの ALU からの特別なキャリー出力もあります。

C++ はそのフラグにアクセスできず、C にも方法がありません。アセンブラを使用する必要があります。

好奇心を満たすために、標準のブール演算を使用してキャリー ビットなどを復元できます。ただし、既存のライブラリをダウンロードする方がはるかに優れています。

于 2010-02-08T22:02:44.957 に答える
1

必要なジョブを実行する最小の int 型 (バイト) を常に使用します。リンクされたリストは、オーバーフローを心配する必要がないため、うまく機能するはずです。

于 2010-02-08T19:08:16.900 に答える
1

二分木 (リーフが int である) を使用すると、リンクされたリストのすべての利点 (無制限の桁数など) を、より単純な分割統治アルゴリズムで利用できます。この場合、単一のベースはありませんが、作業しているレベルに応じて多くのベースがあります。

これを行う場合、キャリーに BigInteger を使用する必要があります。キャリーを常にintとして表すことができるという「intのリンクリスト」アプローチの利点と考えることができます（これは、ほとんどの回答が使用する必要があると想定しているように見えるため、基数10だけでなく、基数にも当てはまります。 .. どのベースでも、キャリーは常に 1 桁です)

2^30 や 2^31 が使えるのに、基数 10 を使うのはもったいないです。

于 2010-02-08T19:10:12.083 に答える
1

リンクされたリストの要素へのアクセスは遅いです。必要に応じて多くの境界チェックと実行時の配列のサイズ変更を行うことで、配列が進むべき道だと思います。

明確化: リンクされたリストのトラバースと配列のトラバースは、どちらも O( n ) 操作です。ただし、リンクされたリストをトラバースするには、各ステップでポインターを参照する必要があります。2 つのアルゴリズムの複雑さが同じだからといって、両方の実行に同じ時間がかかるとは限りません。リンク リスト内のnノードの割り当てと割り当て解除のオーバーヘッドは、配列のサイズを数回変更する必要がある場合でも、サイズnの単一の配列のメモリ管理よりもはるかに重くなります。

于 2010-02-08T19:10:37.060 に答える
0

std::vector<bool>またはstd::vector<unsigned int>おそらくあなたが望むものです。乗算などのためにより多くのスペースが必要なため、 topush_back()またはresize()on にする必要があります。また、2 補数を使用している場合は、正しい符号ビットを push_back することを忘れないでください。

于 2010-02-08T19:18:03.563 に答える
0

私はintの配列と言うでしょう。

于 2010-02-08T19:04:56.267 に答える
0

私は char の std::vector と言います (0-9 のみを保持する必要があるため) (BCD で作業する場合)

BCDでない場合は、intのベクトルを使用します（明確にしませんでした）

リストをリンクするよりもスペースのオーバーヘッドがはるかに少ない

そして、すべてのアドバイスは、「正当な理由がない限りベクターを使用してください」と言っています

于 2010-02-08T19:07:16.717 に答える
0

配列は確かに自然にフィットします。メモリが不足している場合は、OverflowException をスローしても問題ないと思います。先生は細部まで注意を払います。

乗算は桁数をおよそ 2 倍にし、加算は最大で 1 だけ増やします。操作の結果を格納するのに十分な大きさの配列を作成するのは簡単です。

キャリーは、乗算では最大でも 1 桁の長さの数値です (9*9 = 1、キャリー 8)。単一の int で十分です。

于 2010-02-08T19:08:09.433 に答える
0

経験則として、シーケンスの途中に要素を頻繁に挿入する必要がない限り、std::vector代わりに, を使用します。std::listベクターは連続して格納されるため、より高速になる傾向があり、より優れた空間的局所性 (最新のプラットフォームの主要なパフォーマンス要因) の恩恵を受けます。

プラットフォームに自然な要素を使用するようにしてください。プラットフォームに依存しないようにしたい場合は、 を使用してlongください。特別なコンパイラ組み込み関数を使用できない限り、乗算を実行するには、少なくとも 2 倍の大きさの型が必要になることに注意してください。

キャリーを大きな整数にしたい理由がわかりません。キャリーは、加算の場合は 1 ビットで、乗算の場合は要素サイズです。

Knuth の Art of Computer Programming を必ず読んでください。任意精度の算術演算に関連するアルゴリズムがかなり詳しく説明されています。

于 2010-02-08T20:24:10.183 に答える