読者です 読者をやめる 読者になる 読者になる

kivantium活動日記

プログラムを使っていろいろやります

浮動小数点数の除算

この記事はkivantium Advent Calendarの16日目です。

昨日浮動小数点数の加減算を扱いました。
今日は演算器シリーズの最終回として浮動小数点数の除算を取り上げます。

基本原理

浮動小数点数の演算を行うには符号部・指数部・仮数部を決める必要があります。
割り算の場合、符号部は2つの数が同符号なら結果は正、異符号なら負になります。
指数部と仮数部は (s_1\times 2^{e_1})/(s_1\times 2^{e_2}) = (s_1/s_2)\times 2^{e_1-e_2} という関係から指数部の減算と仮数部の除算を行えば決まります。

一番重い処理となるのは仮数部の除算ですが、これを実現する方法として

  • SRT法などの整数と同じ方法を使う
  • Newton-Raphson法
  • Goldschmidt法

があります。

整数と同じ方法

これはbit数に応じて繰り返し引き算を行って仮数部を決定する方法です。
仮数部を A, Bとすると 1\leq A, B < 2なので、 A\geq Bなら結果は 1\leq A/B < 2となり、 A < Bなら 0.5 < A/B < 1となるのでAとBの大小が分かれば正規化でずれる量が確定し、指数部を決めることができます。
仮数部は24bitの精度で表現するため、丸めに必要な2bitを足して、26bitの精度で求めればよいです。

Newton-Raphson法

 f(x)=1/x-b という関数が f(x)=0を満たす  x を見つければ、 x=1/b となるので、 a/b = a\cdot(1/b)を使って割り算ができます。

Newton法  x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}を用いると、 f'(x) = -1/x^2より、 x_{i+1} = x_i - \frac{1/x_i-b}{-1/x_i^2}=x_i(2-x_ib)となります。1回の繰り返しのたびに正しい桁は2倍になります。

これを繰り返し適用することで逆数を求めて計算することができます。初期値は事前に用意したテーブルから使うようです。

Goldschmidt法

 a/b を計算するときに、 rb\sim 1となる rを用いて a/b = ra/rb \sim raとなることを用いる方法です。

アルゴリズム
1.  1\leq b < 2となるよう a, b に適当な数を掛ける
2. テーブルから b' \sim 1/bとなる b'を持ってくる
3.  x_0 = ab', y_0 = bb'とする
4.  r := 2-y, y := yr, x_{i+1} := x_{i}rという計算を十分な精度が出るまで繰り返す

となります。この繰り返しはパイプライン化しやすいです。4倍精度以上ではSRT法よりも繰り返しの回数が少なくなるので今後採用されることも多いと言われています。

演算器編はこれで終わりです。
次回からはCPU設計編に入るつもりですが、ここ数日の記事を見ても分かるように実装が全然追いついておらずこのまま進んでもあまり意味がないので明日の気分によってはしばらく更新を休止することにします。

参考文献

  • ヘネパタのAppendix J ついこの前までこの資料の存在を知らなかったのですが、とてもいい資料でこのAdvent Calendarのだいたい上位互換になっています。これだけ読めばいいんじゃないかな……