除算 (デジタル)
数値的（ディジタル）な除算アルゴリズムはいくつか存在する。それらのアルゴリズムは、低速な除算と高速な除算の2つに分類できる。低速な除算は反復する毎に最終的な商を1桁ずつ生成していくアルゴリズムである。回復型、不実行回復型、非回復型、SRT除算などがある。高速な除算は最初に商の近似値から出発して徐々に正確な値に近づけていくもので、低速な除算よりも反復回数が少なくて済む。ニュートン-ラプソン法とゴールドシュミット法がこれに分類される。
以下の解説では、除算を formula_1 で表し、
とする。
ここで示すアルゴリズムでは、"N" を "D" で割って、商 "Q" と余り "R" (remainder) を得る。いずれの値も符号なし整数として扱う。
codice_1
これは、後述の回復型と基本的には同じである。
低速な除算技法は全て次の漸化式に基づいている。
ここで
である。
回復型（または復元型）除算 (restoring division) を固定小数点数に対して行う場合を解説する。ここで以下を前提とする。
商の各桁 "q" は数字の集合 {0,1} のいずれかである。
二進（基数2）の基本的アルゴリズムは次の通り。
codice_2
なお、q(i) は商のi番目のビットを意味する。このアルゴリズムでは減算の前にシフトした値 2"P" をセーブしておいて、回復（復元）させるステップが必要だが、これはレジスタ "T" を例えば "T" = "P" « 1 としておいて、減算 2"P" − "D" の結果が負だった場合にレジスタ "T" を "P" にコピーすればよい。
不実行回復型除算は回復型除算とよく似ているが、codice_3 の値をセーブしておく点が異なり、codice_4 の場合でも "D" を加算して戻してやる必要がない。
非回復型（または非復元型）除算 (non-restoring division) は商の桁の数字として {0,1} ではなく {−1,1} を使用する。引きっ放し法ともいう。二進（基数2）の基本的アルゴリズムは次の通り。
このアルゴリズムで得られる商は、各桁が −1 と +1 であり、通常の形式ではない。そこで通常の二進形式への変換が必要である。例えば、次のようになる。
SRT除算の名は、考案者のイニシャル (Sweeney, Robertson, Tocher) に因んだもので、多くのマイクロプロセッサの除算器の実装に使われている。SRT除算は非回復型除算に似ているが、被除数と除数に基づいてルックアップテーブルを使い、商の各桁を決定する。Intel Pentium プロセッサの浮動小数点除算バグは、このルックアップテーブルの間違いが原因だった。千以上のエントリがあるテーブルのうち理論上参照しないと信じられていた5個のエントリを省略したことが原因である。基数を大きくすると一度の反復で複数ビットを求められるため、高速化可能である。
ニュートン-ラプソン除算 (Newton-Raphson Division) は、ニュートン法を用いて formula_3 の逆数を求め、その値と formula_4 の乗算を行うことで商 formula_5 を求める。
ニュートン-ラプソン除算のステップは次の通り。
formula_3 の逆数をニュートン法で求めるには、formula_11 で値がゼロとなる関数 formula_12 を求める必要がある。明らかにそのようになる関数としては formula_13 があるが、これは formula_3 の逆数が既にわかっていないと使えない。さらに formula_12 の高次導関数が存在しないため、反復によって逆数の精度を増すこともできない。実際に使用できる関数は formula_16 で、この場合のニュートン-ラプソンの反復は次の式で表される。
この場合、formula_18 から乗算と減算だけで計算可能であり、積和演算2回でもよい。
誤差を formula_19 と定義すると
となる。
除数 "D" が 0.5 ≤ "D" ≤ 1 となるようビットシフトを施す。同じビットシフトを被除数 "N" にも施せば、商は変化しない。すると、ニュートン-ラプソン法の初期値として次のような線形近似が使える。
区間 formula_23 においてこの近似の誤差の絶対値をなるべく小さくするには、次の式を使用する。
この近似を用いると、初期値の誤差は次のようになる。
この技法の収束は正確に二次的なので、formula_26 桁の二進数の値を計算する場合のステップ数は次のようになる。
ゴールドシュミット除算の名は Robert Elliott Goldschmidt に因んだもので、除数と被除数の両方に共通の係数 "F" をかけていき、除数 "D" が 1 に収束するようにする。すると 被除数 "N" は商 "Q" に収束する。つまり、以下の式で分母が1になるようにもっていく。
ゴールドシュミット除算のステップは次の通り。
0 AMDの Athlon やその後のモデルで使用されている。
ゴールドシュミット法は、二項定理を使ってより単純化した係数を使うことができる。formula_32 となるよう N/D を2の冪でスケーリングすることを前提とする。ここで formula_33 となるよう "x" を求め、formula_34 とする。すると次のようになる。
formula_36 なので、formula_37 ステップ後には formula_38 と 1 の相対誤差は formula_39 となり、formula_40 の二進数の精度では 1 と見なせるようになる。このアルゴリズムをIBM方式と呼ぶこともある。
ハードウェアの実装に使われている設計技法は、一般に数千桁から数百万桁の十進数値での除算（任意精度演算）には適していない。そのような除算は例えば、RSA暗号の合同式の計算などでよく見られる。大きな整数での効率的除算アルゴリズムは、まず問題をいくつかの乗算に変換し、それに漸近的に効率的な（つまり桁数が大きいほど効率がよい）を適用する。例えば、やショーンハーゲ・ストラッセン法がある。乗算への変換としては、上述したニュートン法を使った例や、それより若干高速な アルゴリズムがある。ニュートン法は同じ除数で複数の被除数に対して除算を行う場合に特に効率的で、除数の逆数を1度計算しておくと、毎回それを流用できる。
定数を除数とする除算は、その定数の逆数との乗算と等価である。そのため、除数 "D" がコンパイル時にわかっている場合（定数の場合）、その逆数 (1/"D") をコンパイル時に計算すれば、"N"·(1/"D") という乗算のコードを生成すればよいということになる。浮動小数点数の計算であれば、そのまま適用できる。
整数の場合は、一種の固定小数点数による計算に変形する手法がある。まず、算術的に考えてみる。例えば、除数が3の場合、2/3、4/3、256/3などのどれかを使って乗算し、しかる後に2や4や256で除算すればよい。2進法であれば除算はシフトするだけで良い（16ビット×16ビット＝32ビットのような、倍長で演算結果が全て得られる計算機なら、運が良ければ上位16ビットにそのまま解が得られるようにすることもできる）。
これを整数演算でおこなう場合は、256/3は当然正確な整数にはならないので、誤差があらわれる。しかし、シフト幅をより大きくし、値の範囲に注意すれば、常に不正確な部分はビットシフトによって捨てられるように変形できることがある。
具体例として32ビットの符号なし整数で、除数が3の場合 formula_41 との乗算に変換できる。まず 2863311531 との乗算を行い、その後33ビット右シフトする。この値は正確には formula_42 である。
場合によっては、定数による除算を一連のシフト操作と加減算に変換できることもある。特に興味深いのは10による除算で、シフトと加減算で正確な商（と必要なら余り）が得られる。