「なぜJavaScriptで「76287755398823936」が正しく表示できないか、あるいはなぜRubyでも表せないか。」の続きです。後半戦、テンションあげてまいりましょー（涙目

■出力側ソースコードのチェック！

　さて…では重い腰を上げてソースコードを読みましょうか…。　FirefoxでもChromeでも起きるなら、何かWindowsのライブラリのバグ…なんでしょうか。ま、いいや。とりあえずソースコードが探しやすそうなChromeから見てみましょう。

　それっぽいメソッドを探していくと…見つかりました。これですね。v8::internal::Grisu3()です。…あれ…？標準ライブラリじゃ…ない…！？うげぇめんどくさい…

　v8をWindows上でコンパイルするのはひたすら☆面倒†1なので、Ubuntu上でコンパイルしてCodeLiteというIDEをGDBのGUIラッパーとして使いました。これ、初めてだったんですが結構便利。Windowsでも使えるならちょっと試してみようかなってレベルです。EclipseCDTとは何だったのか。あとDDDとxxgdbはクソ。

■原因は、やっぱり精度の問題（

　これも、実はやっぱりというか結局というか、doubleの精度の問題です（

　この問題の値をintegerからdoubleに一意に表現することができるのですが、doubleからintegerには必ずしも一意に変換はできない、ということです。

■何もかもを忘れてさっきのdoubleの表現から元の値を読みだそうとしてみる

　これをやるとどうしてなのかわかります。

0/10000110111/0000111100000111010011110011000101000010010000000000

　今までの事は一切わすれて。この値、いったい何なんでしょうね？早速IEEE754に基づいて分析してみよう！（投げやりな態度で）

　ふむふむ…符号は0だから、プラスの数みたいですね。

　指数は1079だから…1023でバイアスされてるから本当は1079-1023＝56なんですね。メモメモ。

　仮数は0b0000111100000111010011110011000101000010010000000000だから、二進の小数で

1.0000111100000111010011110011000101000010010000000000（53桁）

　なんですねですね。へー。

　それで、このdoubleが示す値は

　(-1)^符号 * 仮数 * 2^指数

　で表現されるから…

＋1.0000111100000111010011110011000101000010010000000000 * 2⁵⁶

＝10000111100000111010011110011000101000010010000000000xxx

　…ん？xxx？？

■「1」と「1.00」は全然違う！

　高校や大学の時に、物理の時間とかで、定規で測った値を「1cm」とかって書いたら怒られませんでした？「この定規、ミリの目盛りまであるじゃん。1cmぴったりだったんなら、1.0cmって書かないとだめだよ！」とかって言われた記憶、ありません…？†2

　今回もそれと根っこは同じことです。「x=1」と書いたら数学的には「x=1.000000000000000000….」だけど、物理学的にはそうではなく「0.5 <= x < 1.5」のあいだであるのと同じ。

　今回の例で言えば、

1.0000111100000111010011110011000101000010010000000000

の”本当の値”は

1.00001111000001110100111100110001010000100011111111111以上、

1.00001111000001110100111100110001010000100100000000001未満

　の間にある！って事です（逆に言えば、これらの値をdoubleにすると皆同じdoubleの表現に落ちる、ということです）。これをそれぞれさっきのに代入すると…

＋1.00001111000001110100111100110001010000100011111111111 * 2⁵⁶

＝76287755398823928

＋1.00001111000001110100111100110001010000100100000000001 * 2⁵⁶

＝76287755398823944

　ほう…そう来ましたか…

とうわけで、このdoubleが示すxは、

「6287755398823928 <= x < 76287755398823944」

なんですね。そう、やっぱり「76287755398823936」には決まりませんでした。

　この時、62877553988239**という桁までは確定、その次の桁は2か3か4、最後の下一桁はさっぱり☆わからない、というわけですが、stringに変換する際はどれかには決めないといけません。この時に最後を40（上側）とするのがChrome/（とたぶんFirefoxとRuby）、30（真ん中）に多分するのがIE8/9、ということになります。でもIEの挙動はなんか標準じゃ無いっぽい…？

　IEEE754での標準の丸めモードは「最近接丸め（偶数）：最も近くの表現できる値へ丸める。表現可能な2つの値の中間の値であったら、一番低い仮数ビットが0になるほうを採用する。」との事なので、切り捨てられがちになるから上の方の値を採用してるって事なんでしょうかね、たぶん。

　ちなみに、この解説した部分がissueで示した、v8::internal::Grisu3のboundary_minusとboundary_plusを計算する部分です。V8では、boundary_plusの方から文字列を作っているので、ソースを読みたい場合はboundary_plusに着目していってみてください。

　あとこの実装の理論的詳細はこちら「Florian Loitschの論文”Printing floating-point numbers quickly and accurately with integers”」にあるそうです。

■もっと単純に表現すると

　「76287755398823936=0b100001111000001110100111100110001010000100100000000000000」は最後の0まで意味があるので、43ビット精度の数ではなくてやっぱり57ビット精度の数です。

