10

私が理解している限り、BigInts は通常、数字を含む配列としてほとんどのプログラミング言語で実装されています。たとえば、2 つ追加すると、学校で知っているように、各数字が次々に追加されます。

 246
 816
 * *
----
1062

* は、オーバーフローがあったことを示します。私は学校でこの方法を学び、実装したすべての BigInt 追加関数は上記の例と同様に機能します。

したがって、プロセッサーが 0 から2^32/までの int のみをネイティブに管理できることは誰もが知っています2^64。

つまり、ほとんどのスクリプト言語は、高レベルで大きな整数を使用した算術演算を提供するために、上記のように整数を配列として扱う BigInt ライブラリを実装/使用する必要があります。しかしもちろん、これはプロセッサよりもはるかに遅くなることを意味します。

だから私が自分自身に尋ねたのは：

  • プロセッサーに BigInt 関数が組み込まれていないのはなぜですか?

他の BigInt ライブラリと同じように動作しますが、(はるかに) 高速で低レベルです。プロセッサはキャッシュ/RAM から 1 桁をフェッチし、それを追加して、結果を再度書き込みます。

私には素晴らしいアイデアのように思えますが、なぜそのようなものがないのでしょうか?

4

8 に答える 8

9

プロセッサがその仕事ではない大量のものを処理する必要がある問題が多すぎます。

プロセッサ DID にその機能があるとします。特定の BigInt が使用するバイト数を把握できるシステムを構築できます。ほとんどの文字列ライブラリと同じ原則を使用して、長さを記録するだけです。

しかし、BigInt 操作の結果が予約されたスペースの量を超えた場合はどうなるでしょうか?

次の 2 つのオプションがあります。

  1. それが持っているスペースの内側を包み込むか、
  2. より多くのメモリを使用します。

問題は、1) を行った場合、それは役に立たないということです。必要なスペースの量を事前に知る必要があり、それが BigInt を使用する理由の一部です。したがって、それらによって制限されることはありません。もの。

2) を行った場合は、何らかの方法でそのメモリを割り当てる必要があります。メモリ割り当ては、OS 間で同じ方法で行われるわけではありませんが、同じ方法で行われたとしても、すべてのポインタを古い値に更新する必要があります。何が値へのポインタであり、何が問題のメモリ アドレスと同じ値を含む単純な整数値であるかをどのように知るのでしょうか?

于 2010-04-12T20:07:16.053 に答える
8

Binary Coded Decimalは、文字列演算の形式です。Intel x86 プロセッサには、直接 BCD 算術演算用のオペコードがあります。

于 2010-04-12T20:06:59.057 に答える
3

乗算の結果が格納されるスペース (メモリ) の 3 倍を必要とするとします。プロセッサはその結果をどこに格納しますか? その結果へのすべてのポインターを含むその結果のユーザーは、サイズが突然変更されたことをどのように知ることができますか? サイズを変更すると、メモリ内で再配置する必要があり、現在の場所を拡張すると別の変数と衝突する可能性があります。

これにより、プロセッサ、OS メモリ管理、およびコンパイラの間で多くの相互作用が発生し、一般化と効率化の両方が困難になります。

アプリケーション タイプのメモリの管理は、プロセッサが行うべきことではありません。

于 2010-04-12T20:15:27.720 に答える
1

私が思うに、最新のプロセッサに bigint のサポートを含めないことの背後にある主なアイデアは、ISA を削減し、フルスロットルでフェッチ、デコード、および実行される命令をできるだけ少なくしたいという願望です。ところで、x86 ファミリーのプロセッサーには、大きな int ライブラリーを 1 日で作成できるようにする一連の命令があります。もう一つの理由は、価格だと思います。より高いレベルで簡単に実装できる冗長な操作を削除して、ウェーハ上のスペースを節約する方がはるかに効率的です。

于 2010-04-12T20:09:15.427 に答える
0

CPU チップ上の領域を争う命令や機能が非常に多いため、最終的には、より頻繁に使用される/より有用であると見なされるものが、そうでないものを押しのけます。BigInt 機能を実装するために必要な手順があり、計算は簡単です。

于 2011-02-21T12:49:21.420 に答える
-1

BigInt: 必要な基本的な関数は次のとおりです: 符号なし整数乗算、以前の高次を追加 Intel 16 ビット アセンブラーで作成し、次に 32 ビット... 通常、C コードは十分に高速です.. BigInt の場合は、ソフトウェア ライブラリを使用します。CPU (および GPU) は、符号なし整数を最優先として設計されていません。

独自の BigInt を作成する場合は...

除算は Knuths Vol 2 を介して行われます (いくつかのトリッキーなアドバックを伴う、多数の乗算と減算です)

キャリー付きの足し算と引き算は簡単です。などなど

Intel にこれを投稿しました: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx SSE4 BigInt ライブラリはありますか?

i5 2410M プロセッサ AVX は使用できないと思います [AVX はごく最近の Intel CPU にのみ搭載されています] が、SSE4.2 は使用できます

SSE 用の BigInt ライブラリはありますか? 符号なし整数を実装するものを探していると思います

PMULUDQ (128 ビットオペランドを使用) PMULUDQ __m128i _mm_mul_epu32 ( __m128i a, __m128i b)

そしてキャリーをします。

これはラップトップなので、NVIDIA GTX 550 を購入することはできません。xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

于 2011-10-13T04:21:43.407 に答える