問題タブ [arbitrary-precision]

この計算機をパブリック IRC ボットで使用しています。Python がデフォルトで任意の精度を使用することを考えると、これにより、任意のユーザーがボットのようなものを実行しcalc 10000**10000**10000たりcalc factorial(1000000)、ボットを効果的に「殺す」ことができます。

私が知りたいのは、これを回避する方法があるかどうかです。式のすべての用語を float にキャストしようとしましたがfloat(factorial(1000000)、Python インタープリターで終了するのにまだ長い時間がかかります。マルチスレッド アプローチがこれを行う正しい方法かどうかはわかりません。

x86-64上のhig-performanceネイティブbig-integerライブラリは、メモリ内の大きな整数をどのように表しますか？（またはそれは異なりますか？最も一般的な方法はありますか？）

^{素朴に私はそれらを基数264}の0で終わる数の文字列として保存することを考えていました。

たとえばX、メモリ内に次のようにあるとします。

B = ^{264とします}

それで

X = D _n * B ⁿ + ... + D ₂ * B ² + D ₁ * B ¹ + D ₀

空の文字列（つまり、8バイトのゼロ）はゼロを意味します。

これは合理的な方法ですか？この方法の長所と短所は何ですか？もっと良い方法はありますか？

署名をどのように処理しますか？2の補数はこの可変長値で機能しますか？

（これが見つかりました：http：//gmplib.org/manual/Integer-Internals.html 手足は何ですか？）

私は C++ で CPLEX を使用して、ハブの場所の問題である MIP を解決しています。最近、問題が確かに実行可能であるにもかかわらず、CPLEX が実行不可能と考える非常に正確な入力セット (つまり、CPXMIP_INFEASIBLE) を見つけました。この問題は、MIP Presolve 中に CPLEX で発散するように見えます。通常、その時点で問題はヌル問題に縮小されますが、実行不可能な入力セットには含まれません。

入力データをわずかに調整すると、CPLEX のソリューションを見つける機能が切り替わる可能性があることがわかりました。たとえば、250.242566 を 250.242567 に変更するか、各入力値を最も近い整数に丸めるだけでも、完全に有効なソリューションが得られます。

私が持っている 2 つのスラック制約を緩和することも解決策を可能にしますが、これらの制約は入力データを考慮して破られるべきではありません。解決後のこれらの制約変数の値は、約 0 ですが、わずかに負の値 (-0.7e-10 など) です。(値が 0 より大きいはずなので、これは疑わしいです。)

何が起こっている？私は無知です。精度に関連するいくつかの CPLEX 変数 (つまり、CPX_PARAM_NUMERICALEMPHASIS、CPX_PARAM_EPOPT、CPX_PARAM_EPMRK、CPX_PARAM_EPRHS) を調整しようとしましたが、何も役に立ちませんでした。入力データ自体はあまり精度を必要としません。入力の最小値は 1.412 で、最大値は 1520.984907 です。

アドバイスや提案をいただければ幸いです。

アップデート：

MIP の Presolve 中に、実行不可能な問題が実行可能な問題から分岐していることに気付きました。

両方の問題について CPXgetprestat をチェックすると、2 つの問題の間に見られる顕著な違いの 1 つは、pcstat ベクトルにあり、実行不可能なセットで 1 つの変数を集約できないことです (つまり、実行不可能な問題では値が 0 であるのに対し、実行可能な問題では -4 です)。 .

また、CPXgetprestat の ocstat および orstat ベクトルは、実行不可能な問題にゼロ以外の値をそれぞれ 1 つずつ持っています (実行可能な問題は、ヌル問題に縮小されているため、値はありません)。orstat[0] == 7 かつ ocstat[0] == 1 の場合、Presolve 前の問題の 7 行目と 1 番目の変数に何か注目すべき点があるということですか? これを確認するにはどうすればよいですか？

両方の問題で CPXwriteprob の出力を比較しましたが、問題を実行不可能にするために 0.0001 だけ変更した入力値以外に違いはありません。

私のPythonコードでは、を使用していくつかの計算を定期的に検証していnumpy.allcloseます。一方、これらのチェックとは別に、実装は多倍長（mpmath.mpc）数を処理できます。番号の確認コードを実行したい場合は、次のmpmathようになります。

2つの多倍長配列が十分に等しいかどうかを確認する最良の方法は何ですか？

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

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

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

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

これは一部の人にとっては非常に単純な質問かもしれませんが、 BigIntegerの JavaDoc の最初の行に表示される任意精度の意味を知りたいです。

不変の任意精度の整数。

Windowsで比較的簡単に実装できるライブラリはありますか？少し前に、数値の配列を使用して目的の結果を得るための関数をいくつか作成しました。時間があれば彼らで働くかもしれません。

しかし、C ++に簡単に実装できるそのような機能はすでに利用可能ですか？

Objective C で任意精度の数値の表現に対してビット操作を行う必要があります。これまでのところ、数値を保持するために NSData オブジェクトを使用してきました。それらの内容をビット シフトする方法はありますか? そうでない場合、これを達成する別の方法はありますか？