3

パフォーマンスに関してどちらが優れているかを判断するための助けが必要です。私はbigint （500万桁以上）を扱っており、ほとんどの計算（すべてではないにしても）は現在のbigintを2倍にすることです。したがって、すべてのセル (bigint の一部) に 2 を掛けてから、それを mod にすると残りがわかるということを知りたかったのです。それとも、それ自体に bigint を追加するだけの方がよいでしょうか。

実装の容易さについても少し考えています (2 つの bigint の加算は 2 の乗算よりも複雑です) が、コードのサイズや実装の容易さよりもパフォーマンスに関心があります。

その他の情報: C++でコーディングします。bigint にはかなり精通しています (この問題に遭遇したことはありません)。プロジェクトはかなり大きく、ほとんどがこの部分を中心に構築されるため、最初から適切な決定を下す必要があるため、ソースコードなどは必要ありません。良い意見と説明/証拠が必要です。それは私が今何を選んだかに大きく依存します。

ありがとう。

4

7 に答える 7

9

各ビットをビットシフトしてみてください。それがおそらく最速の方法です。整数を左にビットシフトすると、2 倍になります (2 倍します)。チェーンに複数の長整数がある場合は、最上位ビットを格納する必要があります。これは、シフト後に失われるため、次の長整数の最下位ビットとして使用する必要があるためです。

これは実際には大した問題ではありません。最新の 64 ビット コンピューターは、2 つの整数をビットシフトするのに必要な時間 (1 クロック サイクル) で加算できるため、同じくらいの時間がかかります。別の方法を試して、大きな時間差がある場合は報告することをお勧めします。3 つの方法はすべて簡単に実装できる必要があり、乱数ジェネレーターを使用して 5mb の数値を生成するのも簡単なはずです。

于 2009-08-11T15:18:20.033 に答える
5

500 万桁の整数を格納するには、かなりの数のビットが必要です。2 進数の場合は 500 万ビット、10 進数の場合は最大 1700 万ビットです。数値が 2 進表現で格納され、演算が 32 ビットや 64 ビットなどのサイズのチャンクで行われると仮定しましょう。

  • 数字をそれ自体に追加する場合、各チャンクはそれ自体に追加され、前のチャンクの追加からのキャリーに追加されます。繰り越しは、次のチャンクのために保持されます。これは、いくつかの追加操作であり、キャリーを追跡するための簿記です。

  • 左シフトによって 2 を乗算する場合、それは乗算のための 1 つの左シフト操作であり、キャリーを取得するための 1 つの右シフト操作 + と 1 です。キャリーブックの保管は少し簡単です。

表面的にはシフトバージョンの方が若干速く見えます。ただし、数値を 2 倍にする全体的なコストは、数値のサイズに大きく影響されます。1700 万ビットという数値は CPU の L1 キャッシュを超えており、処理時間はメモリ フェッチ操作に圧倒される可能性があります。最新の PC ハードウェアでは、メモリ フェッチは加算やシフトよりも桁違いに遅くなります。

そのため、実装がより簡単なものを選択することをお勧めします。私は左シフトバージョンに傾いています。

于 2009-08-11T15:28:09.717 に答える
1

ビットをシフトしてみましたか？
<< 2 倍する
>> 2 で割る

于 2009-08-11T15:18:30.203 に答える
1

1 だけ左にシフトすることは、2 を乗算することと同じです。
このリンクはメカニズムを説明し、例を示します。

int A = 10; //...01010 = 10
int B = A<<1; //..010100 = 20
于 2009-08-11T15:24:09.960 に答える
0

計算の大部分 (すべてではないにしても) は、現在の bigint を 2 倍にする部分です。

すべての計算が数値を 2 倍にすることである場合、別個の (基数 2) スケール フィールドを保持しないのはなぜですか? 次に、スケールに1つ追加するだけです。これは、昔ながらのintにすることができます。これは、数百万ビットの操作よりも確実に高速です。

IOW、bigfloat を使用します。

ランダムベンチマーク

use Math::GMP;
use Time::HiRes qw(clock_gettime CLOCK_REALTIME CLOCK_PROCESS_CPUTIME_ID);

my $n = Math::GMP->new(2);
$n = $n ** 1_000_000;

my $m = Math::GMP->new(2);
$m = $m ** 10_000;

my $str;
for ($bits = 1_000_000; $bits <= 2_000_000; $bits += 10_000) {
    my $start = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    $str = "$n" for (1..3);
    my $stop = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    print "$bits,@{[($stop-$start)/3]}\n";
    $n = $n * $m;
}

何らかの形で GMP が O(n) 時間 (n は 2 進数のビット数) で変換を行っていることを示しているようです。これは、1 の後に 100 万個 (または 2 個) のゼロが続くという特殊なケースが原因である可能性があります。GNU MP のドキュメントには、もっと遅いはずだと書かれています (ただし、O(N^2) よりも優れています)。

http://img197.imageshack.us/img197/6527/chartp.png

于 2009-08-11T15:50:33.667 に答える
0

それが本当に重要な場合は、3 つのメソッド (ビットシフトを含む!) をすべて記述し、さまざまな入力でプロファイルする必要があります。(結果にバイアスがかからないように、小さな数、大きな数、および乱数を使用してください。)

「自分でやる」という回答で申し訳ありませんが、それが本当に最善の方法です。あなた以上にこの結果を気にかけている人はいません。

于 2009-08-11T15:42:03.463 に答える
0

BigNums の適切に実装された乗算は O(N log(N) log(log(N)) です。加算は O(n) です。したがって、それ自体に加算する方が 2 を乗算するよりも高速です。ただし、これは、乗算している場合にのみ当てはまります。 2 つの任意の bignum; ライブラリが bignum に小さな整数を掛けていることを認識している場合、O(n) に最適化できる可能性があります。

他の人が指摘したように、ビットシフトもオプションです。それもO（n）である必要がありますが、一定時間は高速です。ただし、bignum ライブラリがビット シフトをサポートしている場合にのみ機能します。

于 2009-08-11T16:01:09.493 に答える