読者です 読者をやめる 読者になる 読者になる

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

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

算術演算の計算量

気がつけば大晦日。明日はもう2014年です。このブログを始めて1年も過ぎました。記事が充実しないのは筆者の怠慢の致すところであります。

久々の更新で一体何を書くのかといえば、大分放置していた計算量の定義です。誕生日のパラドックス素因数分解に応用しよう!と言ったのはいつの話でしたかね?今回の話からやっと続きに入れます。まずは、最も基本的な算術演算である四則演算(加減乗除)の計算量を考えます。

結論を先に書いておきます。

2つの数 a, b がそれぞれ位取り記数法(基数は2以上で任意に固定)の m, n 桁で入力として与えられるとき、四則演算の結果を同じ記数法で出力するときの(最悪時)計算量は

  • 足し算 a+bO(\max\{m,n\})
  • 引き算 a-bO(\max\{m,n\})
  • 掛け算 a \times bO(mn)
  • 割り算 a \div bO((m-n+1)n)m \geq n

特に、上で m=n および割り算で m=2n とすると

  • 足し算 a+bO(n)
  • 引き算 a-bO(n)
  • 掛け算 a \times bO(n^2)
  • 割り算 a \div bO(n^2)

となります。これらのうち、掛け算と割り算はより小さいオーダーで計算することができることを先に断っておきます。

非常に大雑把な見方をすると、どれも入力の長さ m,n多項式に収まるという意味で、効率的に計算できると言えます。

それでは足し算から順に見ていくとしましょう。

足し算の計算量

問題を繰り返すと、2つの数 a, b がそれぞれ位取り記数法(基数は2以上で任意に固定)の m, n 桁で入力として与えられるとき、a+b を同じ記数法で出力するときの計算量はいくらか、ということを考えます。足し算は交換可能なので、桁数が大きい方を a とし、\max\{m,n\}=m としておきます。

10進法

日本に住んでいる人のほとんどは数を10進法で扱っていると思いますので、まずは10進法での足し算について考えます。これは小学校で習った通りです。違うことといえば、桁数がどんどん増えていくということです。

簡単な場合として、1桁、つまり n=1 のときは、ちゃんと計算の訓練をしてきた人であれば、手続きなど考えずに

1+1=22+3=54+7=117+8=159+9=18

と一瞬で出てくることでしょう。*1とりあえずはこれを計算の1ステップと定義します。上で言ったように、今回扱う時間計算量は、すべてこのようなステップの数で測ります。

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

m,n が大きい場合については、筆算で計算するとします。今回はそれ以上複雑なことは考えません。それでは、筆算の計算量を測りましょう。数えるのは計算を終えるまでに行った1桁の足し算の回数です。

記号として、m,n 桁の足し算の時間計算量を T_{+,10}(m,n) で表すことにします。(下の10は10進法の10です。)ステップ数はもちろん、足す数が何であるかに依存するので、T_{+,10}(m,n)m,n 桁の2つの数の組すべてに対する最大値を取ることとします。すなわち、T_{+,10}(m,n) より少ないステップ数では、必ずある入力に対して計算が正しい結果を返さない、という意味で T_{+,10}(m,n) はこの問題の入力全体の上での計算量を表しているのです。このような計算量は「最悪時(worst case)」*2計算量と呼ばれます。定義より T_{+,10}(1,1)=1 です。

繰り上げがない場合は、1桁ずつ足していくと桁数が少ない方の n 桁目で計算が終わるので、計算量は n となります。これについては考えることもないでしょう。

繰り上げがある場合について考えましょう。ここでは m=n=2 の場合を見ます。

f:id:azapen6:20140103163345p:plain

個々の1桁の足し算を書き下すと、

1桁目:7+5=12
a の2桁目+1桁目からの繰り上がり:7+1=8
2桁目:8+6=14


となります。以後すべてで桁は右(1の位)から数えるとします。

