あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

掛け算の計算量

前回の足し算の計算量に続いて、今回は掛け算の計算量について見ることにします。

掛け算(および割り算)において一つ重要なことは、筆算よりもオーダーの意味で(定数倍を超えて)速い計算方法が存在することです。一方で、足し算(および引き算)の場合は、前回出した n 桁の数に対する計算量 O(n) は、これより小さいステップ数では必ずある入力に対して計算を間違える、という意味で最良になっています。実際、n 桁同士の足し算 111 \dots 1 + 111 \dots 1 = 222 \dots 2 を完了するためには、どうしても1桁の足し算を n 回行う必要がありますよね。ところが、掛け算では最初に筆算で与える計算量 O(n^2) よりも漸近的に速い、例えば O(n^{1.585})(Karatsuba法)を達成するような計算方法があるのです。

ただし、オーダーの評価はあくまで漸近的なものなので、オーダーが良いからと言って現実的な問題サイズで高速化が達成できるとは限らないことには注意が必要です。入力サイズが小さいときは、漸近的に遅いながらも単純な方法が勝ることはよくあります。今回紹介するKaratsuba法では、そこそこの桁数でも高速化が達成できるのですが、他のより高速とされる方法では、かなり多くの桁数を必要とするか、あるいは現実的な桁数で全く役に立たない場合もあります。実用の観点から計算量を見るときは、こういった事情に注意が必要です。

このように、ナイーブな方法よりも真に速く計算できることがあるというのは、計算量理論が抱えるジレンマというべきものです。一方では困難な問題でも計算を速くできるかもしれないという希望を持たせてくれるでしょう。しかし、他方では計算量の下界、すなわち、最低でもどれだけの計算量が必要であるかを数学的に証明することの難しさを含んでいます。かの有名なP≠NP予想がなかなか解決しないのも、根本的には、難しいと考えられている問題が少ない計算量で解ける可能性を排除できないためです。何分、「計算」というものには数学的に上手い扱いのできる構造がないに等しく、計算量の自明でない下界を出すことは至難の業と言うほかありません。そのため、現状の計算量理論の世界とは、非常に弱い結果の先はほとんど未開の地と言っても過言ではないのです。

このような前置きで計算量理論の難しさをアピールしつつ、本題に入ります。

掛け算の計算量

今回扱うのは m 桁と n 桁の2つの数の掛け算の計算量です。前回と同じく、数えるのは1桁の演算の回数とします。1桁の足し算を1ステップと見なすのは前回と同じです。それに加えて、今回は新たに1桁の掛け算を1ステップと見なすことにします。10進法で言うなら、九九が1ステップで出てくるいったところです。*1細かいことを言えば、コンピュータで1ワード*2の計算をするとき、掛け算は足し算の数倍の時間がかかってしまうのですが、それは高々定数倍なのでオーダーの意味で無視できます。というわけで、これ以後の計算量の単位として、1桁同士の計算量を1と定義します。

定義:1桁の足し算および掛け算の時間計算量を1(ステップ)とする。

問題は、\ell 進法で m,n 桁の2つの数(とりあえずは非負整数) a, b が与えられたとき、積 a \times b の計算結果を出力するには何ステップかかるか、ということです。ここでのステップ数は一つ決めた計算手順に関する最悪時、すなわち、すべての入力対に対して計算を行うときのステップ数の最大値を取ります。

筆算の計算量

小学校で習ったように、複数桁の掛け算は、筆算によって九九と足し算に帰着することができます。まずはこれを考察の対象にするのが適当でしょう。基数は何を取ってもやり方に違いはないので、とりあえず10進法で考えることにします。

例として2桁同士の掛け算の筆算を考えると、23 \times 45 = 1035

f:id:azapen6:20140403183800p:plain

となります。演算とステップ数を順番に書き下すと、

1段目:34 \times 9 = 306
4 \times 9 = 36:1
3 \times 9 = 27:1
7 + 3 = 10(2桁目+1桁目から繰り上がり):1
2 + 1 = 3(2桁目からの繰り上がり+↑で生じた繰り上がり):1

2段目:34 \times 8 = 272
4 \times 8 = 32:1
3 \times 8 = 24:1
4 + 3 = 9(2桁目+1桁目から繰り上がり):1

