問題タブ [arbitrary-precision]

整数リングでFFTを使用して、長い整数に任意の数字のベースを掛ける必要があります。n = 2^kオペランドは常に一部の長さkであり、畳み込みベクトルには2nコンポーネントがあるため2n'th、ユニティの原始根が必要です。

私は効率の問題に特に関心がないので、Strassen & Schönhage のアルゴリズムを使用したくありません。基本的な畳み込みを計算し、次にキャリーを計算するだけです。

多くの数学者にとっては単純に思えるかもしれませんが、私の代数の理解は本当によくないので、たくさんの質問があります:

1. 2^n + 1整数環モジュロ(おそらく複合) で FFT を実行する場合と、いくつかの素数を法とする整数 FIELDS でFFT を実行する場合の本質的な違いやニュアンスは何pですか?
   
   私がこれをお願いするの2は、(2n)thがそのようなリングにおける団結の原始根だから2^n == -1 (mod 2^n+1)です。対照的に、整数フィールドでは、そのような原始根を検索する必要があります。
   
   しかし、FFT にそのような形式のリングを使用することを妨げる他のニュアンスがあるかもしれません。

2. 整数環を選んだ場合2^n、この体に 1 乗根が存在するための十分条件は何ですか?
   
   より小さい次数の 1の他のすべての2^k乗根は、この根を 2 乗することで得られますよね?.

3. 環のモジュロによる乗算には、どのような本質的な制限が課せられますか? たぶん、それらの長さ、数値ベース、さらには乗算に使用される数値型についてです。
   
   畳み込みの係数がモジュロ演算によって削減されると、情報の損失が発生する可能性があると思います。それは本当ですか、なぜですか?.. これを回避できる一般的な条件は何ですか?
   
   

4. プリミティブ型の動的リスト (つまりlong) だけで、FFT ベクトル、その積、および畳み込みベクトルに十分である可能性はありますか? それとも、念のために係数を変換する必要がBigIntegerありますか (そして、本当に必要な場合の「ケース」とは何ですか)?

これらの質問に対する一般的な回答に時間がかかりすぎる場合は、次の条件での回答に特に満足します。2^30フィールド Z_70383776563201までの順序統一の原始根の表を見つけました。

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

したがって2^30、長さの数を乗算するために th root of unity を使用する場合2^29、考慮すべき精度/アルゴリズム/効率のニュアンスは何ですか?..

よろしくお願いします！最良の回答には報奨金を授与します - いくつかの例を手伝うことを検討してください。

こんにちは！

既に持っている単純な再帰的 FFT 実装に基づいて NTT アルゴリズムを開発しようとしています。

