前回までの記事で、コンピューターは足し算を全加算器で、引き算を「2 の補数」を使った足し算で計算していることを見てきました。足し算の回路が1つあれば、足し算も引き算もできます。
では、割り算はどうでしょうか。答えを先に言うと、コンピューターは割り算を「ずらす」と「引けるかどうか試す」の繰り返しで計算しています。小学校で習った筆算とほとんど同じ手順です。この記事では、7 ÷ 2 = 3 あまり 1 を例に、その仕組みを説明します。
- 割り算は「何回引けるか」で、2 進数の筆算なら商の各桁は 0 か 1 だけになること
- 「ずらす」「引いてみる」「戻す」を繰り返す、回路での割り算の手順
- 2 のべき乗での割り算、0 で割ったとき、割り算が遅い理由
割り算は「何回引けるか」
7 ÷ 2 は、「7 から 2 を何回引けるか」と言い換えられます。実際に引いてみると、7 → 5 → 3 → 1 と3回引けて、残りの 1 は 2 より小さいのでもう引けません。引けた回数の 3 が商、残った 1 があまりです。
引き算は前回の記事のとおり足し算の回路でできるので、これだけで割り算は作れます。ただ、この方法には大きな弱点があります。引く回数が商の大きさだけ必要になることです。たとえば 1,000,000 ÷ 1 では、引き算を 100 万回繰り返すことになります。
筆算は「ずらして引く」
そこで、小学校で習った割り算の筆算を思い出してみます。筆算では、割られる数の上の桁から1桁ずつ下ろしながら、「割る数が何回引けるか」をその桁ごとに考えます。156 ÷ 12 なら、次のようになります。
| 手順 | 見ている数 | 12 が何回引けるか（商の桁） | 引いた残り |
|---|---|---|---|
| 1 | 1 | 0 回 | 1 |
| 2 | 15（残り 1 に 5 を下ろす） | 1 回 | 15 − 12 = 3 |
| 3 | 36（残り 3 に 6 を下ろす） | 3 回 | 36 − 36 = 0 |
商は 013、つまり 13 で、あまりは 0 です。桁をずらしながら進めるので、引く回数は桁ごとに最大9回で済みます。商がどれだけ大きくても、桁数に比例した手間で終わります。
2 進数の筆算はもっと簡単
同じ筆算を 2 進数でやると、さらに簡単になります。2 進数では商の各桁は 0 か 1 しかないので、各桁で考えることは「割る数が1回引けるか、引けないか」だけです。
7 ÷ 2 を 2 進数で計算する
7 は 0111、2 は 10 です。0111 の上の桁から1ビットずつ下ろし、そのたびに 10（2）が引けるかを調べます。
| 手順 | 下ろすビット | 見ている数（余り） | 2 が引けるか | 商のビット | 残り |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 引けない | 0 | 0 |
| 2 | 1 | 1 | 引けない | 0 | 1 |
| 3 | 1 | 11（3） | 引ける | 1 | 11 − 10 = 1 |
| 4 | 1 | 11（3） | 引ける | 1 | 11 − 10 = 1 |
商のビットを上から並べると 0011（3）、最後の残りが 1 です。7 ÷ 2 = 3 あまり 1 になりました。
13 ÷ 3 でも確かめる
もう1つ、13（1101）÷ 3（11）も同じ手順で計算してみます。
| 手順 | 下ろすビット | 見ている数（余り） | 3 が引けるか | 商のビット | 残り |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 引けない | 0 | 1 |
| 2 | 1 | 11（3） | 引ける | 1 | 11 − 11 = 0 |
| 3 | 0 | 0 | 引けない | 0 | 0 |
| 4 | 1 | 1 | 引けない | 0 | 1 |
商は 0100（4）、あまりは 1 で、13 ÷ 3 = 4 あまり 1 です。4 ビットの割り算なら、4 回の「下ろして、引けるか調べる」で終わります。
回路ではどうやっているか
この手順を回路で行うには、次の3つの部品があれば足ります。
| やること | 回路での実現 |
|---|---|
| 次のビットを下ろす | 余りを入れておく場所（レジスタ）を1ビット左へずらし（シフト）、空いた一番下に割られる数の次のビットを入れる |
| 引けるか調べる | 余りから割る数を実際に引いてみる。引き算は前回の記事のとおり、加算器と 2 の補数でできる |
| 結果を判定する | 引いた結果が負なら「引けない」。負かどうかは、結果の符号ビット（または桁上がりの有無）で分かる |
引いた結果が負だったときは、引く前の余りに戻します。この「戻す」手順があるので、この方法を回復型の割り算（restoring division）と呼びます。
ここで使っている部品は、ずらす回路、加算器、判定の3つだけです。足し算と引き算のために作った加算器を、割り算でもそのまま使っています。
回復型の割り算は、商のビットを1つ求めるごとに「引く」と「戻す」が必要です。そこで、戻す手順をなくした非回復型の割り算（non-restoring division）があります。引いた結果が負になっても元に戻さず、次の桁では割る数を引く代わりに足すことで、1桁あたりの足し算・引き算を1回にしています。実際の CPU では、一度に複数ビットの商を求める SRT 除算などの、さらに速い方法も使われています。初代 Pentium の浮動小数点の割り算の不具合（FDIV バグ）は、この SRT 除算で使う表の一部の値が抜けていたことが原因でした。
2 のべき乗で割るときは、ずらすだけ
10 進数で 1,200 ÷ 100 が、右の 2 桁を消すだけで 12 になるのと同じように、2 進数では 2、4、8 … といった 2 のべき乗で割るとき、右へずらす（右シフト）だけで商が求まります。右にはみ出したビットがあまりです。
シフトは引き算を繰り返すよりずっと速いので、プログラムでも 2 のべき乗の割り算はシフトに置き換えられることがよくあります。ただし、負の数を右シフトしたときの丸め方は、割り算と違います。
2 の補数の数を算術右シフトすると、結果は常に小さいほう（負の無限大の方向）へ丸められます。一方、多くのプログラミング言語の整数の割り算は 0 の方向へ丸めます。たとえば −7 ÷ 2 は、C 言語（C99 以降）の割り算では −3 ですが、算術右シフトでは −4 になります。
0 で割るとどうなるのか
引き算の繰り返しで考えると、0 で割るのは「0 を何回引けば終わるか」という問いになり、いつまでも終わりません。筆算の手順でも、どの桁でも「引ける」と判定されてしまい、正しい答えは出ません。そのため、0 で割る操作の扱いは、CPU や言語ごとに決められています。
| 場面 | 0 で割ったときの扱い |
|---|---|
| x86 の整数の割り算（DIV 命令） | 除算エラー（#DE）という例外が起きる。商が大きすぎて結果を入れる場所に入らないときも同じ例外になる |
| C 言語・C++ の整数の割り算 | 未定義動作（何が起きるか決まっていない） |
| Python など | 例外が発生し、プログラムで受け止められる |
| 浮動小数点（IEEE 754） | 0 以外の数 ÷ 0 は符号付きの無限大、0 ÷ 0 は NaN（数ではない値）になる |
割り算は足し算より時間がかかる
回復型の割り算は、商を1ビット求めるごとに引き算を1回行うので、64 ビットの割り算なら 64 回の繰り返しが必要です。速い方法を使っても、割り算は足し算のように1回の計算では終わりません。x86 の CPU では、整数の割り算命令は 10〜20 サイクル程度かかることが多く、1 サイクル程度で終わる足し算に比べて大きく遅くなります。
そのため、コンパイラは定数で割る割り算を、かけ算とシフトの組み合わせに置き換えて速くすることがあります。プログラムで x / 10 と書いても、CPU の中では割り算命令が使われていないこともあるのです。
まとめ
| 項目 | ポイント |
|---|---|
| 割り算の考え方 | 「割る数を何回引けるか」。単純に引き続けると、商の大きさだけ時間がかかる |
| 筆算 | 上の桁から1桁ずつ下ろし、桁ごとに何回引けるかを考える。2 進数なら各桁は「引ける（1）か、引けない（0）か」だけ |
| 回路での割り算 | 余りを1ビットずらして次のビットを下ろし、割る数を引いてみる。負なら元に戻す（回復型）。ビット数だけ繰り返す |
| 使う部品 | シフト、加算器（引き算は 2 の補数）、符号の判定。足し算・引き算と同じ加算器を使う |
| 2 のべき乗の割り算 | 右シフトだけで計算できる。負の数では丸め方が割り算と違う |
| 0 での割り算 | 答えが決まらないので、例外や未定義動作など、CPU や言語ごとに扱いが決められている |
半加算器から始まって、足し算、引き算、割り算まで、すべて加算器を中心に組み立てられていることが分かりました。かけ算も、割り算の逆で「ずらして足す」の繰り返しで計算できます。
コメント