3段目:306 + 2720 = 3026:3
(920の0はシフトで表しているので計算に含めていない)

ステップ数合計:10

となっています。

掛け算については、単純に2つの数の桁数を掛けた回数だけ行っていることが解ります。この場合は2桁×2桁で4回ですね。これを一般化すれば、m,n 桁の掛け算については、1桁同士の掛け算は mn 回=ステップ行われるとなります。

足し算については、繰り上がりが二重で起こることがあるために少しややこしくなります。ただし、m 桁×1桁の掛け算では、各桁について高々2回、合計で高々 2m 回=ステップであることが言えます。前に出した例を見てみましょう。

f:id:azapen6:20140103163834p:plain

2桁目+1桁目からの繰り上がり:3+8=11
2桁目からの繰り上がり+↑で生じた繰り上がり:6+1=7

ここで、各桁について繰り上がりは高々2回しか起こらないことに注意します。というのも、繰り上がりの重複は、最初がその桁の掛け算によって、次(\で消しているところ)が前の桁の足し算によって生じるものに限られるからです。どちらか一方のみなら1回、両方なら2回であり、1桁でそれより多くの繰り上がりが起こることはありません。また、各桁における足し算は、前の桁からの繰り上がりの足し込みと、次の桁への繰り上がりが重複した場合の足し込みの高々2回となります。これより、m 桁×1桁の掛け算における足し算は、高々 2m 回で抑えられることが解ります。*3

m 桁×n 桁では上の計算を n 回行うので、最後の段以前の足し算は高々 2mn 回=ステップで抑えられます。

最後に行う足し算は、各段の結果を桁をずらしながら上から順に足し込んでいくと考えて、高々 (n-1) \times T_{+,10}(m+1) ステップで済むことが言えます。ここで、T_{+,10}(n) =2n-1n 桁同士の足し算のステップ数です。まず、m 桁×1桁の結果は高々 m+1 桁なので、各段は高々 m+1 桁であることに注意します。よって、1段目と2段目を加えるのは T_{+,10}(m+1) ステップでできます。1つの足し算を行うと、下位の桁が1つ確定するので、次の計算は前の結果から確定した桁を除いたところだけでやればよいことが解ります。k 段目まで足し算を行って次の k+1 段目を足すときは、結果が高々 m+1+k 桁で下位 k 桁が確定しているので、結局確定していない高々 m+1 桁と、k+1 段目の高々 m+1 桁を足せばよく、T_{+, 10}(m+1) ステップでできるということになります。従って、この足し算全体については T_{+, 10}(m+1) ステップ× n-1 回で高々 (n-1) \times T_{+,10}(m+1) ステップとなります。後は少し計算すると (n-1) \times T_{+,10}(m+1) = (n-1)(2m-1) \leq 2mn が出ます。

以上の各段階のステップ数(の上界)をすべて加えると、

  • 掛け算:mn
  • 最後の段以前の足し算:2mn
  • 最後の段の足し算:2mn

合計:5mn

で、筆算による m 桁と n 桁の掛け算の計算量は高々 5mn と出ます。以上の議論は10進法で行いましたが、基数の値を全く用いていないので、任意の位取り記数法で同じことが言えます。

よって、最良の計算方法を取った場合の計算量は 5mn 以下であることが解ります。これをオーダーで表すと、

m 桁と n 桁の掛け算の計算量は O(mn) である

となります。特に、m=n のときは O(n^2) となります。まずはこれが最初の結論です。

一方で、筆算では1桁の掛け算を必ず mn 回行うので、上下界がオーダーの意味で一致します。これもオーダー記法で表すと、

“筆算による“ m 桁と n 桁の掛け算の計算量は \Theta(mn) である。

さて、とりあえずの計算量の上界は出たのですが、実はこれよりもオーダーの意味で計算量が真に小さい計算方法が存在するというのが掛け算の驚きどころです。以下、m=n とします。まず、筆算に限らないあらゆる方法を考えた場合、入力の長さ n が自明な下界となることは言えます。しかし、見ての通り筆算の下界 n^2 とは開きがあります。次に示す方法は、これを上から詰められることを意味します。

