はじめに
CodeIQ のバナー広告として表示されるこの問題に挑戦してみた。
実際にこのコードを
var i = 0;
var cnt = 0;
while(i < 1){
cnt ++;
i += 0.1;
}
console.log(cnt);
JavaScript の実行環境に入力し動作させ、何が出力されるかを確認することは容易ではあるが、「なんかわからんけど動かしたら ～という結果になった」というだけではプログラマ失格である。「これこれこうだから ～という結果になる」と論理的に説明できなければ問題について正確に理解し回答したとは言えない。
本稿では、回答まで書いてしまうと CodeIQ から怒られる気がするので、そこまでには至らない、途中までのところに留めておく。
JavaScript の実数の表現方法
JavaScript は現在の規格では実数は IEEE 754-2008 規格の double-precision 64-bit binary format で表現する。
IEEE 754-2008 規格を参照するのは面倒であるので、手軽な資料として、Wikipedia の IEEE 754 の項目を参照されることをおススメする。
IEEE 754-2008 規格の double-precision 64-bit binary format とは要するに
符号 * 2**指数部 * 仮数部
# 2**n は 2 のべき乗
の書式で表せられる浮動小数点形式であり、非正規数、+0 と -0、+∞ と -∞ の特別な場合を除き
- 符号: +1 か -1
- 指数部: -1022 ～ +1023
- 仮数部: 整数部は 1 に固定、小数部 52ビットの 1.0 以上 2.0 未満の固定小数点数
で表せられる。
本稿では、演算誤差も正確に考慮する関係で、仮数部については IEEE 754 規格では本来省略される整数部や小数部末尾の 0 を含めて 53桁の 2進数で表記することとする。例えば、3.5 という値はこの表記では
+1 * 2**1 * 1.1100000000000000000000000000000000000000000000000000
となる。
0.1 はどのような値として扱われるか
0.1 を 2進数で表すと 0.0001100110011001100110011001100110011001100110011001100110011001100... という循環小数となる。これを浮動小数点形式で表すと
+1 * 2**-4 * 1.100110011001100110011001100110011001100110011001100110011001100...
ということになるが、IEEE 754-2008 規格の double-precision 64-bit binary format では仮数部の精度が 53ビットと決まっているので、上位の 53ビットより下のビットは捨てられる。
+1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011001(これより下は捨てられる)10011001100...
上位の 53ビットより下のビットが捨てられる際に最近接偶数への丸めが行われ、結果として
+1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
となる。
この値を 10進数で表すと 0.1000000000000000055511151231257827021181583404541015625 となる。本来表現したい 0.1 よりわずかに大きいことに留意すべきである。JavaScript は数値リテラルとしては 0.1 という値を正確に表すことはできない。
プログラムの机上トレース
以上を踏まえた上で、『JSちゃんからの問題』を机上にてトレースする。
初期化
var i = 0;
var cnt = 0;
- 変数 i を 0 で初期化する
- 変数 cnt を 0 で初期化する
繰り返し 1回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 1 となる
- 変数 i に値 0.1 が加算される。加算前の変数 i の値が 0 なので 0.1(+1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010 = 0.1000000000000000055511151231257827021181583404541015625) はそのまま代入される
繰り返し 2回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.1000000000000000055511151231257827021181583404541015625 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 2 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
+1 * 2**-4 * 11.0011001100110011001100110011001100110011001100110100
という計算になるが、加算結果の仮数部が 2.0 以上なので正規化が行われる。具体的には、指数部が +1 され、仮数部全体が右に 1ビットシフトし、捨てられるビットに従い仮数部への最近接偶数への丸めが行われ、結果として
+1 * 2**-3 * 1.1001100110011001100110011001100110011001100110011010
となる。この値を 10進数で表すと 0.200000000000000011102230246251565404236316680908203125 ということとなる。
繰り返し 3回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.200000000000000011102230246251565404236316680908203125 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 3 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-3 * 1.1001100110011001100110011001100110011001100110011010
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。
+1 * 2**-3 * 1.1001100110011001100110011001100110011001100110011010
+) +1 * 2**-3 * 0.1100110011001100110011001100110011001100110011001101
-----------------------------------------------------------------------
+1 * 2**-3 * 10.0110011001100110011001100110011001100110011001100111
加算結果の仮数部が 2.0 以上なので正規化が行われ、結果として
+1 * 2**-2 * 1.0011001100110011001100110011001100110011001100110100
となる。この値を 10進数で表すと 0.3000000000000000444089209850062616169452667236328125 ということとなる。
繰り返し 4回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.3000000000000000444089209850062616169452667236328125 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 4 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-2 * 1.0011001100110011001100110011001100110011001100110100
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われ、
+1 * 2**-2 * 1.0011001100110011001100110011001100110011001100110100
+) +1 * 2**-2 * 0.0110011001100110011001100110011001100110011001100110
-----------------------------------------------------------------------
+1 * 2**-2 * 1.1001100110011001100110011001100110011001100110011010
となる。この値を 10進数で表すと 0.40000000000000002220446049250313080847263336181640625 ということとなる。
繰り返し 5回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.40000000000000002220446049250313080847263336181640625 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 5 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-2 * 1.1001100110011001100110011001100110011001100110011010
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。
+1 * 2**-2 * 1.1001100110011001100110011001100110011001100110011010
+) +1 * 2**-2 * 0.0110011001100110011001100110011001100110011001100110
-----------------------------------------------------------------------
+1 * 2**-2 * 10.0000000000000000000000000000000000000000000000000000
加算結果の仮数部が 2.0 以上なので正規化が行われ、結果
+1 * 2**-1 * 1.0000000000000000000000000000000000000000000000000000
となる。この値を 10進数で表すと 0.5 ということとなる。
繰り返し 6回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.5 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 6 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.0000000000000000000000000000000000000000000000000000
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われ、結果
+1 * 2**-1 * 1.0000000000000000000000000000000000000000000000000000
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 1.0011001100110011001100110011001100110011001100110011
となる。この値を 10進数で表すと 0.59999999999999997779553950749686919152736663818359375 ということとなる。
繰り返し 7回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.59999999999999997779553950749686919152736663818359375 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 7 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.0011001100110011001100110011001100110011001100110011
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。結果
+1 * 2**-1 * 1.0011001100110011001100110011001100110011001100110011
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 1.0110011001100110011001100110011001100110011001100110
となる。この値を 10進数で表すと 0.6999999999999999555910790149937383830547332763671875 ということとなる。
繰り返し 8回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.6999999999999999555910790149937383830547332763671875 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 8 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.0110011001100110011001100110011001100110011001100110
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。結果
+1 * 2**-1 * 1.0110011001100110011001100110011001100110011001100110
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 1.1001100110011001100110011001100110011001100110011001
となる。この値を 10進数で表すと 0.79999999999999993338661852249060757458209991455078125 ということとなる。
繰り返し 9回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.79999999999999993338661852249060757458209991455078125 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 9 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.1001100110011001100110011001100110011001100110011001
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。結果
+1 * 2**-1 * 1.1001100110011001100110011001100110011001100110011001
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 1.1100110011001100110011001100110011001100110011001100
となる。この値を 10進数で表すと 0.899999999999999911182158029987476766109466552734375 ということとなる。
繰り返し 10回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.899999999999999911182158029987476766109466552734375 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 10 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.1100110011001100110011001100110011001100110011001100
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。結果
+1 * 2**-1 * 1.1100110011001100110011001100110011001100110011001100
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 1.1111111111111111111111111111111111111111111111111111
となる。この値を 10進数で表すと 0.99999999999999988897769753748434595763683319091796875 ということとなる。
繰り返し 11回目
while(i < 1){
cnt ++;
i += 0.1;
}
- while 文の式 i < 1 について、変数 i の値が 0.99999999999999988897769753748434595763683319091796875 なので式の値が true となるため以下のブロックの内容が実行される
- 変数 cnt の値がインクリメントされ 11 となる
- 変数 i に値 0.1 が加算される。
+1 * 2**-1 * 1.1111111111111111111111111111111111111111111111111111
+) +1 * 2**-4 * 1.1001100110011001100110011001100110011001100110011010
-----------------------------------------------------------------------
という計算になるが、被加算数と加算数の指数部の値が異なるので大きい方に合わせられる。その際に仮数部の捨てれらるビットの内容に従い最近接偶数への丸めが行われる。
+1 * 2**-1 * 1.1111111111111111111111111111111111111111111111111111
+) +1 * 2**-1 * 0.0011001100110011001100110011001100110011001100110011
-----------------------------------------------------------------------
+1 * 2**-1 * 10.0011001100110011001100110011001100110011001100110010
結果の仮数部が 2.0 以上なので正規化が行われ、
+1 * 2**0 * 1.0001100110011001100110011001100110011001100110011001
という結果となる。この値を 10進数で表すと 1.0999999999999998667732370449812151491641998291015625 ということとなる。
繰り返し 12回目
だいぶ回答に近いところまで来たので以下略とする。
おわりに
初心者向けの問題と思ったら意外と手こずった。難易度的には難しいものではないが回答に至るまでには労力的に大変であり、このような問題を出す CodeIQ は鬼だな。