問題タブ [arbitrary-precision]

I recently came across the subject of exact real arithmetic after reading this paper and this paper.

I have found a number of papers that discuss realizations of exact arithmetic using signed digit streams. The use of infinite streams for arbitrary precision leads to nice practical implementations in functional languages, like Haskell, using lazy lists. However, the papers that discuss such implementations in functional languages seem to come to the conclusion that performance is very poor.

Now, I appreciate that exact, non-hardware implementations will generally have relatively poor performance compared to the standard floating-point representation, but I am interested in providing a more efficient implementation in an imperative language (specifically, C++) and a collection of operations/functions (arithmetic operations, trigonometric functions, exp, log, etc.).

My question(s): is there something inherently slow about a signed digit/lazy stream representation that causes the bad performance, or is it Haskell? What is it that makes it slow? Would it be possible to implement a signed digit stream representation using lazy streams in C++ that achieves (significantly) better performance than its Haskell counterpart, or is this an exercise in futility? Perhaps reconstructing as iterations?

I know there exists two C++ libraries, RealLib and iRRAM, that achieve efficient real number computation. However, these seem to use interval arithmetic, representing real numbers as shrinking nested intervals, which doesn't seem as 'pure' an approach as infinite streams (please correct me if you disagree!). But perhaps these are the only approaches that achieve good efficiency?

Any input is appreciated!

これはおそらく以前に尋ねられた可能性がありますが、関連するものは見つかりませんでした。

特殊なクラスまたは整数の任意/固定量の構造体を介して、一種の任意/10進数演算を実装することは可能/パフォーマンスですか?

明確にさせてください。フロート（私が理解しているように）、仮数、指数、およびおそらく符号ビットを使用します。2 分の 1、4 分の 1、8 分の 1 などを表すことはできますが、10 分の 1 などはできません。

私が提案するのは次のようなものです: 整数の範囲で完全にカバーされる 10 の累乗までの値のみを保持して、数値をプレーンintまたはint64_t一連のこれらで表すようにします (つまり、32 ビットの int の場合、制限は 10^8-1 になります)。これは、計算を簡単にするためだけです。これに指数を追加します。これは、実数を得るために 10 の何乗する必要があるかを示します。

例: 125.36 は、int12536 に等しく、10 の累乗が -2 に等しいことで表されます。この数は実際には s と同じくらい多くintの特別な関数を必要とします。

別の例: 4,294,967,297 (2^32+1) は 2 つintの s を取り、1 つは 4 に等しく、もう 1 つは 294,967,297 に等しく、10 の累乗は 0 に等しくなります。

これは、より単純で高速な演算のためにすべてのメモリを捨ててよい考えですか? オーバーフローの部分についてはよく考えていませんが、おそらく計算int32_t+int32_t=int64_tするとそれが美しく解決されるでしょうか?

重複の可能性:
Objective-c の biginteger

C#のBigIntegerのように、目的のcに任意のサイズの整数用のNS *クラスはありますか? そうでない場合、gmpはインポートするのに適したライブラリですか、それともより良いライブラリ/方法がありますか? 必要な操作は、足し算、引き算、掛け算、割り算 (切り捨てあり) です。このアプリケーションではメモリが大きな問題になるため、メモリ使用量が最も少ないアプリケーションが最適です。1 回の操作に何年もかからない限り、実行時間は問題になりません。

私はGMPライブラリを使用して円周率プログラムを作成しています。これは約7兆桁の円周率を計算します。問題は、小数点以下の桁数を保持するために必要なビット数がわからないことです。

16 ビット組み込みデバイス (80251 マイクロコントローラー) 用のアプリケーションを開発していますが、任意精度の演算が必要です。8051 または 80251 で動作するライブラリを知っている人はいますか?

GMP は明示的に 8051 をサポートしていません。

ありがとう

JavaScript で次のことを行う必要がありますが、これまでシームレスに実行するためのソリューションを見つけることができませんでした:

• 2 つの整数を特定の順序で取得し、Python の struct モジュールのようにパックします。

• このパックされた値 (ホストとは異なるエンディアンをサポートするためのボーナス) は、64 ビット float (double) に変換されます。それらは任意である必要があるため、整数の指数表現を取得する可能性があります (たとえば、0xdeadbeef と 500 である可能性があります)。

  exp 形式: 1.0883076389305e-311 1.0883076389305000 * 10 ^ - 311

• それを任意精度の非指数形式に変換する必要があるので、次のようにします。

  0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000108830763893050000000000000000000000000000000000000000000000000000000000000000000000000000

• その数値は文字列に変換されました:)

Javascript でこれを行う方法が見つからず、任意の精度、または少なくとも倍精度の 1024 指数 (または、400) までのスケールをサポートする必要があるような数値を出力する必要があります。

ありがとう！！

注: double/64bit float に変換された 2 つの数値を忠実に表現するには、「packing/unpacking」が必要です。 double の任意精度の double 表現を取得しても問題ありません。

ネイティブ (c) 任意精度ライブラリを使用できるように Python のインタープリターをコンパイルして、Python が decimal クラスを使用する代わりに、通常の数値であるかのように任意精度を使用できるようにする方法はありますか?

例えば。

numpy 2d 配列 [中/大サイズ - 500x500 と言う] があります。それの要素ごとの指数の固有値を見つけたいです。問題は、一部の値が非常に負 (-800、-1000 など) であり、それらの指数がアンダーフローすることです (つまり、値がゼロに非常に近いため、numpy はそれらをゼロとして扱います)。numpyで任意の精度を使用する方法はありますか?

私が夢見ている方法：

gmpy と mpmath を使用して解決策を探しましたが、役に立ちませんでした。どんなアイデアでも大歓迎です。

現在、PHP で任意精度の数値を扱う方法を見つけようとしています。したがって、私の最初の質問は、正確には任意精度の数学とは何かということになると思います。私は良い定義のためにグーグルを試しましたが、何らかの理由で誰もそれを十分に簡単な言葉で表現することはできません.

次に、PHP の BCMath ライブラリと GMP ライブラリの違いは何ですか? GMP の API は「より新しい」という主張を聞いたことがありますが、そうではありません。1つが良いですか？

そして私の最後の質問は、BCMath/GMP がどのような種類の数値を取るかということです。明らかに、文字列形式の通常の整数 (例: "5.34") を使用しますが、BCMath 関数が通常の整数を表すオクテット文字列 (例: "\x12\x23\x45\x67") で直接使用されている実装を見てきました。 「bigint」と呼ばれていると聞いたことがありますが、Google からは何も得られませんでした。

MSVC++固有の任意精度ライブラリを探しています。私が作業しているものにクロスプラットフォームの互換性は必要ないので、すべてを台無しにしたくはありません。

NTLを見てみましたが、「これらの手順はMSVC ++ v6で機能します」などのステートメントを見ると、時代遅れとして精神的に埋めるしかありません。最新のビルド： 2009 08 14。

MPIRは有望に見えます（最新のビルド2011 06 14）。これは私がこれまでに見つけた中で最高のものです。

MSVC ++（.NETではなくネイティブコード）から少なくとも128ビットの浮動小数点演算を実行するための提案はありますか？