「Twitter住所特定実験」を開発中に気づいた事です。取得したツイートをサーバからJSONでクライアント側のJSに送る処理があって、当初この時にTwitterのツイートのIDをJSONに数値として含めて送っていました。
が、JavaScriptではこの値を受信してeval()した†1際、うまく変換することができず、たとえばChrome/Firefoxでは「76287755398823940」となり、微妙に異なった数値になってしまいました。
以下をクリックすることで、実際に実行できます。
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… * 2xxxxのように表す、つまり小数点より大きな部分は必ず1とするように指数を調整することができます(正規化)。
そこで、doubleでは最初の1を省略して残りの小数点以下の部分だけをここに記入しています。つまり、この仮数は、
1.0000111100000111010011110011000101000010010000000000
という二進数の小数を表している、ということになります。
最初の1ビットを省略してるので、実際に表現できる桁数が1ビット増えるんです。仮数部分が52ビットしかないのに、精度が52ビットでなく53ビットなのは、このためです。
■基数
先ほどだと10の何乗かをかけていましたが、doubleでは2の何乗をかけています。
■まとめ
以上をまとめると、doubleのデータは符号、仮数、指数の部分に分けられて、
(-1)符号 * 仮数 * 2指数
の値を示す、ということがわかりました。
■問題の値をdoubleに手動で変換してみよう。
問題の値は、
100001111000001110100111100110001010000100100000000000000
でした。これを実際に表して先ほどしめしたのと一致することを確かめましょう。まずは2進小数での表現になおします。10進数と同じ、小数点を移動させるだけですよ。
1.000011110000011101001111001100010100001001 * 256
ほら、こうすると最後の0が消えて43桁の二進数になったでしょう!だから53ビット精度で表せるはずです。
上の説明とにらめっこしながらパラメータを決めると…
符号:0(プラスだから)
指数:56+1023 = 1079(1023でバイアスします)
仮数:000011110000011101001111001100010100001001(二進数)
(小数点以下だけをdoubleには記入します;けち表現)
これを並べると…
0/10000110111/0000111100000111010011110011000101000010010000000000
元に戻りました!とりあえず、doubleでもちゃんと表現できるんだってこと、理解してもらえましたか?
■問題は入力側?出力側?
となると、これはブラウザのどこかでバグが起きてるということになります。
さて、問題の切り分けを行いましょう。この問題は、2つのうちのどちらかで起こってると思われます。
- 入力側(ソースコードに書かれた文字列をdoubleに変換する際に起こっている)
- 出力側(doubleを文字列に変換する際に起こっている)
で、切り分けるために実際に試してみたのがこれ。
割り算してみました。本当に内部の表現でも76287755398823940になってる(=入力側の問題)なら1024では割り切れないから何かしらの少数が出ると思われますし、もし実は内部表現は正しくなってる(=出力側の問題)なら、きっと桁数が減ってうまく表示できると思われます。
で、結果は「74499761131664」になったと思います。これは正しい結果です。
■Rubyでも起きる!
いつ書こうか悩みましたが、この問題はRubyでも発生します。
$ ruby1.9.1 -e "puts 76287755398823936.to_f" 76287755398823940.0
■次回に続きます
今から続きを書きますが、長くなりすぎたのでちょっと分割。とりあえずV8のissueに投げておきましたので、ゴミのような英語でも良いならそちらへ…。
■続きかけた
つづきです: