Zenn
Open4

浮動小数点数の文字列化（基数変換）

だめぽだめぽ

round tripする桁数

動機付け

計算機の内部では二進浮動小数点数が使われることが多い一方、プログラムのソースコードやテキストベースのデータ形式（例：JSON）では十進小数が使われることが多い。

データのシリアライズ等で、内部的な二進浮動小数点数を十進小数に変換して、再度二進小数に戻すという操作が考えられる。このとき、元々の二進小数の値が保持されることが望ましい。

有限桁の二進小数は原理的には有限桁の十進小数で表現できるが、指数部が大きかったり小さかったりすると仮数部の桁数も膨張するため実用的ではない。

そこで、基数変換の際に丸めが発生することを許容して、二進小数→十進小数→二進小数が恒等写像となるようにしたい。ただし丸めの方法は最近接丸めであるとする。この時、十進小数の仮数部は何桁が必要十分か？

結論

Matulaの論文によれば、\beta進n桁の浮動小数点数を\nu進m桁の浮動小数点数（いずれも指数部の範囲に制限は設けない）を経由して元の形式に戻す時に元の値と同一の値が得られる必要十分条件は、\nu^{m-1}>\beta^nである。ただし、\beta\ge 2, \nu\ge 2, n\ge 1, m\ge 1で、\betaと\nuはいかなるi, j>0についても\beta^i\ne\nu^jであるとする。

動機付けで書いた二進→十進→二進の場合は\beta=2, \nu=10である。倍精度（n=53）を十進に変換して元に戻るためには十進での桁数mが17以上であることが必要十分である（10^{15}<2^{53}<10^{16}なので）。

リンク

だめぽだめぽ

二進浮動小数点数を十進表記するアルゴリズム

解決したい問題

二進浮動小数点数を

  • （round tripするという意味で）情報の喪失が起きない範囲で
  • なるべく短い桁数で
  • 正しい丸めで

十進小数に変換したい。

Dragon4（1990年）

多倍長整数を使うらしい。

  • Guy L. Steele and Jon L. White. 1990. How to print floating-point numbers accurately. SIGPLAN Not. 25, 6 (Jun. 1990), 112–126. DOI:https://doi.org/10.1145/93548.93559
  • Guy L. Steele and Jon L. White. 1990. How to print floating-point numbers accurately. In Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation (PLDI '90). Association for Computing Machinery, New York, NY, USA, 112–126. DOI:https://doi.org/10.1145/93542.93559
    • ACMから無料でPDFをダウンロードできる。

論文としての発表は1990年だが、アルゴリズム自体は1970年代から1980年代にかけて構築・改良されていったらしい。

Grisu3（2010年）

固定長整数だけを使って二進十進変換を行う3つのアルゴリズムを提示する。

  1. 基本的なアルゴリズム（Grisu）
  2. より短い（しばしば最短）十進表示を得るアルゴリズム（Grisu2）
  3. 最短の十進表示を得る、失敗しうるアルゴリズム（Grisu3）

最後のやつが（失敗した場合は他のアルゴリズムを併用するという形で）よく利用されるようだ。

Grisuという名前の由来はドラゴンが登場するイタリアのTVアニメらしい。

Ryū（2018年）

固定長整数だけを使う。Grisu3と比べても高速。ルックアップテーブルを使う。

  • Ulf Adams. 2018. Ryū: fast float-to-string conversion. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). Association for Computing Machinery, New York, NY, USA, 270–282. DOI:https://doi.org/10.1145/3192366.3192369
  • Ulf Adams. 2018. Ryū: fast float-to-string conversion. SIGPLAN Not. 53, 4 (April 2018), 270–282. DOI:https://doi.org/10.1145/3296979.3192369
    • オープンアクセス。
だめぽだめぽ

Gay (1990)

  • Gay, D.M. (1990). Correctly Rounded Binary-Decimal and Decimal-Binary Conversions.

Burger & Dybvig (1996)

Dragon4に対して、指数部を計算するところを高速化する。

  • Robert G. Burger and R. Kent Dybvig. 1996. Printing floating-point numbers quickly and accurately. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation (PLDI '96). Association for Computing Machinery, New York, NY, USA, 108–116. DOI:https://doi.org/10.1145/231379.231397
  • Robert G. Burger and R. Kent Dybvig. 1996. Printing floating-point numbers quickly and accurately. SIGPLAN Not. 31, 5 (May 1996), 108–116. DOI:https://doi.org/10.1145/249069.231397
    • ACMから無料でPDFをダウンロードできる。

Errol (2016)

固定長演算だけを使う。double-double演算を使う。例外的なケースに対しルックアップテーブルを使う。Dragon4よりは速いがGrisu3よりは遅い。

  • Marc Andrysco, Ranjit Jhala, and Sorin Lerner. 2016. Printing floating-point numbers: a faster, always correct method. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '16). Association for Computing Machinery, New York, NY, USA, 555–567. DOI:https://doi.org/10.1145/2837614.2837654
  • Marc Andrysco, Ranjit Jhala, and Sorin Lerner. 2016. Printing floating-point numbers: a faster, always correct method. SIGPLAN Not. 51, 1 (January 2016), 555–567. DOI:https://doi.org/10.1145/2914770.2837654