Karatsuba法

最初に述べた通り、桁数の多い掛け算には、筆算より計算量の小さい方法(アルゴリズム)が知られています。以下では、最初に発明された高速乗算アルゴリズムであるKaratsuba法(1960)を例に取って説明します。計算量の小さいアルゴリズムを与えることは、計算量の上界の改善を意味します。最初に言った通り、Karatsuba法の計算量は O(n^{1.585}) であり、筆算の O(n^2) より指数が小さいので、定数倍を超えた改善になっています。この上界は後々にさらに改善され、現時点では指数の改善をも超えて O(n \log n) にほとんど近いものが得られています。

それではKaratsuba法(1960)について説明しましょう。この方法は分割統治法という枠組みに含まれるもので、つまりは「元の問題を入力サイズの小さい子問題に分けて解く」ということを再帰的に繰り返すものです。よって、これは再帰アルゴリズムでもあります。

再帰的な筆算から

Karatsuba法では、まず入力を半分に分割して、それら同士の計算によって元の掛け算の答えを出します。つまり、n 桁の2つの数に対して、それらを分割した n/2 桁の4つの数を掛けたり足したりして元の計算の答えを出すのです。これ自体は上でやったような筆算を複数桁まとめて(あるいは基数を大きくして)やることと同じです。例えば、4桁同士の場合は2桁のブロックに分割して

f:id:azapen6:20140403191215p:plain

と計算できますよね。ここでブロック同士の掛け算を再帰的に行えば、最終的には1桁の掛け算に帰着されるというわけです。n が2べきでない場合は不均等な分割が出ますが、適当に処理してやれば問題なくできます。よって、細かいことは考えずに元問題、子問題含めて入力長はいつでも2で割れるとしておきます。

上の計算を一般的に書きましょう。n 桁の入力 a を下位(右)半分 a_0 と上位(左)半分 a_1 に分割します。同様に bb_0, b_1 に分割します。基数 \ell において n/2 桁のシフトは B = \ell^{n/2} を掛けることなので、a,b はそれぞれ

a = a_0 + a_1 Bb = b_0 + b_1 B

と書けます。従って、計算結果 R = a \times ba_0, a_1, b_0, b_1 を用いて書くと、

R = R_0 + R_1 B + R_2 B^2
R_0 = a_0 \times b_0
R_1 = a_0 \times b_1 + a_1 \times b_0
R_2 = a_1 \times b_1

となります。

掛け算の数を減らす

計算量を下げる鍵となるのは、掛け算の回数を減らすことです。上では普通の筆算と同じく、2桁のブロックの掛け算4回で計算していますが、Karatsuba法ではこれを3回の掛け算で行うのです。掛け算の方に時間がかかるので掛け算の回数を減らそうというわけですね。さらに a_0 \times b_0 などの掛け算も、同じ方法で再帰的に行うというのが計算量を減らすための基本的なアイデアです。

Karatsuba法では、上の R_1 の計算を1回の掛け算で行います。それは R_1 の計算を次の式に従って行うことで達成されます。

R_1 = R_0 + R_2 + (a_1 - a_0) \times (b_0 - b_1)

展開して計算してみると上の R_1 と一致することが確認できます。よって、R_0,R_1,R_2 をすべて計算するには n/2 桁の掛け算3回と、高々 n+1 桁の足し算および引き算4回で十分です。

それから結果の R を得るのは、桁をずらしながら高々 n+1 桁の足し算3回でできます。B を掛ける操作は足し込み先の桁をずらすことなので、ここでは掛け算は行いません。

全部合わせると、高々 n/2 桁の掛け算を4回、高々 n+1 桁の足し算および引き算を6回行うことで全体の計算ができます。さらに、子問題である n/2 桁の掛け算3回についても再帰的に同じ方法を用いて行います。最終的に桁数が1になったところで1桁の掛け算を行います。*4

計算量

それでは計算量を評価しましょう。Karatsuba法における n 桁同士の掛け算の計算量を T(n) とし、足し算および引き算の計算量は前回の O(n) を用いることとします。すると、T(n) の漸化式は

T(n) = 3T(n/2) + O(n)
T(1) = 1