次のコードを考えてみcoefficientsましょう ( ' 長さmは正確に 2 のべき乗です)。

複雑なFFTで機能しましBigIntegerた（複雑な数値型に置き換えます（私は自分で持っていました））。統一の原始根を見つける手順を適切に変更したにもかかわらず、ここでは機能しません。

おそらく、問題は次のとおりです:渡されたパラメーターには、もともと次の順序で 1 の複素根のrootsOfUnity最初の半分しか含まれていませんでした:m

omega^0 = 1, omega^1, omega^2, ..., omega^(n/2)

これらの 3 行のコードでは次のようになっているため、これで十分でした。

私はもともと、任意のレベルの再帰 (任意のnandの場合i) で、 unity の複素根であるという事実を利用しました-omega^(i) = omega^(i + n/2)。

しかし、その性質は明らかに有限体では成立しません。しかし、根の前半だけを計算できる類似のものはありますか?

または、サイクルを から まで拡張し、n/2すべての1 乗根をn事前に計算する必要がありますか?m

たぶん、このコードには他の問題がありますか? ...

事前にどうもありがとうございました！

私はいくつかの非常に大きな数を操作する必要があるプロジェクト( Scala 内)に取り組んでいます。整数型で表すには大きすぎます。Java は BigInteger クラスと BigDecimal クラスを提供します (そして、scala はそれらを包む素敵な薄いラッパーを提供します)。ただし、これらのライブラリは、私が過去に使用した他の任意精度ライブラリ (つまりhttp://www.ginac.de/CLN/ ) よりも大幅に遅く、速度の差は考えられるよりも大きいようです。言語だけに。

プログラムのプロファイリングを行ったところ、実行時間の 44% が BigInteger 乗算メソッドに費やされました。プログラムを少し高速化したいので、BigInteger クラス (およびその Scala ラッパー) よりも高速で効率的なオプションを探しています。LargeInteger (JScience から) と Aint (Afloat から) を見てきました。ただし、どちらも標準の BigInteger クラスよりもパフォーマンスが遅いようです。

高性能の整数の乗算と加算に焦点を当てた Java (または JVM で利用可能な) 任意精度の数学ライブラリを知っている人はいますか?

ビルド済みの Windows バイナリに付属する多精度ライブラリを提案できる人はいますか。既存の Visual Studio 2010 プロジェクト (または、GMP 用の win7 64 ビット用のビルド済みバイナリを取得できる場所) で使用する必要があります。

私は GMP や MPIR などのプロジェクトをコンパイルしようとして失敗しましたが、どれもさまざまなイライラするあいまいなエラーで機能しません。残念ながら、時間のプレッシャーが私にかかっています。ライブラリを構築/ダウンロードできれば、実装する必要があるのは簡単です。

浮動小数点のサポートが必要なので、bigint ライブラリでは不十分です。

ありがとう、

vpaMatLabでS式を評価するために使用できるコマンドについて簡単な質問があります。

私の教科書には次のように書かれています。

「数値などの関数を使用する場合は注意が必要sqrtです。デフォルトでは倍精度浮動小数点数になります。vpa正しい評価を行うには、このような入力を記号文字列として渡す必要がありますvpa('sqrt(5)/pi')。」

ここでの専門用語はよくわかりません。vpa(input)ほとんどの入力で、入力するか入力するかにかかわらず、まったく同じ答えが得られるのに、vpa('input')平方根では得られないのはなぜですか？たとえば、vpa(sin(pi/4))またはを入力vpa('sin(pi/4)')するとまったく同じ答えが得られますが、上記の「giveproblem」をと入力するとvpa(sqrt(5)/pi)、と入力したときと同じ答えが得られませんvpa('sqrt(5)/pi')。

誰かが私の本が上でしたことよりもう少し詳細にこれを説明することができれば、私は非常に感謝するでしょう！

アセンブリ言語では、通常、2 つのオペランドとキャリーを追加する命令があります。大きな整数の加算を実装する場合は、最小の整数をキャリーなしで加算し、次の整数をキャリー付きで加算します。キャリー フラグにアクセスできない C または C++ で効率的に行うにはどうすればよいでしょうか。いくつかのコンパイラとアーキテクチャで動作するはずなので、単純にインライン アセンブリなどを使用することはできません。

GMPで操作するときに丸めモードを変更する方法はありますか？それとも、そのためにMPFRを使用する必要がありますか？

前もって感謝します！

値が に収まらないN バイナリ桁の整数を手動long longで出力するスケーラブルなアルゴリズムは何ですか? 私は知っているprintfし、友人も<iostream>(おそらくピギーバック<cstdio>は標準型にこの組み込みを持っていますが、N バイトで構成される整数に対してそれを行いたいと思っています。

私はこれについて考えて少しグーグルで検索しましたが、常にGMP（私がまったく慣れていないコードベース）または「printfを使用する」または最も役立つ「これは難しい」などの既存のbigintライブラリを使用することになります。 .

整数は基本的に次のとおりです。

Integer<4>したがって、のバイトを再解釈すると、 が得られますint32_t。これをN>8にスケーリングしたいと思います。効率性は、現時点ではあまり関心がありません。エンディアンでもありません (これは x86 用です)。

私はすでにGMP、MPFRを試しました。しかし、私は以下のような単純な除算を達成することはできません。ところで、私はXcodeにLLVMコンパイラを持っています。コンパイルして、IOSシミュレーターで実行しようとしています。

mpf_t a;

mpf_init2（a、256）;

mpf_set_d（a、0.7）;

mpf_t b; mpf_init2（b、256）;

mpf_set_d（b、1.0）;

mpf_t l; mpf_init2（l、256）;

gmp_printf（ "％。* Ff \ n"、5、a）; --- 0.70000

gmp_printf（ "％。* Ff \ n"、5、b）; ---1.00000

mpf_div（l、a、b）;

gmp_printf（ "％。* Ff"、5、l）; --- 0.52502

MPFRC++C++ プログラムで任意の精度が必要なため、多精度浮動小数点 C-libraryではなく、よく知られている軽量の C++ ラッパーを使用していますMPFR。

私はメモリの問題を抱えています。つまり、amallocは MPFR 関数内で失敗します。(興味がある場合は、下部にある小さなエラー メッセージ)。

MPFR マニュアルには次のように書かれています (10 ページ)。

MPFR 関数は、ユーザーが直接 mpfr_const_pi のような関数を呼び出したか、他の関数を計算するためにそのような関数が MPFR ライブラリ自体によって内部的に呼び出されたために、たとえば pi などの定数を計算するときにキャッシュを作成することがあります。

ユーザーはいつでも mpfr_free_cache を使用してさまざまなキャッシュを解放できます。スレッドを終了する前にそれを行うことを強くお勧めします...

私のプログラムは非常にマルチスレッド化されているため、これを使い始める必要があると思いますmpfr_free_cache。

質問:ラッピング クラスmpfr_free_cache()のデストラクタ に単純に配置できますか? これは安全で適切な方法ですか? 問題を解決するのに十分ですか?(メモリリークを正しく特定したと仮定して)

例えば

// mpreal.cpp - ラッパーの実装

私は本業の開発者ではないので、これが本当に問題を解決する最善の方法であるかどうかはわかりません。しかし、すべての OpenMP マルチスレッド領域/for ループに入り込み、mpfr_free_cache()...

注: スレッドセーフ オプションを使用して MPFR をビルドしました。

興味がある場合は、ここにそのエラーメッセージがあります...

エラー メッセージで参照されているコード: