Garner のアルゴリズムと多倍長整数演算

要約

この記事では、Garner のアルゴリズムについての話、およびその Java 実装と、それが多倍長整数の計算量削減にどう使えるのかを解説するわ。

前提知識

中国剰余定理 中国の剰余定理 - Wikipedia について知っていることを前提にするわ。また、多倍長整数、および Javajava.math.BigInteger クラス についても基本的な知識 (add, subtract, multiply, divide など) を仮定するわ。

 

Garner のアルゴリズム

概要

中国剰余定理で存在が保証されている、整数を出力するアルゴリズム

k 個の相異なる素数 p_1,...p_k があるとする。このとき、

x = a_i (mod p_i)

という k 個の制約から、x mod p_1 p_2 ... p_k を求めることができる。

 

実装

任意modでの畳み込み演算をO(n log(n))で - math314のブログ を参考にして実装したわ。おそらく O(k^2) で動くはずよ。この実装は、 M=p_1 p_2 ... p_k としたとき、絶対値が最小になる様な x を返すわ。 (つまり、 -M/2<=x<M/2 が成り立つ。)

gist.github.com

 

Garner のアルゴリズム多倍長整数演算

中国剰余定理による並列化

k 個の素数 p_1, p_2, ..., p_k を取ったとき、0以上 p_1 p_2 ... p_k 未満の整数 x と、(x%p_1, x%p_2, ..., x%p_k) は1:1に対応するわ。だから、計算結果が0以上 p_1 p_2 ... p_k 未満のとき、各素数 p_i に対して、 mod p_i で計算した結果が分かれば、元の計算結果が復元できる。これを利用して、普通に多倍長整数の演算を行うより高速に演算するのが、ここで紹介する手法の目的だね。

Garner のアルゴリズム vs 多倍長整数演算

多倍長演算には、いくつかの基本演算があるわ。扱う整数のビット数を b として、

  1. 足し算と引き算
    筆算で O(b)
  2. 掛け算
    Java のバージョンによって違うけど、 O(b^2) だったり O(b^1.58) だったりするわ。OpenJDK 8 では大きさによってアルゴリズムを使い分けているようね。 BigInteger#multiply() のソースコードは GC: BigInteger - java.math.BigInteger (.java) - GrepCode Class Source を見ればいいわ。Karatsuba 法Toom-Cook 法 について理解していると、読みやすいかもね。
  3. 割り算
    これも多分 Java のバージョンによって違うけど、ソースを見たところ O(b^2) くらいだね。多倍長整数の割り算を効率的に計算する方法って、あるのかしら…?

この様に、多倍長整数の足し算や引き算なら簡単だけど、掛け算や割り算は難しいの。

法 p_i の選び方

法 p_i は、2^30 から 2^31 までの素数を選ぶのがもっとも簡単ね。また法の個数 k についてだけど、b ビットの整数を扱うとして、k>=b/30 なら、p_1 p_2 ... p_k>=(2^30)^k>=2^bだから、b/30 個の素数があれば十分ね。

b ビット程度の整数の掛け算や割り算を n 回実行するとして、愚直に実行すると計算量が O(nb^2) になるところを、 Garner 法を使うと、O(nk+k^2)=O(nb+b^2) になるね。これは元の計算より高速だね。

 

例題

ちょっと人工的な例だけど、以下の様な問題を考えてみて。

n<=20000と、1<=m_i<=2000, 0<=k_i<=m_iが与えられる。

このとき、コンビネーションの和 C(m_1,k_1)+...+C(m_n,k_n)の正確な値を、10進表記で出力してください。実行制限時間は数秒です。

 このような、最後に全体の計算結果が分かればいい問題を解くときには、 Garner のアルゴリズムが役に立つわ。

以下の議論では m=2000 とするね。

この場合、Garner のアルゴリズムをどう使えばいいかというと、まず、C(i,j)<=2^mで、それを n 個足すから、求める値は m+log n ビット程度の値になるの。だから b=m+log nとして、b/30 個の素数 p_1,p_2,... を法として計算するわ。各 i について、 1! から m! の値を mod p_i で持っておけば、C(i,j) mod p_i は定数時間で計算できるね。よって、計算量の合計は、前計算 O(mb) 、和の計算 O(nb) 、Garner 法 O(b^2)で、合計 O( (n+m)(m+log n)) でできる。この場合だと(n+m)(m+log n)はおよそ4*10^7だね。

愚直解法と比較してみるわね。

  1. C(m_i,k_i) を全部計算して、求めたn個の値を全部足す。
    求めるときに毎回 BigInteger で計算すると、コンビネーションは小さい数での乗算、除算を m 回くらいやればいいから、全部で O(nm^2) でできるね。
    nm^2=8*10^10 だから、この方法だと、数秒で答えを出すのは難しそうだね。
  2. m=1000 として、m 段までのパスカルの三角形を作って、 C(m_i,k_i) の値の表を作っておく。
    この方法だと、最終的に計算する数は m^2 個くらいになって、一つ一つがおよそ m 桁だから、計算量は O(m^3+nm) ね。m^3=8*10^9だから、この方法でも、数秒では計算が終わりそうにないね。
Non-example

Educational Codeforces Round 34 D Almost Difference

この問題は、答えが -10^19 から 10^19 までの範囲をとるから、 long long int にも unsigned long long int にも収まらない。だから多倍長整数を使う必要があるわ。

この問題でも上のテクニックで解こうと思えば解けるけど、桁数が少ないから、あまり意味はない。一応ライブラリの verify はできるわね。

Submission #33247715 - Codeforces (verify のために、わざと法を 10^6 くらいの素数にしている。法は4個。)

まとめ

残念ながら、競技プログラミング多倍長整数演算が必要になる問題は、あまり出ない。その様な問題は、 競技プログラミングにおける多倍長整数問題まとめ - はまやんはまやんはまやん に載っているから、参考にして。

どちらかといえば、競技プログラミングよりも、一般数体篩のような、巨大な整数を扱う分野で役立っているテクニックだね。でも知っておいて損はないと思う。

参考

  1. 任意modでの畳み込み演算をO(n log(n))で - math314のブログ

    math314 による、高速剰余変換を計算量 O(n log n) で計算する記事。この記事の本題は高速剰余変換だけど、C++での Garner 法の実装の参考にもなるわ。
  2. 立教大学の木田祐司による、 暗号アルゴリズムの詳細評価に関する報告書 (pdf) には、これを 一般数体篩 (GNFS) と呼ばれる素因数分解アルゴリズムの中で応用する方法について、述べられているわ。 (5.5.1 中国の剰余定理の変形)