たまりば

パソコン・インターネット パソコン・インターネット三鷹市 三鷹市

浮動小数点数の10進指数表示のアルゴリズム
2016年12月28日 01:28

printfなどで浮動小数点数を10進指数表示するとき、倍精度では17桁の仮数で適切に出力すれば読み込んだ時元の値に戻ることが知られている。
この適切な出力アルゴリズムがどうなっているのか昔から気になっていた。

多倍長整数で1の位まで計算すれば明らかに正しい出力を出せるが、2進1024桁(10進308桁)だか何かそのレベルの桁数が必要になる。
最終的に17桁しか必要でないのに途中に308桁もの計算をするのはコストが大きく無駄に思える。他に方法が無いものだろうか。
log210nだかlog102nだかの表を(浮動小数点数で)持っておけば多数桁を保持すること無く10進指数表示ができそうだ。
しかしこれは表の値の精度に依存することになる。全ての値で正しい出力が出せるような気がしない。ちょうど丸めの境目あたりの数になった時に間違った出力にならないだろうか。

質問サイトに質問しても有用な回答が得られず悶々としていたのだが、先日偶然見つけたアルゴリズムの論文で疑問が氷解した。
Printing Floating-Point Numbers Quickly and Accurately with Integers
これによれば、
・1970年台~1980年台を通して多くのライブラリが誤った(wrong)表現を生成していた。
・Coonenが1980年と1984年の論文で拡張精度を使った正確(accurate)な手法を示したが広まらなかった。
 (拡張精度というとx87の80bit仮数のものが有名だ。8087の発売はちょうど1980年なのでこれを使ったのだろうか。)
・SteeleとWhiteの1990年の論文の多倍長整数を使うDragon4アルゴリズムが広まった。
という。

そしてこの論文で示されているアルゴリズムはGrisuという名で3種類あり、
・Grisu1は、入力の浮動小数点数の仮数の桁数より2bit以上多い整数を使い、正確な出力を返す。Coonenの手法の一般化。
・Grisu2は、正確かつGrisu1より短い出力を返す。
・Grisu3は、正確かつ最適(optimal)な出力を返すか、あるいはエラーを返す。

最適とはどういうことかというと、例えばGrisu1では、「0.3」(に相当するdouble)に対して「29999999999999998e-17」を出力する。(2.9999999999999998e-1って書き方のほうが馴染みがあるが本質に違いはない)
0.3と29999999999999998e-17はdoubleに変換した時同じ値になるので、どちらの表記も同じく正確である(accurate)。しかし、どうせなら短い「0.3」のほうで出してほしいと考えるのが自然だろう。
これはつまり、「同じ浮動小数点数に変換される10進表記が複数あるなら、仮数の桁数の少ない方を優先する」ということだ。加えて「同じ桁数なら、真の値に近い方を優先する」という条件も付けたものを最適(optimal)と呼んでいるようだ。

Grisu1のアルゴリズムだが、論文や実装「grisu.net」を見たところ特殊なことは何もやっていない。単純に、(入力より少し仮数の多い)自作の浮動小数点演算で適切な10の階乗を掛けてから10進変換しているだけのようだ。10の階乗の表を作るあたりの効率化に何かあるようだが、本質ではないので読んでいない。
これで正確な出力になる証明も、真面目に読んでいないが、たぶん地道に誤差の最大値を追っていっているだけだ。

Grisu3は、最適な出力を出せなければDragon4を使うというものだから、結局(あらゆる入力に対して)最適な出力を出すには多倍長整数演算を使わなければならないということになる。
テーブルメーカーのジレンマというやつだろうか。

以上より、冒頭の疑問に対する答えとしては、
・正確なだけでよければ仮数+2bitの精度の演算で単純なアルゴリズムで出力可能。1980年からある。
・最適も求めると多倍長整数を使うほかない(少なくとも2010年の時点では)。
ということになろう。
自分の直感はいい線をいっていたが、「正確だが最適でない」表記という考えが不足していた。