Daily Julia #1

Julia にもっと近づきたいという気持ちが出てきたので ML や master の開発周りを眺めながら話題をメモってみる。自分にはちょっと流速が速すぎるので見落としは多くまるで網羅的じゃないですが 、内容より更新速度重視ということでやっていきます。

Grisu アルゴリズムの実装 #7291

WIP: Grisu by quinnj · Pull Request #7291 · JuliaLang/julia

WIP ではあるが、浮動小数点数を正しく高速に 10 進変換する Grisu アルゴリズムというものが実装された。大量のテストコードが追加されており気魄が感じられる。

Grisu at Avik’s Ruminations

Grisu というか浮動小数点数周りがよくわからないので、リンク先を読み下しながら知識を整理してみる。

復習: 浮動小数点数は符号と指数部と仮数部のビット列から成り立っている。例えば 64 ビットのマシンでの Float は指数部 11 ビット、仮数部 52 ビット、符号 1 ビットからなる。

浮動小数点数を画面に表示したり、文字列に変換したりするとき、ビット列で表現された浮動小数点数を 10 進表現に直す必要がある。ここで注意しなければいけないのは、2進表現された浮動小数点数では表現しきれない10進小数があるということだ。Julia は Float16 が使えるのでそれを用いて丸め誤差が起こっていることを簡単に観察できる。

julia> float16(0.1)
float16(0.099976)

これは有限精度のコンピュータを使っている以上避けられないことではあるのだが、それでは困ることもあるので(どう困るのかよいシチュエーションが思い浮かばないが、まあいろいろ困るだろう)、正確に 10 進変換するアルゴリズムが必要とされたのであろう。正確な 10 進変換が満たすべき性質は次のように書ける。

read( show(d) ) == d

つまり変換と逆変換を行って元の数に戻るような 2 つの関数が欲しいのだ。

こうした浮動小数点数から 10 進数への変換に関する研究は 1990 年の How to print floating-point numbers accurately がよく知られている。この論文で発表されたアルゴリズムは Dragon4 という。なんだそのかっこいいネーミング。

Dragon4 は高速なアルゴリズムであり netlibdtoa.c に取り込まれ広く使われていた。だが、実装には任意長精度の数値型を必要とし (いわゆる bignum)、そのために実用上の速度は遅くコードも長くて複雑になるという問題があった。

Dragon4 の高速な代替として提案されたのが Grisu である。これは 2010 年に考案された。

【PDF注意】 Printing floating-point numbers quickly and accurately with integers

Grisu は任意精度計算をせず Int64 しか使わないので高速である。ただし欠点もあり、浮動小数点数全体の 0.5 % に対して正確な計算がうまくできないことがあるとのことだ。失敗した計算をフォローするとパフォーマンスが落ちるとの由。

Grisu が現実世界のどこで使われているのかというと、JavaScript の V8 エンジンに取り込まれていることで有名であったらしい (実際には double-conversion という独立なプロジェクト)。

Julia ではこれまでマクロによって C++ の実装を叩いていただけであったが、このたび pure Julia による実装が書かれたということで実にめでたいというお話でした。

関連

Implement proper print_shortest for Float16 · Issue #5959 · JuliaLang/julia

Port of Double-Conversion library to native Julia

quinnj/Grisu.jl

Dates.jl が Base にマージされた #7285

Merge Dates.jl package into Base by quinnj · Pull Request #7285 · JuliaLang/julia

Datetime.jl もあるようだが関係性がよく分からない。

quinnj/Dates.jl

quinnj/Datetime.jl