となります。1桁の場合は定義に従って計算量を1としました。

一つ断っておくべきは、この漸化式自体は上界評価であり、T(n) の値を決めているわけではないということです。このような書き方は再帰アルゴリズムの計算量評価でよく見られます。一般項の上界は適当な方法で評価することができます。(→補遺)

ともかく、ある方法で T(n) を評価すると、

T(n) = \Theta(n^{\log_2 3})
\log_2 3 = 1.5849625\dots

となるので、上に丸めてやれば T(n) = O(n^{1.585}) が出ます。

筆算では n 桁の入力に対して n^2 以上の計算量を要すると解っているので、Karatsuba法は筆算より真に計算量の小さいアルゴリズムになっています。

再帰的に筆算を行った場合

一応、導入のところで書いた再帰的な筆算のやり方では、普通の筆算と同じ計算量になることを確認しましょう。上の計算は R の式をそのまま計算するのと同じなので、R_0, R_1, R_2 の計算は、n/2 桁の掛け算を4回、高々 n 桁の足し算を1回行えばできます。そこから R を出す計算は同じです。全部合わせると、高々 n/2 桁の掛け算を4回、高々 n+1 桁の足し算を4回行うことで全体の計算ができます。この場合の計算量を T(n) と置くと、漸化式は

T(n) = 4 T(n/2) + O(n)
T(1) = 1

となります。これを評価すると、

T(n) = \Theta(n^2)

となって、再帰的に計算しても改善がないことが解ります。実際、計算の進め方をよく観察すると、結局はすべての桁で掛け算を行っているのです。

というわけで、Karatsuba法の方が計算量が小さいことが再び確認されました。

ここまでの結論を述べると、

n 桁同士の掛け算の計算量は O(n^{1.585}) である。

代表的な高速乗算アルゴリズム

以下、立ち入った説明はしませんが、より計算量の小さい高速乗算アルゴリズムを挙げておきます。

Toom-Cook法

Karatsuba法を拡張してより分割数を増やしたものにToom-Cook法(Toom 1963、Cook 1966)があります。特に入力を両方とも d 分割するものは Toom-d と呼ばれます。今回説明したKaratsuba法はToom-2に相当します。分割数を増やすことは、掛け算の回数の減少率(Karatsubaでは4→3、Toom-3では9→5)を大きくできるというメリットがありますが、一方で再帰の各ステップの計算(上の漸化式で O(n) で抑えたところ)が多くなってしまうというデメリットもあります。すなわち、実用的な意味では、一概に分割数を多くすれば速くなるというわけではないことに注意が必要です。

Toom-d の計算量は dn によらない定数として O(n^{\log_d (2d - 1)}) です。すなわち、任意の \epsilon>0 に対してある d が存在して、Toom-dn 桁同士の掛け算を O(n^{1+\epsilon}) の計算量で行うことができます。

Toom-Cook法についての解説記事を作りました。主題は掛け算の回数が減るカラクリです。
http://azapen6.hatenablog.com/entry/2014/04/11/235315

Schönhage–Strassenのアルゴリズム

以上は指数の改善でしたが、それを超える改善を果たしたのがSchönhage–Strassenのアルゴリズム(Strassen 1968、Schönhage–Strassen 1971)です。この方法の鍵となるのは、高速フーリエ変換による畳み込みの高速計算法です。高速フーリエ変換は信号処理や画像処理などで用いられる離散フーリエ変換を高速に行うアルゴリズムですが、これを利用することで掛け算を高速化できるのです。*5

Schönhage–Strassenのアルゴリズムによる n 桁の掛け算の計算量は O(n \log n \cdot \log \log n) であることが知られています。すなわち、n の指数を下げるという範囲を超えた高速なアルゴリズムとなっています。ただし、n が非常に大きい(数万桁以上)場合でないと高速フーリエ変換のオーバーヘッドが勝ってしまうので、そこそこの桁数(〜数千桁程度)の掛け算ではむしろKaratsuba法などの方が実用上高速です。主にこのアルゴリズムが威力を発揮するのは、超巨大素数の生成・判定や円周率の超高精度計算などの純粋に数学的な用途です。

