3

整数の任意精度演算をサポートする必要があるBigIntクラスを実装しています。

S.Skienaによる「アルゴリズム設計マニュアル」からの引用：

[編集者注：任意精度]の算術演算はどのベースで行う必要がありますか？-独自の高精度算術パッケージを10進数で実装するのがおそらく最も簡単であり、したがって、各整数を基数10桁の文字列として表します。ただし、より高いベースを使用する方がはるかに効率的です。理想的には、ハードウェア演算で完全にサポートされている最大の整数の平方根に等しくなります。

ハードウェア演算で完全にサポートされている最大の整数を見つけるにはどうすればよいですか？私のマシンがx64ベースのPCであるということを正しく理解していれば、サポートされる最大の整数は2 ^ 64（http://en.wikipedia.org/wiki/X86-64-アーキテクチャ機能：64ビット整数機能）であるはずです。 base 2 ^ 32を使用する必要がありますが、c ++でこのサイズをプログラムで取得して、base_typeをそれにtypedefできるようにする方法はありますか？

4

4 に答える 4

5

とを検索している可能性がstd::uintmax_tありstd::intmax_tます。

于 2012-08-18T12:12:43.103 に答える
2

static_cast<unsigned>(-1)最大整数です。たとえば、すべてのビットがに設定され1ていますそれはあなたが探しているものですか？

std::numeric_limits<unsigned>::max()またはを使用することもできますUINT_MAX。これらはすべて同じ結果になります。これらの値が示すのは、unsignedタイプの最大容量です。たとえば、符号なし型に格納できる最大値。

于 2012-08-18T12:14:12.993 に答える
1

int (and, by extension, unsigned int) is the "natural" size for the architecture. So a type that has half the bits of an int should work reasonably well. Beyond that, you really need to configure for the particular hardware; the type of the storage unit and the type of the calculation unit should be typedefs in a header and their type selected to match the particular processor. Typically you'd make this selection after running some speed tests.

INT_MAX doesn't help here; it tells you the largest value that can be stored in an int, which may or may not be the largest value that the hardware can support directly. Similarly, INTMAX_MAX is no help, either; it tells you the largest value that can be stored as an integral type, but doesn't tell you whether operations on such a value can be done in hardware or require software emulation.

Back in the olden days, the rule of thumb was that operations on ints were done directly in hardware, and operations on longs were done as multiple integer operations, so operations on longs were much slower than operations on ints. That's no longer a good rule of thumb.

于 2012-08-18T16:47:25.727 に答える
1

物事はそれほど白黒ではありません。ここには5月の問題があり、他にも検討する価値があるかもしれません。これで、2つの可変精度ツール（MATLAB、VPI、およびHPF）を作成し、それぞれで異なるアプローチを選択しました。また、整数形式と高精度浮動小数点形式のどちらを記述しているかも重要です。

違いは、整数は桁数に制限なく大きくなる可能性があることです。ただし、ユーザーが指定した桁数で浮動小数点の実装を行っている場合は、仮数の桁数が常にわかります。これは修正されました。

まず、10進数ごとに1つの整数を使用するのが最も簡単です。これにより、多くのことがうまく機能するため、I/Oが簡単になります。ただし、ストレージの点では少し非効率的です。ただし、加算と減算は簡単です。また、各桁に整数を使用すると、乗算も簡単になります。たとえばMATLABでは、convはかなり高速ですが、それでもO（n ^ 2）です。gmpはfft乗算を使用しているので、まだ高速だと思います。

ただし、基本的なconv乗算を使用すると仮定すると、桁数が膨大な数値のオーバーフローについて心配する必要があります。たとえば、10進数を8ビットの符号付き整数として格納するとします。convに続いてキャリーを使用すると、乗算を実行できます。たとえば、私が9999という番号を持っているとします。

N = repmat(9,1,4)
N =
     9     9     9     9

conv(N,N)
ans =
    81   162   243   324   243   162    81

したがって、9999 * 9999の積を作成する場合でも、数字が8ビットの符号付き整数でオーバーフローするため、注意が必要です。畳み込み積を累積するために16ビット整数を使用している場合、1000桁の整数のペアを乗算するとオーバーフローが発生する可能性があります。

N = repmat(9,1,1000);
max(conv(N,N))
ans =
       81000

したがって、数百万桁の可能性について心配している場合は、注意する必要があります。

1つの代替方法は、基本的に10より高いベースで機能するmigitsと呼ばれるものを使用することです。したがって、ベース1000000とdoubleを使用して要素を格納することにより、要素ごとに10進数の6桁を格納できます。ただし、畳み込みを使用すると、数値が大きくなるとオーバーフローが発生します。

N = repmat(999999,1,10000);
log2(max(conv(N,N)))
ans =
       53.151

したがって、長さが10000ミギット（10進数の60000桁）である2セットのベース1000000ミギット間の畳み込みは、doubleが整数を正確に表すことができないポイントをオーバーフローします。

繰り返しになりますが、数百万桁の数字を使用する場合は注意してください。畳み込みベースの乗算でより高い基数のミギットを使用することの良い点は、conv演算がO（n ^ 2）であるため、基数10から基数100に移動すると4-1のスピードアップが得られることです。ベース1000に移動すると、畳み込みで9-1のスピードアップが得られます。

最後に、10以外の基数をミギットとして使用すると、保護桁（浮動小数点の場合）を実装するのが論理的になります。浮動小数点演算では、計算の最下位ビットを信頼してはならないため、数桁を保持するのが理にかなっています。影に隠されています。そのため、 HPFツールを作成したときに、何桁を運ぶかをユーザーが制御できるようにしました。もちろん、これは整数の問題ではありません。

他にも多くの問題があります。これらのツールに付属しているドキュメントでそれらについて説明します。

于 2012-08-18T14:01:59.980 に答える