2桁目では繰り上がりを足し込む計算が入るため、2ステップかかっています。そんな簡単な計算にそこまで数える必要はないと思われるかもしれませんが、先ほど「1桁の足し算の計算量は1」と決めたので、ちゃんと守らなければなりません。よって、この場合の計算量は3です。2桁目も繰り上がっていますが、足す相手が3桁目にいないので、これは数えません。

実はこれは最悪の場合になっています。というのも、繰り上がりがすべての桁で起こったとして、それが足されるのは2桁目だけだからです。最大の桁に関してはそのまま繰り上げるだけなので数えられないのです。よって、1桁目、2桁目、1桁目からの繰り上がり、この3つ以外の1桁の足し算は生じません。

気をつける必要があるのは、同じ桁での繰り上がりの重複です。例えば、1桁目から2桁目への繰り上がりの足し込みで3桁目への繰り上がりがあったところに、2桁目の足し算が行われることによってもう一度繰り上がりが起こって、3桁目に新たに繰り上がりが生じる場合です。しかし、足し算においてはこのようなことはあり得ません。もし先の繰り上がりの足し込みで3桁目に繰り上がりがあったとすると、2桁目の数は 9+1=10 で0です。そのため、2桁目にどんな数を足しても新たな繰り上がりは生じません。よって、考慮すべき繰り上がりの重複は起こりません。これは上位の桁についても帰納法を用いて一般化されます。

以上から、T_{+,10}(2,2)=3 です。

ちなみに、同じ桁での繰り上がりの重複は掛け算であれば起こり得ます。例えば、

f:id:azapen6:20140103163834p:plain

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

のような場合です。この場合は1桁の繰り上がりに対して2回の足し算が行われることになります。それはまた後で。

一般の m,n 桁について考えると、計算量が最悪となる場合とは、1桁目から m 桁目までの全ての桁で繰り上がりが生じる場合でしょう。この場合の計算量は、各桁の足し算 n 回に加えて、2桁目から m 桁目までの繰り上がりの足し算 m-1 回を加えた m+n-1 となるはずです。先に言った通り繰り上がりの重複は起こらないので、これが最悪時計算量の上界となります。では、実際そのような場合があるのでしょうか?…あります。例えば、999\dots 9 + 999 \dots 9 では、すべての桁で繰り上がりが起こります。よって、

T_{+,10}(m,n)=m+n-1

となります。特に、m=n のときは

T_{+,10}(n,n)=2n-1

となります。

2進法

今度は2進法での足し算の計算量を出してみましょう。2進法はコンピュータ内部で用いられている数の表し方なので、コンピュータに関連した計算量を出すには都合がよさそうです。

1桁の足し算は10進法のときよりもパターンが少なくて、

0+0=10+1=11+0=11+1=10

の4つだけです。その意味ではこちらの方が簡単とも言えますが、それと引き換えに同じ数を表すのに多くの数字が必要となります。

計算量の単位となる1ステップの数え方は先ほどと同じとします。

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

記号として、2進法での m,n 桁の足し算の時間計算量を T_{+,2}(m,n) で表すことにします。(下の2は2進法の2です。)T_{+,2}(m,n) はやはりすべての m,n 桁の数での最悪時を取ります。定義より T_{+,2}(1,1)=1 です。

早速2桁の場合を考えましょう。繰り上がりがない場合はそのまま T_{+,2}(m,n)=n となるのは明らかですが、繰り上がりがある場合はどうでしょうか?

f:id:azapen6:20140103163415p:plain

個々の1桁の足し算を書き下すと、

1桁目:1+1=10
a の2桁目+1桁目からの繰り上がり:0+1=10
2桁目:1+1=10

となります。

2桁目では繰り上がりを足し込む計算が入るため、2ステップかかっています。おや?先と何も変わるところがありませんね。ということで、この場合の計算量は3です。

実はこれは最悪の場合になっています。というのも、10進法で述べた通りです。同じ桁での繰り上がりの重複が起こらないことも10進法の場合と全く同様にして示されます。

よって、T_{+,2}(2,2)=3 です。

