コンピュータアーキテクチャの話 (102) Newton-Raphson法とGoldschmidt法

　

　現在のマイクロプロセサでは、SRT割り算器で商を求める方式が広く使われているが、浮動小数点の除算や平方根の計算には、別の方式も使われている。その代表的なものが、ニュートンラプソン(Newton-Raphson)法とゴールドシュミット(Goldschmidt)法である。これらの方法では、商や平方根の近似値を初期値として、誤差を計算し、次々と近似値を補正するというプロセスを繰り返して精度を改善して行く。このため、これらの方法は、一般的に反復法と呼ばれる。

Newton-Raphson法による除算

　a/bの商をQとすると、Q=a×(1/b)である。ここでf(X)=1/X-bという関数を定義する。そうすると、f(X)がゼロとなると、1/X=bとなり、X=1/bとなる。このようなXが求まれば、a×X=Qとなり割り算ができる。ということで、割り算は、f(X)=0となるXを見つけるという問題となる。

　Newton-Raphson法では、

　の形で、現在の値Xiで関数f(X)とその微分値f'(X)からXiの補正量を計算してf(X)=0に収束させていく。ここでf(X)は1/X-bであるので、この式は、

　となる。つまり、Xiから次の値Xi+1を求めるのは、Xiとbの掛け算を行い、それを2から引いて、更にXiを掛けるという操作になる。2から引くという操作は2の補数化であり、各ビットを反転して最下位の桁に＋1すれば良いが、この＋1をサボっても誤差は小さいので、各ビットの否定だけとして、計算時間を短縮する実装が多い。そうすると、2回の乗算でXi+1を求めることができる。

　この方法での計算では、Xiの精度(有効ビット数)は繰り返しごとに2倍になる。最初のX0をROMなどを使って8ビット精度で与えると、1回の繰り返しでX1は16ビット精度となり、2回の繰り返しでX2は32ビット精度、3回目のX3では64ビット精度となり、倍精度浮動小数点で必要とされる精度をクリアすることが出来る。そして、最後にQ=a×X3を計算すると商が求まる。但し、IEEE 754が規定する無限精度で計算した結果とは完全には一致しないケースがあり、規格準拠とする場合は、剰余を求めて補正するサイクルが必要となる。

　補正サイクルを別とすると、Newton-Raphson法では、8ビット精度の初期値からスタートすると、7回の乗算で倍精度浮動小数点の商が求まる。乗算に何サイクル掛かるかは設計により異なるが、仮に、1回の乗算に必要なサイクルが4サイクルであるとすると28サイクルで商が求まるので、Radix-4のSRT割り算器でガードビットなどを含めて56ビットの商を求める場合の28サイクルと同じになる。

　しかし、25ビット精度で良い単精度の場合でも、Newton-Raphson法では5回の乗算が必要であり、必要サイクル数が半減するRadix-4のSRT割り算器より遅くなってしまう。このため、単精度の除算性能を考慮すると、Radix-4のSRT割り算を使う方が有利となってしまうので、最近のマイクロプロセサではSRT法を採用する例が多い。

　Newton-Raphson法の除算の実装は、単純に数値計算としてソフトウェアだけでも実現できるが、ハードウェアとして実装する場合は、中間の乗算ステップでは、正規化や丸めを省いて、固定小数点形式で演算を行う。このような演算の過程での計算精度を保証するため、乗算器のビット数は、浮動小数点乗算器で必要とされる56ビットより多少、ビット数の多い乗算器が用いられる。