問題タブ [arbitrary-precision]

宿題として c++ 任意整数ライブラリを作成しています。数値を基数 10^n の unsigned int のベクトルとして内部的に表現しました。ここで、n は 1 つの unsigned int 数字に収まる範囲で可能な限り大きくします。

この選択は、スペース、パフォーマンス、数字アクセスの間のトレードオフとして行いました (人間が読める文字列に変換する際に複雑さを加えることなく、基数 10 を使用するよりもはるかに優れたパフォーマンスを得ることができます)。

たとえば、次のようになります。

base10(441243123294967295) 18桁

base1000000000(441243123,294967295) 2桁(カンマ区切り)

uint32 による内部表現

[00011010 01001100 11010101 11110011] [00010001 10010100 11010111 11111111]

宿題を完了するには、ビット シフトとその他のビット単位の演算子を実装する必要があります。そのような内部表現を持つ数値のシフトを実装することは理にかなっていますか?

内部表現のすべてのビットが有効になるように、基数 2^n に変更する必要がありますか?

I would like to create boost::spirit::qi::grammar for arbitrary integer. Storing integer to string just feels terrible wasting of memory especially when integer is represented in binary format. How could I use arbitrary precision integer class (e.g. GMP or llvm::APInt) in structure?

もちろん、GMPライブラリやその他の多数の任意精度ライブラリを使用するなど、これに対する簡単な解決策があることは知っています。これは授業用なので、これらのルートを使用することはできません。すべての操作を構築した後、RSA 暗号化スキームを実行できるようになります。

ベクトルを使用して、バイナリで表された n ビットの数値を格納しています。後で 10 進数に変換しますが、2 進数を操作し、表示用にのみ変換する必要があります。

足し算、引き算、掛け算の実装に成功しました。私は除算と剰余演算に固執しています...特に剰余累乗です。少なくとも基本的なレベルではアルゴリズムを理解していますが、それを任意の長さの数値で機能するコードに変換することはできないようです。外部ライブラリなしで c++ で行われたこのタイプの作業の例を見つけることができないようです。

具体的な質問:

私が書いている除算関数を呼び出して、返された剰余を使用する以外に、n ビットの数値でモジュラスを実行するより良い方法はありますか?

GMP ソース コードをまったく理解できないので、良い C++ の例をいくつか見てみたいと思います。

勉強するための良いリソースや助けをいただければ幸いです。ありがとう

このコードを使用すると、いくつかの奇妙な問題が発生しました。

iこのforループを繰り返すたびに、頻度を指定してイベントの発生数が発生する二項確率を計算する必要があります。各反復はまた、結果を合計します。これにより、prob変数が1を超えることはありませんが、ループの反復が7程度になると、すべてが地獄にprob落ちて1を超えます。

正確な数字の問題かもしれないと思ったので、Rmpfrを使ってみましたが、役に立たなかったのですが、同じ問題が解決しませんでした。

この状況を克服するためのヒントやパッケージがあるのか​​、それとも私がこれに固執しているのか疑問に思いました。

C/C++ 用の任意精度浮動小数点ライブラリを探しています (プレーン C が推奨されます)。任意精度の指数が必要です。GMP と MPFR は固定サイズの指数を使用するため、不適格です (回避策についていくつかのアイデアがありますが、すぐに使えるソリューションを好みます)。無限値を防ぐために指数の精度を自動的に調整できると便利な機能です。

そのようなライブラリが存在しないことが確実にわかっている場合は、そう言ってください。

製品を計算するための最も効率的な方法は何ですか

a ¹ b ² c ³ d ⁴ e5 ..。^_

二乗のコストが乗算の約半分であると仮定しますか？オペランドの数が100未満です。

乗算時間がオペランドの長さの2乗に比例する場合にも（のようにjava.math.BigInteger）簡単なアルゴリズムはありますか？

最初の（そして唯一の）答えは、操作の数に対して完璧です。

おかしなことに、かなりBigIntegerのサイズに適用すると、この部分はまったく問題になりません。最適化なしでabbcccddddeeeeeを計算する場合でも、ほぼ同じ時間がかかります。

ほとんどの時間は最終的な乗算に費やされます（BigIntegerカラツバ、トゥームクック、FFTなどのよりスマートなアルゴリズムは実装されていないため、時間は2次式です）。重要なのは、中間被乗数がほぼ同じサイズであることを保証することです。つまり、ほぼ同じサイズの数p、q、r、sが与えられた場合、 （pq）（rs）の計算は通常（（pq）r）sよりも高速です。速度比は、数十のオペランドで約1：2のようです。

アップデート

Java 8では、にカラツバ法とToom-Cook法の両方の乗算がありBigIntegerます。