同様にして、一般の m,n 桁に対して最悪の場合とは、1桁目から m 桁目までの全ての桁で繰り上がりが生じる場合でしょう。この場合の計算量は、各桁の足し算 n 回に加えて、2桁目から n 桁目までの繰り上がりの足し算 m-1 回を加えた m+n-1 となるはずです。そのような場合として、111\dots 1 + 111 \dots 1 ではすべての桁で繰り上がりが起こります。よって、

T_{+,2}(m,n)=m+n-1

となります。ここでも10進法のときと全く同じ値が出ましたね。

\ell 進法の場合

ここまで来れば一般の \ell \geq 2 進法の場合も全く同様に話が進むように思われます。足し算の筆算で繰り上がりの重複が起こらないのは基数を任意の \ell に選んでも変わりません。

先と全く同様に、m,n 桁の足し算に対して計算量が最大となる場合とは、1桁目から m 桁目までの全ての桁で繰り上がりが生じる場合です。この場合の計算量は、各桁の足し算 n 回に加えて、2桁目から m 桁目までの繰り上がりの足し算 m-1 回を加えた m+n-1 となるはずです。そのような場合として、(\ell-1)(\ell-1)(\ell-1)\dots (\ell-1) の形のもの同士を足せば、すべての桁で繰り上がりが起こります。

従って、すべての \ell \geq 2 に関して、

T_{+,\ell}(m,n)=m+n-1

が成り立ちます。

ちなみに、\ell=1 の場合(1進法)では全く違うことになります。1進法というのは、数字として使えるのは1だけで、n という数を n 桁の1 (=1^n)で表すというものです。この場合、足し算は単に文字列を連結するだけなので、上とは全く違うことになります。今回は1進法については考えません。*3

引き算の計算量

引き算についても上の議論とほぼ同様にして、1桁の引き算を1ステップとして同じ計算量を得ることができます。1桁の引き算には、2-7=-5 のように結果が負となる場合も含みます。

また、どんな桁数の数についても、それが正か負かの判定および符号の反転を行うのにかかる時間は考慮しないとします。実装上は数の表現に符号用の1ビットを加え、それを見ることで正か負かを判定します。仮にこの判定に1ステップかかるとすると、計算量は定数倍程度には増えます。その時間を考慮しないというのは、繰り下がりが生じるかどうかの判定に要する時間を考慮しないことと同じです。これは、足し算で繰り上がりが生じるかどうかの判定を計算量に入れなかったことに対応します。

定義:1桁の引き算の時間計算量を1とする。

記号として、\ell 進法 m,n 桁の足し算の時間計算量を T_{-,\ell}(m,n) で表すことにします。

引き算に関して注意すべきは繰り下がりの処理だけです。ある桁で 2-7=-5 のように符号が反転する場合は、繰り下がりとみなしてその桁の計算を 12 - 7 = 5 (実際上は負号を外すだけ)とし、上の桁を繰り下げる(1を引く)というようにします。

一例として10進法2桁の引き算をやってみましょう。

f:id:azapen6:20140817034746p:plain

1桁目:2-5 = -7
a の2桁目−1桁目への繰り下がり:4-1 = 3
2桁目:3-1 = 2

これはやはり最悪の場合になっています。よって、計算量は T_{-,10}(2,2) = 3 となります。

足し算の場合と同様に、同じ桁での繰り下がりの重複は起こりません。例えば、2桁目から1桁目への繰り下がりを引いたとき、3桁目からの繰り下がりが起こったとします。このとき、2桁目は 0-1=-9 から9となります。これに続けて2桁目の引き算を行っても3桁目からの繰り下がりは起こりません。これは上位の桁についても帰納法を用いて一般化されます。

一般の m,n 桁について考えると、計算量が最悪となる場合とは、2桁目から m 桁目までの全ての桁で繰り下がりが生じる場合でしょう。この場合の計算量は、各桁の足し算 n 回に加えて、2桁目から m 桁目までの繰り下がりの足し算 m-1 回を加えた m+n-1 となるはずです。先に言った通り繰り下がりの重複は起こらないので、これが最悪時計算量の上界となります。では、実際そのような場合があるのでしょうか?…あります。例えば、222\dots 2 - 999 \dots 9 では、すべての桁で繰り下がりが起こります。よって、

