floatのパズルを解説してみた

パズル

先日こんなツイートが流れてきました。

@Java Puzzler:

int i = 0;
for (float f = 16384; f < 16384 + 1; f += 1e-3f)
i++;

What is i?

— Peter Lawrey (@PeterLawrey) 2017年1月25日

しばらく考えてみましたが、分かりませんでした・・・。
実行してみて答えを見てみましたが、なぜそうなるのかがぱっと見わかりませんでした。そこで。

解説を考えてみた

floatとは

問題にfloatがあるのでfloatの仕組みを知る必要があります。まず見るのは当然ながら言語仕様です。
4.2.3. Floating-Point Types, Formats, and Values

The floating-point types are float and double, which are conceptually associated with the single-precision 32-bit and double-precision 64-bit format IEEE 754 values and operations as specified in IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Standard 754-1985 (IEEE, New York).

IEEE 754に概念的に関連づけられている、つまり準拠しているとわかります。ではIEEE 754準拠とは何か。わかりやすいサイトがありました。
IEEE754 Floating Point Number ※

単精度のIEEE 754浮動小数点数は、符号ビット（1 ビット）、指数部（8 ビット）、仮数部（23 ビット）の 32 ビットで表現されます。

参考：WikipediaのIEEE 754 での単精度浮動小数点数の形式: binary32 ではそれが図解されています。

検証

さて、※のサイトを参考に Integer.toBinaryString(Float.floatToRawIntBits(floatValue)); というコードを使って検証してみます。

System.out.println("rawIntBits(16384f        )=" + Integer.toBinaryString(Float.floatToRawIntBits(16384f)));
System.out.println("rawIntBits(16384f + 1e-3f)=" + Integer.toBinaryString(Float.floatToRawIntBits(16384f + 1e-3f)));

これはどうなるでしょうか？
出力結果はこうなります。

rawIntBits(16384f        )=1000110100000000000000000000000
rawIntBits(16384f + 1e-3f)=1000110100000000000000000000001

ここで、文字は31文字しか出ていませんので、実際の表現は

rawIntBits(16384f        )=01000110100000000000000000000000
rawIntBits(16384f + 1e-3f)=01000110100000000000000000000001

であることに注意が必要です。（そう出力するようにコードを書けばよいだけですが）

さて、これが意味するところは何でしょうか？

APIドキュメント にありますが、

• 31ビット目：符号s(0がプラス、1がマイナス)
• 30-23ビット目：指数部e
• 22-0ビット目：仮数部m （※のサイトにあるとおり、最上位ビットが常に1となるため2ビット目以降の値)

です。s, e, m をそれぞれ使って、浮動小数を示します。

value = (-1)^s\times (1.m)_{2}\times 2^{e-127}

16384f

これは、

s	e	m
0	10001101	00000000000000000000000

なので、

\begin{align}
(-1)^0\times (1.00000000000000000000000)_{2}\times 2^{141-127} &= 1\times1\times2^{14} \\
&=16384
\end{align}

ということですね。

16384f + 1e-3f

同様に置くと、

s	e	m
0	10001101	00000000000000000000001

となり、

\begin{align}
(-1)^0\times (1.00000000000000000000001)_{2}\times 2^{141-127} &= 1\times (1+2^{-23}) \times 2^{14} \\
&= 1.00000011920928955078125 \times 16384 \\
&= 16384.001953125
\end{align}

話の核心

そう、つまり、1e-3=0.001 と考えると、クイズのループは、(16384 + 1 - 16384) ÷ 0.001=1000なので1000回回ることになり答えは1000になるはずです。ところが、上記で解説したとおり、16384+1e-3f=16384.001953125 ですから、1回のループで0.001よりも多く加算されてしまっています。ということは、1000回よりも少なくなります。

答え

1回のループで増分となった 0.001953125 は $2^{-9}$ です。つまり、クイズのfがループ終了条件に達するには $2^{9}$ 回のループが必要ということになります。

ということで、答えは 512 になります。