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

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

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

割り算の計算量

足し算、引き算、掛け算と来たら、残る四則演算は割り算です。

割り算においてこれまでと違うことは、何と言っても「割り切れない」場合が存在することでしょう。他の四則演算はすべて整数の範囲で閉じている*1のですが、整数同士の割り算では結果が整数とならない場合が存在します。

そこで、今回は割り算を小学校で習ったように、割り切れないときは余りを出す、という形で行うこととします。つまり、除算と剰余算を同時に行うというわけです。入力として2つの非負整数 a, b を受け取り、計算の結果としては a \div b の商 q と余り r の組 (q, r) を出します。これらが満たす関係は

a = q \times b + r \quad (0 \leq r < b)

です。a \div b が割り切れるということは、r=0 となることに他なりません。

結果として小数を出す割り算もこれに当てはめて行うことができます。例えば、分数 11/23 の小数第4位までの値を第5位を四捨五入して得る計算は、次のように実現できます。まず分子に欲しい位と同じ4個の0を足して 110000 \div 23 = 4782 \dots 14 を計算します。次に、14 \times 2 \geq 23 であることから余りを切り上げて4783とします。最後に小数点をつけた0.4783が欲しい結果です。

ここで除算だけでなく剰余算まで一緒に扱うのは、剰余算が数論アルゴリズムの最も基本的な要素の一つだからです。例えば、ユークリッドの互除法(最大公約数の計算)は余りを用いて計算を行うアルゴリズムの代表的なものです。また、同じく数論アルゴリズムで重要な剰余環(体)上の計算においても、使われるのは余りの値だけです。実際的にも剰余算は除算(と他の四則演算)に帰着できるので、ここで一緒に扱うのが得策でしょう。

割り算の計算量

それでは割り算の計算量を見て行きましょう。まずは問題設定を書いておきます。

問題:m \geq n とするとき、\ell 進法 m 桁で表された非負整数 a と同 n 桁の非負整数 b に対して、a \div b の整商と剰余を計算するときの計算量は何ステップか?

m < n の場合は自明に商が 0、余りが a なので除外しました。

計算の基本ステップを定める上でこれまでと大きく違う点は、割り算が桁数の小さい割り算の組み合わせでないことです。これは、割り算の筆算を実際にやってみれば分かるでしょう。例えば、4567 \div 123 を計算するとき、最初に手をつけるのは、割る数と同程度の桁数の割り算 456 \div 123 です。そして、これを計算するためには、123 \times q_1 \leq 456 を満たす最大の q_1 (1桁の数)を探します。ここで 123 \times q_1 は掛け算です。また、123 \times q_1 \leq 456 の大小比較は前に見たように引き算 456 - 123 \times q_1 と同じです。いずれの計算でも桁数の小さい割り算は出てきません。

f:id:azapen6:20140913195636p:plain

計算の過程(線形探索)
456 > 123 \times 1
456 > 123 \times 2
456 > 123 \times 3
456 < 123 \times 4q_1 = 3

よって、割り算の計算量を考えるときは、これまでの話に新たに加えることもなく、1桁の足し算、引き算、掛け算を基本ステップとすれば十分です。改めて書くと、

定義:1桁同士の足し算、引き算、掛け算をそれぞれ1ステップとする。

筆算の計算量

それでは、割り算の筆算について、計算量を見ていきましょう。以下、数字は \ell \geq 2 進法で書かれているとします。

まず、a の頭から b と同じ n 桁だけの数字を取り出し、これを p_1 とします。そして p_1 \div b を計算し、商と余りの組 (q_1, r_1)q_1 は1桁の数) を得ます。これは、先に見たように、p_1 \geq q_1 \times b となる q_1 のうち最大のものを選ぶことで行えます。続けて r_1 の後に a の次の桁を追加したものを p_2 とします。そして前と同様に p_2 \div b を計算し、 商と余りの組 (q_2, r_2) を得ます。

以上の計算を a の桁をすべて取り尽くすまで繰り返します。p_1 を取った時点では、a には m - n 桁の残りがあるので、k = m - n + 1 として p_k まで進めるとすべての桁を取り尽くすことになります。最後に p_k \div b を計算し、 商と余りの組 (q_2, r_2) を得ます。以上の計算によって、数字の列 q_1, q_2, \dots, q_k と余り r_k が得られます。

計算結果は、整商が q_1, q_2, \dots ,q_k をすべて繋げたもの、剰余が r_k です。

例の 4567 \div 123 について最後まで見ると、

f:id:azapen6:20140913200617p:plain

k = 4 - 3 + 1 = 2

1段目:
p_1 = 456
q_1 = 3, r_1 = 87

2段目:
p_2 = 877
q_2 = 7, r_2 = 16

結果:
整商: q_1 q_2 = 37
剰余: r_2 = 16

となります。

以上の計算の過程をアルゴリズムとして書き下すと、次のようになります。

入力:m 桁の整数 an 桁の整数 bm \geq n
出力:(q,r) = a \div b の整商と剰余の組

  1. p_1 \leftarrow a の先頭(大きい位)から n
  2. i = 1,2, \dots, k = m - n + 1 について3-5を繰り返す
  3. q_ip_i \geq q' \times b を満たす最大の q' とする
  4. r_i \leftarrow p_i - q_i \times b
  5. p_{i+1} \leftarrow r_i の末尾に a の次の桁を追加した数(i=k ではスキップ)
  6. q = q_1 q_2 \dots q_kr = r_k として (q,r) を出力