　つまり、64ビットの浮動小数点の精度53ビットでは足りないので、うまく表現することはできません。

■でも「76287755398823936」って出てほしい！！

　1cmって書いたら1.0ｃｍだし1.00cmだって言いたくなるのも人情（たぶん）。そう表現したい場合は、

javascript:alert((76287755398823936).toFixed(0))

　ってやってみてください。詳しい仕様はこちら！そして今までの、ToStringをnumberに適用した場合の仕様はこちら。

■まとめ

• JavaScriptで整数を扱うときは53ビット整数までにしよう（あれ…？普通だ…？）
• 浮動小数点は結構厄介。でもたまに見る分には面白いね！

■早速v8のissueに回答もらった

　はやい！ありがとう！

Precise representation of this number requires 57 bits not 43.

When formatting a string representation of double we are free to choose any string that when parsed back would give the same double number. Simply speaking only the following must hold:

parseFloat(d.toString()) == d

In this case both 76287755398823940 and 76287755398823936 map to the same double number and we can use either of them when printing the result back.

You can use d.toFixed(0) to uses different formatting algorithm for numbers less than 10^21. This algorithm will render double with mantisa m and positive exponent p exactly as integer m*2^p. In you case it means that

(76287755398823936).toFixed(0) === “76287755398823936”

For more information please read:

ECMA-262 5th 9.8.1 ToString Applied to the Number Type. http://es5.github.com/#x9.8.1

ECMA-262 5th 15.7.4.5 Number.prototype.toFixed (fractionDigits) http://es5.github.com/#x15.7.4.5

Details about the algorithm used by V8 are available in Florian Loitsch’s paper “Printing Floating-Point Numbers Quickly and Accurately with Integers”.

　こんなに詳しく教えてもらえるなんてほんとありがたいです…。しかしそれに対する私の返答はひどすぎ…。こういうのあるともっと英語を知らないとな！って思います…。

• †1: SConsっていうビルドツールとかが必要。
• †2: 多分理系じゃないと無いとおもうケド。

　「Twitter住所特定実験」を開発中に気づいた事です。取得したツイートをサーバからJSONでクライアント側のJSに送る処理があって、当初この時にTwitterのツイートのIDをJSONに数値として含めて送っていました。

　が、JavaScriptではこの値を受信してeval()した†1際、うまく変換することができず、たとえばChrome/Firefoxでは「76287755398823940」となり、微妙に異なった数値になってしまいました。

　以下をクリックすることで、実際に実行できます。

javascript:alert(76287755398823936)

　IE8/9だと「76287755398823930」となり、まだ微妙に違った値になります。

■doubleの精度の問題？？

　まず疑われたのはdoubleの精度の問題。一部では有名な話で、JavaScriptでは数値はすべてdoubleで持っています。doubleは64ビットの浮動小数点なので、64bit整数より若干精度が落ち（具体的には53ビットしか精度がありません）、かなり大きな（64bit整数の限界に近いような値は）うまく表現することができません。

　で、実際に実験してみると…。

$ cat test.asm
global  _main
extern  _printf
section .text
_main:
;問題の値を読み込む
push 0x010f074f
push 0x31424000
fild qword [esp]
;64ビット浮動小数点としてスタックに保存←おそらくここで下位ビットが失われる
fstp qword [esp]
;表示
push    messagef
call    _printf
add     esp, 12
ret
messagef:
db      "%f", 0x0a, 0
$ nasm -fwin32 test.asm
$ gcc -o test.exe test.obj
$ ./test.exe
76287755398823936.000000

…あれれ！？せっかくアセンブラまで書いたのに

■実は余裕でdoubleで表せる

　Doubleの精度は53ビットまでですが、この「76287755398823936」という値は43ビットの精度があれば表すことができます。この値を2進数で表すと、

100001111000001110100111100110001010000100100000000000000（57ビット）

　となります。これは57ビットありますが、doubleで十分表すことができます。えっdoubleって53ビットまでってさっき言ったじゃん？

　それについて詳しく納得していくために、doubleの仕組みを見ていきましょう。

　doubleはIEEE754に基づく浮動小数点で…。能書きはいいさね、実物を見ながら解説します。

　問題の値のdoubleでの表現は次の通りです。

0/10000110111/0000111100000111010011110011000101000010010000000000

　スラッシュで区切った三つの構造からできています：左から符号、指数、仮数。

　浮動小数点では、理系の本でよく見るような値の表現をします。つまり、

+4.2195 * 10³m

　みたいな感じですね。42195mじゃなくて、+4.2195 * 10³mです。

■符号（0）

　先ほどの例で言うと、「+」のところを現しています。

　1ビットの値で、0ならプラス、1ならマイナスの値で有ることを示します。

■指数（10000110111）

　先程の例で言えば、「³」の部分にあたります。

