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

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

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

割り算を使わずに割り算をする

妙なタイトルですが、今回は次のような問題を考えます。

割り算を計算をするために電卓を使いたい。しかし、電卓を持ってきたところ、割り算のボタンが故障していて使えないことが判った。他のボタンは問題なく機能しているが、割り算だけは使えない。なんとか割り算ボタンを使わずに目的の割り算を計算できないか?ボタンを押す回数はできるだけ少ない方がいい。

「電卓買えよ」という突っ込みは置いといて、要するに割り算を他の3つの四則演算だけを使って計算できるかという話です。

以下、10進 m 桁の非負の整数 a と10進 n 桁の正の整数 b について a/b の10進小数での値を求める方法を考えます。

筆算による方法

上の問題の答えは、もちろん「できる」です。なぜなら、我々は筆算で割り算の答えを得ることができるからです。筆算を行うのに必要な計算は、掛け算と引き算(および比較)だけであり、この問題の答えになっています。

例えば、22/7 = 3.142857 \dots を小数第2位まで求め、それより下の位は四捨五入するとしましょう。これを整数の計算だけで行うには、22 \div 7 の小数点を右に2つずらしたものが 2200 \div 7 であることに注目します。まず普通に割り算を行い 2200 \div 7 = 314 \dots 2 を得ます。小数部分は余りから 2 / 7 なので、2 < 7 \times 0.5 より四捨五入すると切り捨てられることが判ります。よって、2200 \div 7 の小数点以下を四捨五入した結果は314となります。後は小数点を2つ左にずらすと、3.14となり、これが求める結果です。

問題はボタンを押す回数ですが、この計算を行うためには、筆算を m + k - n + 1 段計算する必要があります。一つの段については、定数回の掛け算および比較で実行できるので、ボタンを押す回数は O(m + k - n + 1) 回となります。

実はこの方法は良いものではありません。以下に述べるように、ずっと少ないボタン操作で割り算を行うことができるのです。それはともかく、割り算を使わずに割り算をすることが実際に可能であることは解りました。

級数による方法

別の方法として、よく知られている級数

\displaystyle \frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots \quad (|x| < 1)

を用いるということが考えられます。例えば、10/9 = 1.111111 \dots を求めるには、少し変形が必要ですが、

\displaystyle \frac{10}{9} = \frac{1}{1 - \frac{1}{10}} = 1 + 0.1 + 0.1^2 + \dots

と計算できます。右辺の第7項までの和が 1.111111 になることは明らかでしょう。

これを一般化するには少し工夫が必要です。例えば、同じ方法で 7/6 = 1.166666 \dots を求めようとすると

\displaystyle \frac{7}{6} = \frac{1}{1 - \frac{1}{7}} = 1 + \frac{1}{7} + \left( \frac{1}{7} \right)^2 + \dots

となって、1/7 の計算をする必要が出てきてしまいます。これでは割り算を使わずに割り算をすることにはならないというわけです。そこで次のような変形をします。

\displaystyle \frac{7}{6} = \frac{7/10}{6/10} = 0.7 \times \frac{1}{1 - 0.4}

何をしたかというと、分母を1以下の値にするために分母、分子を基数の10で割ったのです。10での割り算は小数点を左に1つずらすことと同じなので、割り算を使わずに実現できます。こうすれば最後の分数は

\displaystyle \frac{1}{1 - 0.4} = 1 + 0.4 + 0.4^2 + \dots

となって、こちらも割り算を使わずに計算できるというわけです。試しに第7項まで計算すると 1.663936 となるので、元の計算結果は 0.7 \times 1.663936 = 1.1647552 となります。

以上を一般化すると、a / b を計算するには、b の桁数 n について 10^n b < 1 から、x = 1 - 10^{-n} b として

\displaystyle \frac{a}{b} = \frac{10^{-n} a}{10^{-n} b} = 10^{-n} a \times \frac{1}{1 - x}
\displaystyle = 10^{-n} a \times \left( 1 + x + x^2 + \dots \right)

とすればよいということになります。今は10進で考えましたが、任意の基数 \ell \geq 2 についても、x = 1 - \ell^{-n} b として

\displaystyle \frac{a}{b} = \frac{\ell^{-n} a}{\ell^{-n} b} = \ell^{-n} a \times \frac{1}{1 - x}
\displaystyle = \ell^{-n} a \times \left( 1 + x + x^2 + \dots \right)

と一般化できます。肝要なのは \ell^{-n} を掛ける計算が小数点をずらすことと同じであり、\ell^{-n} a, \ell^{-n} b, x のすべてが割り算を使わずに計算できるということです。

収束の速さ

級数による方法で問題となるのは、第何項までを足せば答えが目標の精度に収まるのかということです。当然ながら早く答えに近づく方がよいです。

先に上げた筆算による方法と違って、級数による方法では小数第 k 位までを正確に出すというのがそのままではできない(もう少し計算が必要)ので、目標精度は小数第 k+1 位を四捨五入して一致するということにします。これは、絶対誤差が \epsilon = 5 \times 10^{-k-1} より小さければ達成できます。すなわち、第 t 項までの和をとって計算した値を

\displaystyle q_t = 10^{-n} a \times \left( 1 + x + x^2 + \dots + x^{t-1} \right)

とするとき

\displaystyle \left| \frac{a}{b} - q_t \right| < \epsilon

となるような t の値を求めればいいというわけです。

右辺は q_t \to a / b \; (t \to \infty) から、

\displaystyle \left| \frac{a}{b} - q_t \right| = \left| q_{\infty} - q_t \right|
\displaystyle = 10^{-n} a \times \left( x^t + x^{t+1} + x^{t+2} \dots \right)
\displaystyle = 10^{-n} a x^t  \left( 1 + x + x^2 + \dots \right)
\displaystyle = 10^{-n} a x^t  \times \frac{1}{1-x} = 10^{-n} a x^t  \times \frac{1}{10^{-n} b}
\displaystyle = \frac{a}{b} x^t

