問題タブ [gmp]

これと同様の質問が他にもあることは知っていますが、次の質問は、モンテカルロ シミュレーションで使用する C での任意精度の乱数生成に関するものです。

大気ノイズが常に利用できるとは限らない場合、ボトルネックを作成するディスク I/O やネットワーク アクセスに依存せずに、C で高品質の任意精度の乱数を生成するにはどうすればよいでしょうか?

libgmp は乱数を生成できますが、疑似乱数ジェネレーターの他の実装と同様に、シードが必要です。マニュアルに記載されているように、「システム時間は非常に推測しやすいため、予測不可能性が必要な場合は、シード値の唯一のソースであってはなりません。」

乱数または乱数のシードを生成するためのポータブル/移植ライブラリはありますか? libgmp には、「一部のシステムには、シードとしての使用により適したランダム データを提供する特別なデバイス /dev/random がある」と記載されています。ただし、/dev/random* nix システムでのみ/dev/urandom使用できます。

ご挨拶、

テキストファイルに保存されている2つの非常に長い整数値を乗算する必要があります（GMP（正確には、MPIR）を介してエクスポートされるため、どのベースでもかまいません）。さて、私は通常、mpz_inp_str（）関数を介してこれらの整数をインポートし、RAMで乗算を実行しますが、これらの値は長すぎるため、実際にロードすることはできません（それぞれ約1 GBのデータ）。これを行うための最速の方法は何でしょうか？おそらく、この種のことをすでに行っている外部ライブラリがいくつかありますか？このための簡単に実装できる方法はありますか（この操作は1回または2回しか実行されないため、パフォーマンスはそれほど重要ではありません）？

tl; dr：プロセスメモリの制限に収まらないほど大きな値を乗算する必要があります（Windows）。

お時間をいただきありがとうございます。

ご挨拶、

私のプログラムはコード3で終了します。エラーメッセージも例外もありません。また、終了は私のコードによって開始されません。

この問題は、テキストファイルから非常に長い整数値を読み取ろうとすると発生します（テキストファイルが存在し、正しく開かれ、事前に正常に読み取られます）。

非常に大量のメモリを使用しています（実際、プロセスあたり2GBのメモリ制限を超えているとほぼ確信しているため、これが原因である可能性があります）。また、GMP（またはMPIR）ライブラリを使用してbignumを乗算しています。完全にメモリ内にあった以前のプログラムバージョンで同じエラーコードが発生したため、これはファイルI/Oの問題ではないと確信しています。

システム：
MS Visual Studio 2008
MS Windows Vista Home Premium x86
MPIR 2.1.0 rc2
4GB RAM

このエラーコードはどこから発生したのでしょうか？

編集：これはコードで終了する手順です

EDIT2：完全にメモリ内のバージョンで、3で終了します

gmp.h ヘッダー ファイルを使用している間。mpz_t 型の入力を受け取り、mpz_t 型も返す関数が必要です。私はgmp.hを使用するのが非常に初心者なので、ここに私のアプローチしたコードのスナップがあります...

しかし、エラーが表示されます：

1. pow はこのスコープでは使用されていません。" とはいえ、ファイルの先頭に math.h を追加しました。
2. 配列を返す関数として宣言された sum_upto...

bignumの筆算を実装しようとしています。組み込みプログラミングの制限により、残念ながらGMPのようなライブラリを使用することはできません。その上、私はそれを実装する方法を学ぶ知的運動が欲しいです。これまでのところ、任意の長さのバイト配列を使用して加算と乗算を行っています（したがって、各バイトはベース256桁のようです）。

除算/モジュラスの実装を開始しようとしていますが、どこから始めればよいですか？ネット上で高度に最適化された（別名読み取り不可能な）コードをたくさん見つけましたが、それは私を助けません。また、理論と実装の間のギャップを埋めることができない高度に技術的な数学のホワイトペーパーをたくさん見つけました。 。

誰かが人気のあるアルゴリズムを推奨し、それが実装に傾いている簡単で理解しやすい説明を私に指摘できれば、それは素晴らしいことです。

