除算 (デジタル)
ゴールドシュミット除算の名は Robert Elliott Goldschmidt に因んだもので、除数と被除数の両方に共通の係数 Fi をかけていき、除数 D が 1 に収束するようにする。すると 被除数 N は商 Q に収束する。つまり、以下の式で分母が1になるようにもっていく。
Q = N D F 1 F 1 F 2 F 2 F ... F ... {\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}}
ゴールドシュミット除算のステップは次の通り。
乗数となる係数 Fi を推定により生成する。
除数と被除数に Fi をかける。
除数が十分 1 に近くなったら、被除数を返す。さもなくばステップ1に戻ってループする。
0 < D < 1 となるよう N/D を調整済みとし、それぞれの Fi は D から次のように求める。
F i + 1 = 2 − D i {\displaystyle F_{i+1}=2-D_{i}}
除数と被除数にその係数をかけると次のようになる。
N i + 1 D i + 1 = N i D i F i + 1 F i + 1 {\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}}
k 回の反復で十分なら、 Q = N k {\displaystyle Q=N_{k}} となる。
ゴールドシュミット法はAMDの Athlon やその後のモデルで使用されている。