浮動小数点数の除算 - 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$ という計算を十分な精度が出るまで繰り返す