Next: , Previous: , Up: GMP Basics   [Index]


3.11 高速計算のための諸注意

小さい値に対する演算

扱う値が小さい時には,計算時間よりも関数呼び出しやメモリ割り当てに要する時間の方がシビアに効きます。標準データ型を使う際には不可避のことではありますが,GMPでは,桁の長短に応じてこのオーバーヘッドを調節して効率化を図っています。

スタティックライブラリの利用

CPUによっては,特に,x86系統では,スタティックライブラリlibgmp.aを使うと高速に実行できるようになります。これは,ダイナミックライブラリにおけるPICコードで,関数やグローバルデータの呼び出しに要する小規模なオーバーヘッドが発生することに起因します。大方のプログラムでは大した問題にはなりませんが,長時間にわたる計算を実行するとじわじわ効いてくるでしょう。

変数の初期化と解放

変数に対して初期化や解放を連続的に行わないようして下さい。加算のように軽い演算に比べ,結構な時間を食われてしまいます。

インタプリタの場合,解放した変数リストや,初期化済みの使用可能な変数のスタックを保持している場合があり,これによってガベージコレクションが可能になります。

メモリ空間の再確保

mpz_t型とmpq_t型の変数は逐次的に桁を増やしていくものなので,その都度realloc関数を使ってメモリ空間を再確保することになります。当然,低速になったり,メモリ空間の断片化が起こったりしますが,その程度はCライブラリ次第です。アプリケーション側で予め最大サイズが分かっているのであれば,mpz_init2関数かmpz_realloc2関数を呼び出して,最初から必要スペースを確保しておくこともできます。(see Initializing Integers).

mpz_init2関数やmpz_realloc2関数で確保したサイズが小さすぎるということは気にする必要はなく,全ての関数は必要に応じて桁が収まるようにメモリ空間の再確保を行います。むしろ,メモリを余分に取り過ぎる方が無駄というものです。

2exp関数

mpz_mul_2expのような関数を適切な所に使うとアプリケーションの性能向上が見込めます。とはいえ,こういう被演算数が特殊な場合を演算ごとに確認するのは時間の無駄なので,mpz_mul関数のような汎用演算関数を2のべき乗や高速化が見込める形の演算用として使うのは止めましょう。

ui関数 と si 関数

ui関数や,少数ながら存在するsi関数は,利用可能なケースには便利です。とはいえ,例えば mpz_t型に値が入っていて,これがunsigned long型に収まる桁数である場合は,わざわざこれをunsigned long型に取り出して使うメリットはなく,そのまま通常のmpz関数を使った方が得策です。

同じ変数に対する演算

mpz_abs, mpq_abs, mpf_abs, mpz_neg, mpq_neg, mpf_negといった関数は,mpz_abs(x,x)というように,同じ変数に対する処理は高速に行います。 現在の実装では,xという一つのフィールドだけを変更するだけで済むからです。これに向いているコンパイラ(例えばGCC)においてはインラインとして実行できます。

mpz_add_ui, mpz_sub_ui, mpf_add_uimpf_sub_uiといった関数も,mpz_add_ui(x,x,y)という一変数演算に向いており,xの1,2リム変更するだけで済みます。yの桁数が短い時には同様のことがフル精度のmpz_add等の関数にも言えます。yが長い桁であっても,全桁計算しますがキャッシュの効果が期待できます。

mpz_mul関数は上記の関数群とは真逆で,現在の実装では,演算結果の格納先は別変数になっていた方が多少マシになります。 mpz_mul(x,x,y)のように使用すると,yがたとえ1リム長であっても,xの一時的な複写が行われてから演算が実行されます。 通常,この複写は乗算に比べれば僅かな時間で済みますので,あまり問題にはならないとは思いますが。

mpz_set, mpq_set, mpq_set_num, mpf_set等の関数は,代入先が元の変数かどうかの確認は行いませんので,mpz_set(x,x)などというのは無駄以外の何物でもありません。こんな書き方にはならないように,二つのポインタが同じ値を指示しているかどうか,下記のように確認しておきましょう。

if (x != y)
  mpz_set (x, y);

無駄なmpz_set呼び出しを導入しないよう,GMPにおけるデータの行先には注意を払って下さい。

(小さい整数による)除算可能性のテスト

mpz_divisible_ui_p関数とmpz_congruent_ui_p関数は,mpz_t型の数が,小さい整数で割り切れるかどうかを確認するための最良の関数で,mpz_tdiv_ui関数より高速なアルゴリズムを使っています。但し,剰余の情報を得ることはできないので,使えるのはきっちり割り切れるときだけです(もしくは,剰余が既知の時のみ)。

複数の小さい整数で割り切れるかどうかの確認を行う時には,それらの積の剰余を求めるのが最良で,これによって多倍長演算量を節約できるようになります。例えば,ある数が23, 29, 31で割り切れるかどうかを知りたい時には,23*29*31 = 20677の剰余を求め,これが割り切れるかどうかを確認します。

mpz_tdiv_q_ui関数のように,商と剰余を同時に求める除算関数は, mpz_tdiv_ui関数のように剰余のみ求める関数より少々低速になります。商が必要になることはあまりないので,剰余だけ求めておき,必要に応じて商を計算するようにした方がいいでしょう(剰余がゼロならmpz_divexact_ui関数が使えます)。

有理数演算

mpq関数は,既約分数であるmpq_t型の値を使って演算を行います。約分できるのであれば必ず実行する必要があり,こうすることで,なるべく桁数を減らして後続の演算を軽くできます。

とはいえ,アプリケーション側が約分できるかどうかの情報を持っている場合は,いちいちGCDを確認するのは避けたくなります。例えば,素数を乗じた場合,GCDを確認するよりは分母にその素数因子があるかどうかだけを見れば十分なわけです。また,積が長くなる場合も,殆ど約分できないことが分かっているのであれば,約分は最後までとっておきたくなります。

mpq_numrefmpq_denrefマクロは,分子と分母へのアクセスを提供するためのもので,mpq関数の枠外で個別に操作ができるようになります(See Applying Integer Functions)。

有理数の標準形はmpq_tと整数の加減算を混ぜて使うことができます。例えば次のようになります。

/* mpq++ */
mpz_add (mpq_numref(q), mpq_numref(q), mpq_denref(q));

/* mpq += unsigned long */
mpz_addmul_ui (mpq_numref(q), mpq_denref(q), 123UL);

/* mpq -= mpz */
mpz_submul (mpq_numref(q), mpq_denref(q), z);
数列

mpz_fac_ui, mpz_fib_uimpz_bin_uiuiといった関数は,数列中の特定の値を求めるためのものです。一定範囲の数列全て欲しい場合は,初期値だけこの関数を使って求め,残りは漸化式で求めるのが最良です。

テキストの入出力

16進,もしくは8進表現はテキストの入出力時に指定できます。このように2のべき乗が基数である時には,それ以外の基数の表現よりも効率的に変換ができます。長い桁の数に対しては,処理時間はどのみち長くなりますので,基数は大して影響しません。

スウェーデン王国のチャールズ12世とその後継者が提案しているように,そのうち8進数が日常生活で普通に利用されるようになってほしいモンですな。(Knuth本の Vol.2, 4.1節参照)