たまりば

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

浮動小数点数の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年の時点では)。
ということになろう。
自分の直感はいい線をいっていたが、「正確だが最適でない」表記という考えが不足していた。  

  • 【訂正・加筆】
    2016年12月06日 00:00

    2016/12/06 漢点字一覧表で、別の元データとの間で不一致があったので追記。
    2016/09/10 ネット契約を1Mbpsにしてみたの読み込み時間の記述が間違っていたので訂正。
    2016/09/04 ファミコンの縦解像度224px説の考察 左8pxを隠す機能の用途が思っていたのと違ったので追記。
    2016/06/06 Windows7でのペイントの劣化具合に新しく気づいたバグ情報を追加。
    2015/08/29 ベースラインPICの注意点で、型番の間違いを訂正、OPTION2の書き込み方法の間違いを訂正。
    2015/08/28 Windows7でのペイントの劣化具合に新しく気づいたバグ情報を追加。
    2013/09/26 5×5 ひらがなフォント5×5フォント改 / JavaScriptフォント表示機から5×5ドットフォント完成版に、思えばリンクを貼っていなかったのでリンク。
    2013/05/05 最弱のPICマイコンで電子オルガン_前編の単純ミスを1ヶ所修正。
    2013/04/27 文字コード表示機が特定の環境で動かない問題を修正、RTL文字での表示崩れを修正。
    2013/03/03 5×5ドットフォント完成版が紹介されていたので少々加筆しました。
    2012/11/18 ハロウィー?ンの正規表現に訂正・加筆があります。

    【このエントリについて】
    (2012/11/18)
    今まで、記事の内容にミスを見つけた場合はその記事だけ修正していたのですが、最新の記事はともかく古い記事にミスを見つけた場合は直しても気づかれないだろうと思って直すのが億劫になっていました。
    これではいけないと、どうするべきか考えた結果、訂正を知らせるエントリを1つ作ることにしました。
    記事を訂正した際にはこのエントリを更新して最上位に持ってくるように運用しようと思います。
    (2013/03/03)
    訂正だけに限らなかったので、エントリ名を【訂正】から【訂正・加筆】に変更しました。  
    タグ :お知らせ