4

ご挨拶、

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

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

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

4

1 に答える 1

4

これをサポートするライブラリがあるかどうかはわかりませんが、それぞれの非常に大きな数(RBN)の一部でGMP/MPIRを使用できます。つまり、各RBNを管理しやすい均一なサイズのチャンクに分割することから始めます(たとえば、1,000万桁のチャンク、最上位桁には小さすぎるチャンクが必要です。以下も参照してください)。

    RBN1-> ABCDE
    RBN2-> FGHIJ

チャンクは10進数で実行できるため、各ピースのファイルから<chuck_size>文字を読み取るだけです。次に、各番号のチャンクを一度に1つずつ乗算します。

     AxF BxF CxF DxF ExF
    + AxG BxG CxG DxG ExG
    + AxH BxH CxH DxH ExH
    + AxI BxI CxI DxI ExI
    + AxJ BxJ CxJ DxJ ExJ

メモリ内の最終合計の各列を実行します。次に、キャリーをメモリに保持し、列をディスクに書き込み、次の列に対して繰り返します...キャリーの場合、各列の合計結果をGMPを使用して文字列に変換し、結果の下部の<チャンクサイズ>部分を書き出して読み取ります。キャリー用のGMPintとして上部が戻ってきます。

各列の加算をメモリに保持するために、乗算ごとにチャンクサイズを動的に選択することをお勧めします。数値が大きいほど、より多くの列の追加を行う必要があり、チャンクサイズを小さくする必要があります。

読み取りと書き込みの両方で、メモリマップトファイルを使用することをお勧めします。boostにはこのための優れたインターフェイスがあります(これはファイル全体をロードするのではなく、基本的に仮想メモリのIOをバッファリングするだけです)。入力RBN番号ごとに1つのマップされたファイルを開き、size = size(RBN1)+ size(RBN2)+1の出力を1つ開きます。メモリマップトファイルでは、ファイルアクセスはraw char *として扱われるため、gmpc-stringioメソッドを使用してチャンクを直接読み取り/書き込みできます。GMPの終了文字列をNULLにするために、おそらく中間バッファに読み込む必要があります(メモリマップトファイルを一時的に変更する場合を除く)。

これを正しく実装するのは簡単ではありませんが、これも特に簡単な問題ではありません(おそらく面倒です)。このアプローチには、GMPがメモリ内で実行していることを正確に反映するという利点があるため、アルゴリズムはよく知られています。

于 2010-06-06T18:13:51.450 に答える