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

　Goldschmidt法

　もう一つの方法として、1/bをマクローリン級数で展開し、展開した各項を順に計算していくGoldschmidt(ゴールドシュミット)のアルゴリズムと呼ばれる方法がある。

　Goldschmidt法では、a/bを求めるに当たり、被除数aをx(0)とし、除数bをy(0)とする。そして、その逆数の近似値の初期値をr(0)として、x(i+1)=x(i)*r(i)、y(i+1)=y(i)*R(i) とr(i+1)=2-y(i+1)の計算を繰り返す。この繰り返しでy(n)=1となれば、x(n)がa/bの商となる。Newton-Raphson法とは原理は違うのであるが、1回の繰り返しには2回の乗算と1回の2の補数化が必要であり、また、ビット精度も繰り返しごとに2倍になるので、Newton-Raphson法とほぼ同じ手間で割り算ができる。しかし、詳細にみると、実装の観点からは、Goldschmidt法はNewton-Raphson 法より優れている。2の補数化の処理をサボって否定で代用すると、Newton-Raphson 法ではb*X(i)を計算し、それを否定してからx(i)を掛けるという処理となる。一方、Goldschmidt法では、y(i)を否定してr(i)を掛けるのと同時にx(i)にr(i)を掛けることが可能である。

　図27:Newton-Raphson法とGoldschmidt法による割り算。Newton-Raphson法では、乗算が直前の結果に依存するので、全て直列に実行する必要がある。一方、Goldschmidt法ではxとyの計算は独立であり、並行して計算できる。

　これを図にすると図27のようになり、乗算に必要なサイクル数をNとすると、1回のループ当たり、Newton-Raphson法では2N+1サイクルを必要とするのに対して、パイプライン乗算器を使うと、Goldschmidt法ではN+1サイクルとほほ半分の時間で処理が完了する。Goldschmidt法の浮動小数点割り算器はIBMの初期の超大型機であるSystem360/91で採用された。それ以降も、Goldschmidt法はIBMのG4メインフレームプロセサや、SunのUltraSPARCの前世代のSuperSPARCなどで採用されている。

　このIBM System360/91は、浮動小数点の掛け算を毎秒5.53M回、割り算は1.385M回実行することができた。現在のマイクロプロセサと比較すると、おおよそ1/1000の性能であるが、40年あまり前(1966年の発売)のマシンとしては驚異的な高性能であった。

　前述のように、単精度の除算を考えると計算時間がLog2(N)に比例するGoldschmidt法は不利であるが、IEEE 754rで追加が予定されている4倍精度の浮動小数点除算の場合は、逆に、計算ステップ数が仮数の長さNに比例するSRT法に較べて反復法が有利になる。 113ビット精度の仮数(ガードビットとラウンドビットを入れると115ビット)をSRT割り算器で計算すると、Radix-4の割り算器では58サイクル、Radix-16の割り算器でも29サイクルを必要とする。一方、Goldschmidt法では、2回の掛け算からなる繰り返しをもう一度追加すれば良い。1回の乗算を4サイクルとすると4回の反復を17サイクルで実行でき、IEEE 754rの4倍精度の時代になると、Goldschmidt法が、再度、復権する可能性があると思われる。

反復法による平方根の計算

　Newton-Raphson法やGoldschmidt法により商を求めたように、これらの反復法を用いて平方根を計算することもできる。Newton-Raphson法の場合は、平方根の初期値をテーブルなどで生成し、

　という計算を繰り返す。最終的にx(i)がaの平方根の逆数となると、x(i+1)はx(i)と同じになる。そうなると、最後にx(i+1)×aを計算すると、aの平方根が得られる。平方根の計算も割り算と同様に、繰り返しによりビット精度が倍増するので、8ビット精度の初期値からスタートすると、16ビット、32ビット、64ビットと3回の繰り返しで、IEEEの倍精度浮動小数点クラスの精度に到達する。しかし、割り算の場合はx(i+1)=x(i)×(2-b×x(i))であったので、各繰り返しステップの演算は、2回掛け算と1回の2の補数化で計算できたが、平方根の場合は3回の掛け算と1回の引き算が必要となるので、割り算よりも時間がかかる。

　Goldschmidt法では、x(0)=y(0)=aの初期状態から、z(i)=(3-y(i))/2、x(i+1)=x(i)×z(i)^2、y(i+1)=y(i)×z(i)を繰り返し計算する。ここでiの値にかかわらず、常にx(i)/y(i)^2=1/aであるので、繰り返しにより、x(i)が1.0になれば、y(i)はaの平方根となる。この計算も引き算が1回と3回の掛け算が必要であり、各ステップの計算量はNewton-Raphson法と同じであるが、最後の掛け算は不要である。

　また、 Newton-Raphson法では全ての計算が直前の計算結果をオペランドとするという依存関係があり全ての乗算をシリアルに実行する必要があるが、Goldschmidt法ではxとyの計算には依存関係が無いので、パイプライン乗算器を使う場合には、高速に計算できるというメリットがあるのは、割り算の場合と同様である。