　11ビットの値で、仮数で表される値が2の何乗されるかを表します。ただし、この値は本当の値より1023大きく表現されています。^-2（マイナス二乗）のように小さな値を示す場合に困らないようにするための表現です†2。これをバイアスする、と言います。

■仮数（0000111100000111010011110011000101000010010000000000）

　残りの52ビットの値です。先程の（略）、「4.2195」に対応します。

　doubleでは10進数の小数ではなく、二進数の小数を表します。

　よって、値は必ず1.01011110… * 2^xxxxのように表す、つまり小数点より大きな部分は必ず1とするように指数を調整することができます（正規化）。

　そこで、doubleでは最初の1を省略して残りの小数点以下の部分だけをここに記入しています。つまり、この仮数は、

1.0000111100000111010011110011000101000010010000000000

　という二進数の小数を表している、ということになります。

　最初の1ビットを省略してるので、実際に表現できる桁数が1ビット増えるんです。仮数部分が52ビットしかないのに、精度が52ビットでなく53ビットなのは、このためです。

■基数

　先ほどだと10の何乗かをかけていましたが、doubleでは2の何乗をかけています。

■まとめ

　以上をまとめると、doubleのデータは符号、仮数、指数の部分に分けられて、

　(-1)^符号 * 仮数 * 2^指数

　の値を示す、ということがわかりました。

■問題の値をdoubleに手動で変換してみよう。

　問題の値は、

100001111000001110100111100110001010000100100000000000000

でした。これを実際に表して先ほどしめしたのと一致することを確かめましょう。まずは2進小数での表現になおします。10進数と同じ、小数点を移動させるだけですよ。

1.000011110000011101001111001100010100001001 * 2⁵⁶

　ほら、こうすると最後の0が消えて43桁の二進数になったでしょう！だから53ビット精度で表せるはずです。

　上の説明とにらめっこしながらパラメータを決めると…

符号：0（プラスだから）

指数：56+1023 = 1079（1023でバイアスします）

仮数：000011110000011101001111001100010100001001（二進数）

（小数点以下だけをdoubleには記入します；けち表現）

これを並べると…

0/10000110111/0000111100000111010011110011000101000010010000000000

　元に戻りました！とりあえず、doubleでもちゃんと表現できるんだってこと、理解してもらえましたか？

■問題は入力側？出力側？

　となると、これはブラウザのどこかでバグが起きてるということになります。

　さて、問題の切り分けを行いましょう。この問題は、2つのうちのどちらかで起こってると思われます。

• 入力側（ソースコードに書かれた文字列をdoubleに変換する際に起こっている）
• 出力側（doubleを文字列に変換する際に起こっている）

　で、切り分けるために実際に試してみたのがこれ。

javascript:alert(76287755398823936/1024)

　割り算してみました。本当に内部の表現でも76287755398823940になってる（＝入力側の問題）なら1024では割り切れないから何かしらの少数が出ると思われますし、もし実は内部表現は正しくなってる（＝出力側の問題）なら、きっと桁数が減ってうまく表示できると思われます。

　で、結果は「74499761131664」になったと思います。これは正しい結果です。

■Rubyでも起きる！

　いつ書こうか悩みましたが、この問題はRubyでも発生します。

$ ruby1.9.1 -e "puts 76287755398823936.to_f"
76287755398823940.0

■次回に続きます

　今から続きを書きますが、長くなりすぎたのでちょっと分割。とりあえずV8のissueに投げておきましたので、ゴミのような英語でも良いならそちらへ…。

■続きかけた

　つづきです：

やっぱりdoubleでは「76287755398823936」は表現できない

• †1: といいつつprototype.js頼りですが
• †2: 補数表現じゃだめだったんだろうか？

　引っかかってしまって悩んだので備忘録的に書いておきます。

■

　SVNでは、一切設定をしていなくても特定の拡張子をデフォルトで無視するようになっています。

　設定ファイル（UNIXでは~/.subversion/.config、windows版ではC:\Users\<ユーザ名>\AppData\Roaming\Subversion\config）内では、一切設定していない場合このようになっています。

# global-ignores = *.o *.lo *.la *.al .libs *.so *.so.[0-9]* *.a *.pyc *.pyo
#   *.rej *~ #*# .#* .*.swp .DS_Store

　これを読む限りだとコメントアウトされてるから無視されなさそうな感じがしますが、実は無視されます。（設定例を示すのではなく、デフォルト値を示すコメントみたいで…。）

$ touch test.a
$ svn st
$ svn st --no-ignore
I       test.a

　明示的にこれらを共有したい場合は、svn addに–no-ignoreを設定するか、上記の設定ファイルをコメントアウトして無視設定を外すなど工夫が必要です。

# こうすれば無視しなくなる
global-ignores =

$ svn add --no-ignore test.a
A         test.a

■

　現在ノートPCとデスクトップPCでSVNを使って開発環境を共有してるのですが、この仕様でひどく苦労しました…。Bazaarに移行しようかな、やっぱり…。