除算 (デジタル)
定数を除数とする除算は、その定数の逆数との乗算と等価である。そのため、除数 D がコンパイル時にわかっている場合(定数の場合)、その逆数 (1/D) をコンパイル時に計算すれば、N·(1/D) という乗算のコードを生成すればよいということになる。浮動小数点数の計算であれば、そのまま適用できる。
整数の場合は、一種の固定小数点数による計算に変形する手法がある。まず、算術的に考えてみる。例えば、除数が3の場合、2/3、4/3、256/3などのどれかを使って乗算し、しかる後に2や4や256で除算すればよい。2進法であれば除算はシフトするだけで良い(16ビット×16ビット=32ビットのような、倍長で演算結果が全て得られる計算機なら、運が良ければ上位16ビットにそのまま解が得られるようにすることもできる)。
回復型(または復元型)除算 (restoring division) を固定小数点数に対して行う場合を解説する。ここで以下を前提とする。
0 ≤ N
0 < D < 1.
商の各桁 q は数字の集合 {0,1} のいずれかである。
二進(基数2)の基本的アルゴリズムは次の通り。
なお、q(i) は商のi番目のビットを意味する。このアルゴリズムでは減算の前にシフトした値 2P をセーブしておいて、回復(復元)させるステップが必要だが、これはレジスタ T を例えば T = P << 1 としておいて、減算 2P − D の結果が負だった場合にレジスタ T を P にコピーすればよい。
不実行回復型除算は回復型除算とよく似ているが、2*P[i] の値をセーブしておく点が異なり、TP[i] ≤ 0 の場合でも D を加算して戻してやる必要がない。
非回復型(または非復元型)除算 (non-restoring division) は商の桁の数字として {0,1} ではなく {−1,1} を使用する。引きっ放し法ともいう。二進(基数2)の基本的アルゴリズムは次の通り。
このアルゴリズムで得られる商は、各桁が −1 と +1 であり、通常の形式ではない。そこで通常の二進形式への変換が必要である。例えば、次のようになる。
ここで、 N ̄ = n e g ( n o t ( P ) ) = P + 1 {\displaystyle {\bar {N}}={\rm {{neg}({\rm {{not}(P))=P+1}}}}} が成り立つことに注意すると、以下のように修正できる。