T_{-,10}(m,n)=m+n-1

となります。特に、m=n のときは

T_{-,10}(n,n)=2n-1

となります。

もし最上位の桁の計算で繰り下がりが起こったならば、それは結果が負の数であることを意味します。

以上の議論は10進法で行ってきましたが、これもまた任意の \ell \geq 2 について \ell 進法でも並行して議論することができ、同じく

T_{-,\ell}(m,n)=m+n-1

を得ることができます。

大小比較の計算量

関連して、引き算と正負判定を組み合わせることで、2つの数の大小比較を行うことができます。すなわち、ab の間に入る不等号は、a-b と0の間に入るそれと同じです。例えば、a-b < 0 ならば a < b です。よって、\ell 進法 m,n 桁の大小比較の計算量を T_{<,\ell}(m,n) で表すことにすると、

T_{<,\ell}(m,n) = T_{-,\ell}(m,n) = m+n-1

となります。

まとめと問題点

今回は、算術計算の計算量について、1桁の計算に還元してその回数で測ることにより、足し算、引き算、および大小比較の計算量を求めました。任意の基数 \ell \geq 2 について、\ell 進法 m,n 桁の計算量はすべて同じ

T_{+,\ell}(m,n) = T_{-,\ell}(m,n) = T_{<,\ell}(m,n) = m+n-1

となることが判りました。

数字の見方で計算量が違う??

以上で表現ごとの計算量がすべて同じであることを見てきましたが、ここで一つの問題が生じます。

a, b を1組決めて計算することを考えると、数字の見方によって計算量の値が変わってしまうのです。式の形として T_{+,\ell}(m,n)=m+n-1 は同じなのに、どうして計算量が変わるのかというと、数字の見方を変えると桁数も変わってしまうためです。例えば、a, b を2進法で 4n 桁の数とすると、それらは16進法では n 桁となります。(2進法の数を \ell=2^k 進法に読み替えるのは、k ビットをもって1つの数字と見做すことと同じです。例えば、2進法で10110101を16進法に読み替えるのは、1011と0101をそれぞれ1つの数字と見なすことと同じです。一般的な表記としては、1011→b、0101→5と置き換えてb5とするだけです。)よって、元が同じ数なのに足し算の計算量は T_{+,2}(4n,4n)=8n-1T_{+,16}(n,n)=2n-1 という違いが出てしまうのです。

もし計算機が入力ビット列(2進法)を16進法のつもりで読んで計算しているとしたら、その実装のために計算量は T_{+,2}(4n,4n)=8n-1 のほぼ4分の1になります。もっと大きい k に対して \ell=2^k 進法に読み替えるとしたら、計算量はさらに小さく 1/k になります。

数字の見方を変えるだけで計算量が変わるなどというと屁理屈を言っているようにも思われますが、実はコンピュータの中でもそれと同じことが行われています。通常のコンピュータにおける1ステップのデータ処理の単位は、ビットではなくて複数のビットを一塊にした「ワード」というものだからです。プロセッサの能力を表すのによく使われる32ビットや64ビットという数字は、この1ワードの長さのことなのです。位取り記数法で考えるなら、k ビット=2^k 進法です。1ワードの足し算は基本的に1ステップで行われるので、計算量は上と同様に測ることができます。すなわち、CPUを32ビットから64ビットに更新したとすると、同じ足し算の計算量は半分になってしまうのです。

1ステップで処理できる位取りの数が何であるかというのは実装の問題であり、これが理論的な意味での計算量に影響することは避けたいものです。

*1:世の中には3桁でも一瞬で出てくるなんて人もいますが、それは10進3桁を1000進1桁と見なすことに相当し、後述する計算量の定数倍の違いを生じます。

*2:最「悪」という主観が入った言い方をするのは、計算量は小さくある方が好ましいという工学的な動機によります。最悪時計算量が小さいということは、最も困難な入力に対しても、計算を早く終えることができることを意味します。

*3:1進法は数の表現として非常に効率の悪いもので、こんなものを考える意味はないようにも思えますが、理論においては度々現れます。