同様のトピックに関するスレッドがいくつかあることを知っています ( C++ に最適な (速度の場合) 任意精度ライブラリは何ですか?および最高のクロスプラットフォーム (ポータブル) 任意精度数学ライブラリ) と私はこれらのスレッドから GMP または何かベースのものよりも取得しますMPFRが利用可能な最速のライブラリのようですが、私は特に疑問に思っています.30 decの場所だけを言いたいのであれば、quadmathライブラリの__float128の方が速いでしょうか?

また、MAPM は MPFR とどのように比較されますか?

このウェブサイトから見えます：

http://pari.math.u-bordeaux.fr/benchs/timings-mpfr.html

そのMPFRはかなりうまくいきますが、CLNとapfloatもありますか?

eを2兆（2,000,000,000,000）桁で計算したい。これは純粋なeの約1.8TiBです。GMPを使用してテイラー級数展開アルゴリズムを実装しました（コードはここにあります）。

残念ながら、私のコンピュータで4000を超える用語を合計すると、おそらくメモリが不足しているためにクラッシュします。

eのコンピューティングにおける現在の最先端技術は何ですか？どのアルゴリズムが最速ですか？検討する価値のあるオープンソースの実装はありますか？y-cruncherについては言及しないでください。これはクローズドソースです。

非常に長い整数 (10 進数で約 100,000 桁) の乗算の算術演算に取り組んでいます。ライブラリの一部として、2 つの長い数字を追加します。

プロファイリングによると、私のコードは add() および sub() ルーチンで時間の 25% まで実行されるため、可能な限り高速であることが重要です。しかし、私はまだ多くの可能性を見ていません。多分あなたは私に助け、アドバイス、洞察、またはアイデアを与えることができます. 私はそれらをテストし、あなたに戻ってきます。

これまでのところ、私の追加ルーチンはセットアップを行ってから、8 回展開されたループを使用します。

異なるオフセットを持つさらに 7 つのブロックが続き、ループします。

以前にメモリから値をロードしようとしましたが、それは役に立ちませんでした。これはプリフェッチが優れているためだと思います。Intel i7-3770 Ivy Bridge 4 コア CPU を使用しています。しかし、最新の CPU で適切に動作するコードを書きたいと思っています。

編集：いくつかのタイミングを取りました：約2.25サイクル/ワードで1kワードを追加します。ADC を削除すると、MOV だけが残り、1 ワードあたり約 1.95 サイクルかかります。したがって、主なボトルネックはメモリアクセスにあるようです。ライブラリmemcpy()は約 0.65 サイクル/ワードで動作しますが、入力は 2 つではなく 1 つだけです。それでも、SSE レジスタを使用しているため、はるかに高速だと思います。

いくつかの質問：

• 「ロード、ロード、追加、保存」構造を使用することは有用ですか、それとも「ロード、メモリへの追加」が役立ちますか? これまでのところ、私のテストでは利点は見られませんでした。
• いつものように、期待される SSE(2,3,4) からの助けはありませんか?
• アドレッシング (スケーリングされたインデックスとベースとオフセット) は悪影響を及ぼしますか? 代わりに使えますADD r11, 8。
• ループの展開はどうですか？Sandy Bridge アーキテクチャ (Agner Fog http://www.agner.org/optimize/ ) では展開が悪いと読みました。それは優先されるべきですか、それとも回避されるべきですか？
• (編集) SSE レジスタを使用してメモリから大きなチャンクに単語をロードおよび格納し、汎用レジスタおよび SSE レジスタと効率的に単語を交換できますか?

コメントをいただければ幸いです。

While I was working on my fast ADD loop (Speed up x64 assembler ADD loop), I was testing memory access with SSE and AVX instructions. To add I have to read two inputs and produce one output. So I wrote a dummy routine that reads two x64 values into registers and write one back to memory without doing any operation. This is of course useless, I only did it for benchmarking.

I use an unrolled loop that handles 64 bytes per loop. It is comprised of 8 blocks like this:

Then I upgraded it to SSE2. Now I use 4 blocks like this:

And later on I used AVX (256 bit per register). I have 2 blocks like this:

So far, so not-so-extremely-spectacular. What is interesting is the benchmarking result: When I run the three different approaches on 1k+1k=1k 64-bit words (i.e. two times 8 kb of input and one time 8kb of output) I get strange results. Each of the following timings is for processing two times 64 bytes input into 64 bytes of output.

• The x64 register method runs at about 15 cycles/64 bytes
• The SSE2 method runs at about 8.5 cycles/64 bytes
• The AVX method runs at about 9 cycles/64 bytes

My question is: how come the AVX method is slower (though not a lot) than the SSE2 method? I expected it to be at least on par. Does using the YMM registers cost so much extra time? The memory was aligned (you get GPF's otherwise).

Does anyone have an explanation for this?