となります。よって、絶対誤差を \epsilon 以内に収めるには

\displaystyle x^t = \frac{b}{a} \epsilon

から

\displaystyle t > \frac{\log_{10} \frac{a}{b} + \log_{10} \frac{1}{\epsilon}}{\log_{10} \frac{1}{x}}

を取ればいいことが解りました。ただし、0 < x < 1 から分母の対数が正になるようにしました。

しかしこの段階では x が1に近いとき分母が0に近づいて上の t が無限に大きくなってしまうので、まだ完全ではありません。それには x のより強い上界が必要です。x = 1 - 10^{-n} b を最大にする b とは、n 桁の数で最小のもの、すなわち 10^{n-1} です。よって、x \leq 1 - 1/10 = 9/10 と出ます。これを上の t の式に代入すると、

\displaystyle t > \frac{\log_{10} \frac{a}{b} + \log_{10} \frac{1}{\epsilon}}{1 - \log_{10} 9}

で、具体的に数を出すと

\displaystyle t = 22 \times \left( \log_{10} \frac{a}{b} + \log_{10} \frac{1}{\epsilon} \right)

で十分であるという結果が得られました。

ところで、a < 10^m, b \geq 10^{n-1} なので a/b < 10^{m-n+1} 、また、\epsilon = 5 \times 10^{-k-1} から

\displaystyle t = O(m-n+k+1)

と出ます。少し前に見たことのある形ですね。

級数 1 + x + x^2 + \dots + x^{t-1} を計算するには、

  1. r \gets 0, y \gets 1
  2. i \gets 1, 2, \dots t について3-4を繰り返す。
  3. r \gets r + y
  4. y \gets y \times x
  5. r を出力

とすればよいです。1反復あたりのボタン操作の回数は定数で、それを t 回繰り返すので、全体では O(m-n+k+1) 回のボタン操作が行われることになります。

ここまで来て、この級数による方法では筆算による方法と同じ程度の結果を得るのに同じ程度のボタン操作が必要であることが解ります。つまりは改善にはなっていないというわけです。残念でした。

しかし諦めるのはまだ早いです。要は級数の計算方法が悪かったのです。これを劇的に改善するのが次の方法です。

積による方法

先の方法では級数を一つ一つ足していたので、一気に二倍先の項まで足せる方法があればよいわけです。次の計算を見てください。

\displaystyle 1 + x
\displaystyle (1 + x)(1 + x^2) = 1 + x + x^2 + x^3
\displaystyle (1 + x + x^2 + x^3)(1 + x^4) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7

これを一般化すると、s \geq 1 について

\displaystyle (1 + x)(1 + x^2) \dots (1 + x^{2^{s-1}}) = 1 + x + x^2 + \dots + x^{2^s - 1}

となると思われます。大きい記号で書くと

\displaystyle \prod_{i = 0}^{s-1} (1 + x^{2^i}) = \sum_{i = 0}^{2^s - 1} x^i ・・・(*)

です。証明は s による帰納法でできるので一応やってみましょう。

まず s = 1 の場合は 1 + x = 1 + x で明らかです。

s-1 までで成り立っているとすると、

\displaystyle \prod_{i = 0}^{s-1} (1 + x^{2^i}) = (1 + x^{2^{s-1}}) \prod_{i = 0}^{s-2} (1 + x^{2^i})
\displaystyle = (1 + x^{2^{s-1}}) \sum_{i = 0}^{2^{s-1} - 1} x^i = \sum_{i = 0}^{2^{s-1} - 1} x^i + x^{2^{s-1}} \sum_{i = 0}^{2^{s-1} - 1} x^i
\displaystyle = \sum_{i = 0}^{2^{s-1} - 1} x^i + \sum_{i = 2^{s-1}}^{2^s - 1} x^i = \sum_{i = 0}^{2^s - 1} x^i

より、(*)は s でも成り立ちます。

よって、すべての s \geq 1 について(*)が成り立つことが示せました。

(*)の左辺は次のようにして計算できます。

  1. r \gets 1, y \gets x
  2. i \gets 1, 2, \dots s について3-4を繰り返す。
  3. r \gets r \times (1 + y)
  4. y \gets y \times y
  5. r を出力

すると、s 回の反復で右辺は 2^s 個の項まで足すことができるのです。

収束の速さで求めた項数の式を使うと、

\displaystyle 2^s = O(m - n + k + 1)

で十分なので、この方法での反復回数は s = \log_2 (m - n + k + 1) + O(1) にまで減らせます。ここでも1反復あたりのボタン操作の回数は定数なので、全体では O(\log (m - n + k + 1)) 回のボタン操作が行われることになります。

まとめ

今回は、割り算を使わずに割り算を行う方法について見ました。筆算による方法は小数第 k 位までを正確に出せますが、多くの掛け算を行う必要がありました。級数による方法は単純にやると筆算と同じ程度の性能ですが、積を使うことで級数の計算を速くできることを示しました。その方法では、10進 m 桁の非負の整数 a と10進 n 桁の正の整数 b について、小数第 k 位相当の精度を得るには、O(\log (m - n + k + 1)) 回の演算で十分であることが解りました。

記事の3番目に述べた方法をGoldschmidt法といいます。これの良い所は、高速乗算アルゴリズムを少ない回数だけ使って割り算を行えることです。実際の計算は有限桁で行うので誤差の評価が入って面倒なのですが、大枠で捉えれば、掛け算の計算量のlog倍程度の計算量で割り算を計算できることになるのです。