これの計算量について見ていきます。計算のステップとして考慮しているのは足し算、引き算、掛け算だけなので、他の操作(p_i を作る操作など)は計算量には数えないものとします。よって、考慮すべきは3-5の反復の部分だけです。このうち5は考慮しないので、3、4の1反復の計算量が分かれば全体の計算量を出すことができます。

4については q_i \times b が1桁× n 桁なので O(n)、それを p_i から引くのが n 桁×高々 n 桁なので O(n)、合わせて O(n) となります。

3では、p_i \geq q' \times b を満たす q' の中で最大のものを探索するという操作が入るので、計算量は探索の方法に依存します。

ここでは、とりあえずの(良くない)方法として、最初の例で行ったような線形探索、すなわち、

q' を1から \ell - 1 まで順に増やしていって、p_i < q' \times b となった時点で q_i \leftarrow q' - 1、最後までそうならなかったら q_i \leftarrow \ell - 1 とする

という方法を取ることにします。このとき、調べる候補は \ell 個です。

1つの q' に対して p_i \geq q' \times b かどうかを調べるには、O(n) ステップかかります。これは、大小比較が4と同じ引き算 p_i - q' \times b の正負判定と同等であることから判ります。

よって、3では \ell \times O(n) = O(\ell n) ステップかかることが判りました。

後は繰り返し回数を書けることで、全体の計算量が (m - n + 1) \times (O(n) + O(\ell n)) = O(\ell (m - n + 1) n) と出ます。\ell は入力の長さに関係ない定数なので、オーダーの中から消去することができます。

定理1: 割り算の(筆算による)計算量は O( (m - n + 1) n) である。

二分探索による改善

上では \ell を定数としてオーダーの中から消しましたが、その方法では \ell が大きいほど不利になります。例えば、1ワード=32ビットは \ell = 2^{32} に対応するので、最悪で 2^{32} 個もの候補を探索しなければならず、これではとても実用に堪えません。これまで扱った計算ではワード長が長いほど有利となるはずなので、これはゆゆ式問題です。

その前にちゃんと、同じ数に対して \ell が変わる場合の計算量を見ておきましょう。\ell を呼び戻して、筆算の計算量がある定数 C > 0 を用いて C \ell (m - n + 1) n と書けるとします。2進法で計算する場合は 2 C (m - n + 1) n です。次に、数値として同じ入力に対して \ell 進法で計算する場合を考えます。2つの入力の桁数はともに 1 / \log \ell 倍になるので、計算量は C (\ell / \log^2 \ell) (m - n + 1) n になります。これは2進法のときの \ell / (2 \log^2 \ell) 倍になっています。例えば、\ell = 2^{32} を代入すると85899346倍にもなります。このように、上の筆算のやり方では \ell が大きいと非常に不利であることが判ります。

さて、それでは何が悪かったのかと言うと、ステップ3の p_i \geq q' \times b を満たす最大の q' の探索を線形探索で行ったことです。

これを改善するには、二分探索を用いるのが定石でしょう。すなわち、真ん中を見て q_i の探索範囲を半分にし、さらにその真ん中を見て探索範囲を半分にし…と繰り返していくのです。例えば、最初の例の場合は、

計算の過程(二分探索)
探索範囲:0-9、中央値:5
456 < 123 \times 5q_1 は5より小さい

探索範囲:0-4、中央値:2
456 > 123 \times 2q_1 は2以上

探索範囲:2-4、中央値:3
456 > 123 \times 3q_1 は3以上

探索範囲:3-4、中央値:4
456 < 123 \times 4q_1 は4より小さい

探索範囲:3-3 → q_1 = 3

と絞り込んでいって q_1 を見つけることができます。この例は数が小さいために改善になっていないのですが、\ell が大きいときには二分探索によって評価回数を大幅に少なくすることができます。

というのは、1回の評価で探索範囲をほぼ半分にできるためです。もし探索範囲が \ell 個ならば、t 回の評価で探索範囲はおよそ \ell / 2^t にまで縮められます。これが1個になった時点で終了なので、t = \log \ell 回程度の比較で目当ての q_i が見つかることになります。

よって、3の探索に二分探索を用いた場合の筆算の計算量は O(\log \ell (m - n + 1) n) となります。これならば、たとえ \ell = 2^{32} でも十分実用的な時間で計算できるでしょう。

同じ数値を2進法と \ell 進法で計算する場合を比較すると、後者は前者の \log \ell/ (2 \log^2 \ell) = 1 / (2 \log \ell) となるので、この方法では \ell が大きいほど有利であることが判ります。

このように二分探索を用いることで、ワード長が長い=基数 \ell が大きい場合でも、問題なく割り算の筆算を行うことができます。

今回はここまで

今回は割り算の計算量の手始めとして、筆算による計算量を出しました。それによって一つの上界が得られました。

m, n 桁の割り算の計算量は O( (m - n + 1) n) である。

また、途中の探索を二分探索とすることによって、ワード長が長い場合でも効率良く計算できることを示しました。

次回は割り算の計算が高速乗算アルゴリズムによって改善する方法を示し、計算量を掛け算と同じ程度のオーダーにできることを示します。それではまた。

*1:集合が演算に対して閉じているとは、すべての要素対に対して演算を行った結果が同じ集合に入ることを言います。このとき、集合と演算の組をもって「代数系」と言います。特に、整数のように加減乗算について閉じている(かつ、演算に関していくつかの法則を満たす)ものを「環」と言います。