-編集：被除数が約4000ビット、除数が約2000ビットの場合に機能するアルゴリズムが必要です

-編集：このアルゴリズムはbase-256で機能しますか？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-編集：これは私が実際に使用すべきアルゴリズム（ニュートン除算）ですか？http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

2^64 は、私の RAM/ハード ドライブが処理できる「無限」にはまだほど遠い...

最初に、GMP がメモリ/プロセッサでどのように機能するのか疑問に思います。GMP はある種の疑わしい最適化を行うためです...

また、任意のバイト数に整数 (符号なし、より簡単) を格納する方法があるかどうかも疑問に思っていました。たとえば、50 バイトの場合、上限は 2^400 -1 になります。やるべきことは、キャリーとうまく連携して、あるバイトから別のバイトへの数値の一貫性を保つことです.私はそれについていくつかの考えを持っていますが、それがこれを行うための最速の方法になるかどうかは本当にわかりません. 私が正しいかどうかさえわかりません。

GMP はこの種の方法でデータを保存していると思いますが、(少しでも) 説明をしたり、何らかの理論に転送したりしたいだけです (私は博士号を持っていないので、タフにならないでください)。

Windows の C++ プログラムで GMP を使用しようとしていますが、Cygwin で正常にコンパイルし、.lib ファイルの Linux バージョンである .a ファイルを取得しました。これを Visual C++ コンパイラで使用する方法はありますか、または Windows 用の GMP をコンパイルして .lib ファイルを生成する方法はありますか?

サイズのない long long が表すことができるよりも大きな範囲の数値を探索する準備をする必要があるという問題があります (範囲は 3^(n*n) で表されます)。このコミュニティから、多倍長数には GMP を使用するようアドバイスを受けました。一度に 1 つの数値の範囲を反復処理する必要があるため、カウンターを簡単にインクリメントする方法が必要です。

私の衝動は「mpz_add_ui(my_counter, my_counter, 1UL);」を使用することですが、戻り引数と加数の両方としてカウンターを渡すと、結果が破損する可能性があるのではないかと心配しています。関数が答えの計算中に return 演算子を変更すると、答えが間違った結果になるように数値が変更される可能性があります。インクリメントによって問題が発生する可能性は低いですが、大きな mpz_t を 2 つ追加する場合はどうでしょうか。または乗算、またはべき乗ですか？ドキュメントには、私の懸念を和らげたり確認したりするものは何もありません。ソース コードを調べてみましたが、マクロ、まばらなコメント、および 1 つのファイルから別のファイルへのジャンプの組み合わせにより、私はまだそれを理解するのに十分なプログラマーではないという結論に達しました。

安全のために、動作することがかなり確実な形式を示す関数を作成しましたが、プログラムの速度が低下することが確実であるため、むしろ避けたいと思います。

だから、私の質問はこれです。倍精度型を戻り引数とオペランドの 1 つとして GMP 算術関数に渡すことは安全ですか?それとも結果が破損することになりますか?

GMPは、mpf（浮動小数点）タイプの文字列シリアル化のみを提供しているようです。

mpf_get_str()、mpf_class::get_str()

mpz（整数）タイプには、rawバイト用の追加のインターフェースがあります。mpz_out_raw()

http://gmplib.org/manual/Function-Index.html

私は何かが足りないのですか？GMPフロートをシリアル化できる別のライブラリを知っている人はいますか？堅牢なシリアル化を提供する別のbignumlibを知っている人はいますか？

編集：MPFRのmpfr_tもシリアル化できれば幸いです。これは、同様に文字列出力しか提供しないようです：http ://www.mpfr.org/mpfr-current/mpfr.html#Function-Index

Mac OS 10.5.7 で GCC をクロスコンパイルしようとしています。GMP、MPFR、および MPC をインストールした後、次のコマンドを使用して GCC を構成しました。

このエラーが発生しました：

GCC が GMP、MPFR、および MPC のヘッダーを検出できたのに、ライブラリを検出できなかったのはなぜですか?