浮動小数点数の文字列化の調べごと

浮動小数点数の文字列化（基数変換） や 浮動小数点数の文字列化アルゴリズムSchubfach | Hiroshi Kurokawa’s site にあるように
(1) 2進→10進小数→2進で変換したときにもとの値が得られるように
(2) なるべく短い桁数で
(3) もちろん正確な丸めで
2進小数を10進小数表記に変換したい。
(1) は例えば浮動小数点数をJSON文字列にserializeして外部サーバーに送信し、受け取り側がそれをdeserializeしたときにもとの浮動小数点数を得られないと困るため

(2) は human readable はフォーマットで表示するため (?)変換したい。

tanishiking

In-and-out conversions | Communications of the ACM によると17桁もあれば情報の喪失なくもとに戻すことができるらしい。(証明とかは見てない)
ナイーブな方法としては research!rsc: Floating Point to Decimal Conversion is Easy にあるように frexp の結果に 2^53 をかけて mantissa 部を整数にもってきて文字列上で2^xをかける操作を繰り返すことで浮動小数点数を文字列化することができる。
そして2進数に情報の喪失なく戻すのに必要な17桁で打ち切ってあげれば良い。
しかしこのような方法だと、例えば 2.3 を小数点以下20で表示すると
package main

import (
	"fmt"
	"strconv"
)

func main() {
	fmt.Println(strconv.FormatFloat(2.3, 'g', 20, 64))
	// 2.2999999999999998224
}
https://go.dev/play/p/FKUPevv01pU
しかし 2.3 は "2.3" という文字列に変換しても一意にもとの値を得られるはず。
Just remember: The conversion is easy. The optimizations are hard.
と書いているが、難しいのは optimizations だけでなく、最も短い桁数の文字列を得ることでもある。
(第三引数 prec に -1 を渡すと ryu 実装になるっぽい)

tanishiking

ところで ECMAScript の spec でもこれらの、なるべく短い桁数の10進数表記を得ることを要件としているように見える(in step5)
Note1 では2進->10進->2進変換でもとに戻ることは必ずしも要件には入らないと書いているけど、実質的にそうなるように見える?

(10と2以外だとなんかあるのか?)

tanishiking

何故こんなことを調べているかというと Scala の Wasm バックエンドで使う ftoa/dtoa のアルゴリズムを検討している。
ScalaNative は [ryu] を使っている

https://github.com/scala-native/scala-native/blob/bb497a48be765b2f004f4c9176806f9cd9e3cb0d/javalib/src/main/scala/java/lang/Float.scala#L298-L303 が、できるだけ簡単でメンテナブルなアルゴリズムを採用したい。
一番古いのは Dragon4 というアルゴリズムだが、これは多倍長整数を使っている。もし Dragon4 を使うと Wasm バックエンドのランタイムコードが javalib に依存することになり、あまり好ましくない。できるだけ言語コアで完結したい。(parseFloat はそれ自体が javalib にあるので、BigInteger に依存するのはOK)
Grisu1/2/3 は integer だけで計算できるのが強みらしくて良さそうだが、一部ケースで失敗する?らしい。ちゃんと読んでない。その一部ケースでナイーブな実装にfallbackしても良いかもしれない?
Ryu とかはルックアップテーブルを使っていて、まあそれは良いんだけどできるだけシンプルな方が良いな〜