ところで、計算量の O(n \log n \cdot \log \log n) の後ろについている \log \log n が無くなれば O(n \log n) となって綺麗だと思いませんか?実はこの部分は、概念的なアルゴリズムを正確に実装するために要した「おまけ」みたいなものです。一般的な高速フーリエ変換O(n \log n) 回の算術演算(桁数などは考えない)を行うことから、大雑把には掛け算も同じ回数の算術演算でできるはずだったのです。ところが、高速乗算アルゴリズムは桁数まで考えた算術演算の中身をどうにかしようという話なので、邪魔な \log \log n がくっついてきたというわけです。この部分を改良したのが次に挙げるFürerのアルゴリズムです。

Schönhage–Strassenは高速フーリエ変換を用いるという以外は単純なアルゴリズムであり、実用にも供されることから、いくつもの本やWebサイトで解説が為されています。(丸投げ)

Fürerのアルゴリズム

現時点で計算量の意味で最速のアルゴリズムとして、Fürerのアルゴリズム(2007)が知られています。これは、上のSchönhage–Strassenのアルゴリズムと同じ流れで、技術的な詳細に立ち入ってチューニングを行ったものです。ただし、そのためにかなり複雑なアルゴリズムになっていて、その分オーバーヘッドが大きいため、実用上の用途は(少なくとも現時点で)ありません。Fürerのアルゴリズムが既存の方法に勝るには、入力として天文学的な桁数が必要と考えられています。故にこのアルゴリズムの意義は、理論的な計算量の上界の改善を果たしたことのみです。

Fürerのアルゴリズムの計算量は O(n \log n \cdot 2^{\log^* n}) です。ここで、\log^* n は(底2の)重複対数と呼ばれる関数で、ほとんど定数と思って差し支えないほど増加の遅いものです。定義は

f:id:azapen6:20140412031609p:plain

を満たす2の数の最小値(ただし \log^* 1 = 0)です。この関数の値は、全宇宙の粒子数が 10^{80} と考えられている中で、n=2^{65536} \approx 2*10^{19728} に対して \log^* n = 6 なので、6を超えることは宇宙レベルであり得ないということになります。そして、2^{\log^* n} もまた \log \log n よりはずっと増加の遅い関数となります。よって、FürerのアルゴリズムはSchönhage–Strassenの計算量の上界を改善しています。

もう一度言いますが、Fürerのアルゴリズムはあくまで「理論上」最速の高速乗算アルゴリズムです。実装とか考えたら負けです。

掛け算の計算量の上界

まとめると、最良のアルゴリズムにおける掛け算の計算量の漸近的上界については、2014年1月の時点で次のことが知られています。

n 桁同士の掛け算の計算量は O(n \log n \cdot 2^{\log^* n}) である。

今回はここまで

今回は掛け算の計算量についてお話しました。普通の筆算では O(n^2) だったものが、より高速なアルゴリズムO(n^{1.585})(Karatsuba)、O(n^{1+\epsilon})(Toom-Cook)、O(n \log n \cdot \log \log n)(Schönhage–Strassen)ときて、O(n \log n \cdot 2^{\log^* n})(Fürer)まで上界を下げられることが現在までに解っています。このように筆算よりも真に高速な計算方法が知られていることは、掛け算(および割り算)に関して特筆すべきことです。一方で、下界は \Omega(n \log n) と予想されていますが、現時点では \Omega(n) という自明なものしか知られていません。

次回は割り算をやるつもりでしたが、少々積もる話があるので、前後をどうするか未定です。

*1:インドでは2桁の掛け算まで1ステップでできるそうです。これは100進法の九十九九十九(つくもつくも?)が1ステップでできると言い換えられるので、問題はありません。

*2:実装上の1桁。kビットプロセッサというときは原則として1ワード=kビット。

*3:厳密に言えば、1の位は前からの繰り上がりがないので足し算は1回少ないですが、重要な差ではないので無視します。

*4:実装上は桁数が十分小さくなったところで普通の筆算に切り替えて構いません。

*5:他にも文字列のパターン照合など様々な応用があります。ただし、高速フーリエ変換のオーバーヘッドが大きいため、現実的な問題サイズで役に立つものは数えるほどありません。