現代のコンピュータってどうして割り算が苦手なのでしょうか？？

Question

掛け算と違って桁数が増えると割り算は遅くなる。

除算（割り算）も一番簡単で分かりやすい方法は、割り算の基本理念に基づいて、割られる数から割る数を引いていき、商が［1］以下になるまで何回引いたかをカウントする方法です。

2進数を右にSビット論理シフトすると、2-s倍すること(2sで割ること)に相当

現代のCPUには「割り算用の回路」が組み込まれているそうですが・・・
どこかで「200桁くらいの割り算をやるとかなりの年数がかかる」みたいな情報を見かけたことがあります。

#桁数が増えると割り算の演算速度が極端に遅くなる理由がわかりません。
以下のサイトを参考にしました。

実は足し算しかできない!?
あなたは論理演算がわかりますか？

#ソフトウェアでの工夫
C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか？？
桁を減らし、回数を増やした方がはやくなるかな？と思いました。

1/(x-2)(x-5) → 1/3(1/x-5 - 1/x-2) みたいに？

面白いサイトを見つけましたので、載せておきます。
プログラムによる数値演算のベンチマーク

教えてください。

Answer 1

乗算に関しては、Karatsuba法では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます（n桁×n桁の掛け算ででO(n^1.59)程度）し、3つの乗算のうち2つは並列実行できます。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。

これに対して、除算の場合、「分けて計算する」という方法が使えないので、O(n^2)のオーダーから減らすことができません（「割る数の桁数に比例した処理」を「割られる数の桁数に比例した回数」だけ繰り返すことになります）。上の桁が決まらないと下の桁の計算に入れないので、並列実行にも向きません。

結論：除算が遅い、というより、乗算が高速化できるから相対的に遅くなってしまう

なお、「素因数分解で割る数を小さくする」というアイデアは、素因数分解の手間自体が莫大となるため、一般の数に対する割り算の高速化にはほぼ使えません（「素因数分解がおいそれとできない」ことそのものがRSA暗号の安全性の鍵となっている、というように、本質的に困難な問題です）。

Comments

[strike1217]

>乗算が高速化できるから相対的に遅くなってしまう
そうなんですか！

割り算が遅いわけではないんですね。

[strike1217]

yubaさんのURLの「一般的にコンピュータの除算は、他の演算に比べて非常に遅いです。」
やはり、割り算自体が遅いというわけではないようですね。

[tacsheaven]

もうすでに終わってるから余談ですが、除算を速くするために「予め除算結果のテーブルを用意していてそれを参照する」というのを、CPU レベルでやっています。
で……もうIT業界でははるか昔のこと（1994年10月ですから22年前）、Intel の Pentium プロセッサで、この表を誤ったために特定の除算の場合に結果が正しくない、というエラッタを出しました。世にいう「Pentium FDIV バグ」です。このときはまあいろいろ言われましたねえ…（当時のキャッチコピー、「Intel 入ってる」に引っかけてまあいろいろとパロディが…）

[strike1217]

除算を速くするためのテーブルというものが存在するんですか！！
なるほどです！

Answer 2

もしかして極端に時間がかかる、とは、現代暗号である公開鍵暗号方式の基本となる、RSA 暗号における素因数分解の困難さにまつわる話でしょうか？

割り算が遅いのではなく、素因数分解に近道がない（解くための公式がないため、愚直に試すしかない）ことを示すものです。

※この「近道がない」ことはまだ数学的には証明されておらず、「P≠NP予想」という数学における未解決問題の一つとなっています。

Comments

[strike1217]

>「P≠NP予想」という数学における未解決問題の一つとなっています

調べてみます。
割り算が遅いのではないのですね！

Answer 3

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか？？

桁を減らし、回数を増やした方がはやくなるかな？と思いました。

除算を高速化する工夫ということであればもっと効率的なものがあります。
整数の除算は、1回の乗算に変換することができるのです。
http://www.emit.jp/prog/prog_div.html
もちろん、その変換作業に除算が必要なのですが。

ということは、Cのプログラム上で除数が定数であれば、コンパイルの時点でこの乗算への変換作業をやってしまえば実行時の効率が上がります。
そして、ここまで言えば気付かれていることかもしれませんが、コンパイラにはまず間違いなくこの最適化が実装済みです。

Comments

[strike1217]

整数除算の高速化のための最適化が備わっているのですね！
ありがとうございます。

Answer 4

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか？？

桁を減らし、回数を増やした方がはやくなるかな？と思いました。

基本実行環境での測定（プロファイル）がいちばんの早道です。
また、下手に人間が最適化を行うよりも、コンパイラに任せるのが吉だと思います。
もちろん、大局的な最適化は人間が行った方が良いでしょうけれど。