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

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

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr"><a href="https://twitter.com/java">@Java</a> Puzzler:<br><br>int i = 0;<br>for (float f = 16384; f &lt; 16384 + 1; f += 1e-3f)<br>    i++;<br><br>What is i?</p>&mdash; Peter Lawrey (@PeterLawrey) <a href="https://twitter.com/PeterLawrey/status/824335093586100226">2017年1月25日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

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

# 解説を考えてみた

## floatとは
問題にfloatがあるのでfloatの仕組みを知る必要があります。まず見るのは当然ながら言語仕様です。
[4.2.3. Floating-Point Types, Formats, and Values](https://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.2.3)

> 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](http://msugai.fc2web.com/java/binary.html) ※

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

参考：Wikipediaの[IEEE 754 での単精度浮動小数点数の形式: binary32](https://ja.wikipedia.org/wiki/%E5%8D%98%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0#IEEE_754_.E3.81.A7.E3.81.AE.E5.8D.98.E7.B2.BE.E5.BA.A6.E6.B5.AE.E5.8B.95.E5.B0.8F.E6.95.B0.E7.82.B9.E6.95.B0.E3.81.AE.E5.BD.A2.E5.BC.8F:_binary32) ではそれが図解されています。

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

```java
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ドキュメント](https://docs.oracle.com/javase/8/docs/api/java/lang/Float.html#floatToRawIntBits-float-) にありますが、

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

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

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

### 16384f

これは、

|**s**|**e**|**m**|
|----:|----:|----:|
|0|10001101|00000000000000000000000|

なので、

```math
\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|

となり、

```math
\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** になります。