javascript でなぜ 2^53 - 1 以下の整数を正確に表せるのか

javascript の勉強をしていて疑問に思ったことについて調べたので書きます。冷静に考えるとかなり当たり前のことなのですが、同じ疑問を持つ人もいるかと思うのでメモを残しておきます。勘違いがあったら教えてください。

## jsでは数値はすべて浮動小数点型で表す

ほとんどのプログラミング言語では、整数と整数以外の実数を異なる型で表す（以下、面倒なので整数以外の実数を単に実数と表現する場合がある）。つまり、数値の中でも整数だけを特別に扱う型がある。例えば、Cでよく使うのは整数は`int`、実数は`double`などですね。これに対して、 javascript では整数だけを表す型というのがなく、数値はすべて`Number`という型で表現される。つまり、`3`も`0.3`も同じ型の値である。`Number`は実数を表すのによく使われる**64bit の浮動小数点型**なので、 javascript では整数も実数っぽく表していることになります。

## 浮動小数点型は正確に実数を表せない

一般に、計算機で実数を正確に表すことはできない。これは当然で、実数は無限にあるのに対して、計算機において有限の bit で表せる値の種類は有限だからである。例えば、 4bit で１つの数値を表すとすると、当然ながら $2^4$ 種類の値しか表現できない。bit を増やしても結局は有限種類の値しか表せないので、無限個ある実数に対応させるのは冷静に考えて無理という話になる。

その無理な中でも、できるだけ広い範囲の実数を計算機で誤差を少なく表現する方法として浮動小数点方式が使われている。浮動小数点については適当に[wikipedia](https://ja.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0)などを読めばわかると思いますが、実数を、

(仮数) × (基数)^(指数)

のように表現する。例えば $382.4$ を $3.824 x 10^2$ と表すみたいな感じです。

## 疑問

上で述べたように、浮動小数点型は正確な実数を表せない。例として、 javascript の適当な実行環境で`0.1 + 0.2`を計算すると以下のようになると思う。

```
> 0.1 + 0.2
0.30000000000000004
> 0.1 + 0.2 === 0.3
false
```

これは、 0.1 とか 0.2 という値は浮動小数点では正確に表すことができず、それを足し算することで誤差が見えてしまった例である。これは、普通の10進数で 1/3 (= 0.33333...) が正確に表せないのと同じ話です。

10進数の小数では、小数点以下第一位が 0.1 (= $10^{-1}$) が何個あるか、小数点以下第二位が 0.01 (= $10^{-2}$) が何個あるか...を表している。例えば、 0.826 は 0.1 が8個、 0.01 が2個、 0.001 が6個集まってできた数ということだ。このように、 0.826 は $10^{-m}$ の和で正確に表すことができるが、 1/3 (= 0.33333...) は 0.1 が3個、0.01が3個、 0.001が3個、0.0001が3個...というように、どれだけ桁を増やしても正確に表すことができない。

一方で、計算機で使われる2進数では、小数において小数点以下第一位が 0.5 (= $2^{-1}$) が何個あるか、小数点以下第二位が 0.25 (= $2^{-2}$) が何個あるか...を表す。例えば、10進法での 0.3125 (= 5/16) は、 1/4 + 1/16 (= $2^{-2} + 2^{-4}$)なので、2進法では 0.0101 になる。2進数でも、10進数の場合と同様に実数を正確に表せない場合があり、それが例えば上で例示した 0.1 とか 0.2 とかということになる。

ということで、浮動小数点型では一部の数を正確に表すことができないことがわかった。そうなってくると、javascriptでは 2 とか 3 とか 178943247 とかの整数も浮動小数点型なので、正確に表せない可能性があるのではないかと思えてくる。もしそうだとすると、例えば3回ループを回したいとき、

```javascript
for (let i = 0; i < 3; i++) {
  console.log(i)
}
```

みたいな`for`文を書くと思いますが、iが 3 となるべきところで 2.99999997 とかになったら４回ループすることになってめちゃくちゃ困ることになる。しかし、冷静に考えてみんなが山ほど使っている言語でそんな意味不明なことになっているはずがないので、 javascript でも整数は正確に表せているはずである。実際、ネットで少し検索してみると[javascriptでは正確に表せる保証のある整数の値の最大値`Number.MAX_SAFE_INTEGER`が存在し、それが 2^{53} - 1 である](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)ということがわかる。つまり、$2^{53} - 1$以下の整数は、浮動小数点型ですべて正確に表せるということだ。
しかし、 0.1 とか 0.2 は正確に表せないのに、なぜ同じ型の整数の 1 とか 2 とか 7829432667 とかはすべて正確に表せるのかわからない、ということで調べました。

## IEEE 754

まずは、 javascript の`Number`型が具体的にどうやって数値を表しているのかを整理する。javascriptでは、浮動小数点型のフォーマットとして、 [IEEE 754](https://ja.wikipedia.org/wiki/IEEE_754) を利用している。 IEEE 754 形式では、`Number`型の 64bit を

- 符号部（sign）：1 bit
- 指数部（exponent）：11 bit 
- 仮数部（fraction）：52 bit

のように使う。

![618px-IEEE_754_Double_Floating_Point_Format.svg.png](https://qiita-image-store.s3.amazonaws.com/0/159260/041d84da-8b63-b04b-7493-32f052186c23.png)

これらの値を使って、実数を

(-1)^(符号部) x (1+仮数部) × 2^(指数部‐1023)

のように表現する。ここで、基数を固定したとしても同じ数値を表す仮数部と指数部の組み合わせは複数ある（例えば 4 は $2 \times 2^1$ でもあるし $1 \times 2^2$ でもある）ので、数値の表現を一意にするために、仮数部は整数部分が1の小数の小数部分としている。また、指数部から1023が引かれているのは指数部が負の場合を表すためである。

具体的に適当な実数の IEEE 754 形式での表現を考えてみる。例えば、4.5は $+1.125 \times 4 = (-1)^0 \times (1+0.25) \times 2^{1025-1023}$ となるので、

- 符号部：0
- 指数部：1025
- 仮数部：0.125

となる。これらを2進数で表すと、

- 符号部：0
- 指数部：01000000001
- 仮数部：001000....

となる。ここで、指数部は整数ですが、仮数部は小数部分を表しているので、1bit 目が 1/2 、 2bit 目が 1/4 (= $2^{-2}$) 、 3bit 目が 1/8 (= $2^{-3}$)...を表していることに注意。

## 整数を浮動小数点で表す

次に、整数を IEEE 754 形式で表してみる。といっても、やることは小数を表すときと同じ。例えば、-7は $-1.75 \times 4 = (-1)^1 \times (1+0.75) \times 2^{1025-1023}$なので、

- 符号部：1
- 指数部：01000000001
- 仮数部：110000....

となる。手続きは小数の場合と同じなので、これだとなぜ小数は正確に表せない場合があるのに、整数は必ず正確に表せるのかわからない。

より一般的に考えてみる。以下、簡単のため整数は正であるとして符号部を無視します。一般に、整数は、 $2^m + k$ のように表せる（ただし、$0 <= k < 2^m$とする）。例えば、$34 = 2^5 + 2$ とか $15 = 2^3 + 7$ のような感じ。$0 <= k < 2^m$ という条件は、$34 = 2^4 + 18$ とか $34 = 2^6 - 30$ のような変な表し方をしないという意味です。 

$2^m + k$ を浮動小数点型として表そうと試みてみると、

$2^m + k = (1 + k \times 2^{-m}) \times 2^m$

となります。 IEEE 754 形式の定義と見比べてみると、仮数部は $k \times 2^{-m}$ ということになる。ここで、$k \times 2^{-m}$ は $2^{-m}$ の整数倍である。また、 $k < 2^m$ より $k \times 2^{-m}$ は1未満である（もちろん、仮数部なので1未満になってくれないと困る）。

つまり、一般に整数を浮動小数点型で表そうとすると、その仮数部は $2^{-m}$ の整数倍かつ1未満の数ということになる。ここで、例えば $2^{-m}$ の1倍の $2^{-m}$ ならば、仮数部は m 個目の bit のみが1で他の bit を0になり、**正確に表せる**（これは $2^{-1}$ が 10000...、 $2^{-2}$ が 01000...と**正確に表せる**ことを考えれば理解できる）。また、仮数部が $2 \times 2^{-m}$ ならば、 $2 \times 2^{-m} = 2^{-(m-1)}$ より、 (m-1) 個目の bit のみが1で他は0になる。 $3 \times 2^{-m}$ ならば、$3 \times 2^{-m} = 2^{-(m-1)} + 2^{-m}$より、 m 個目と (m-1) 個目の bit が1で他が0になって**正確に表せる**...。ということで、以上から考えればわかると思うのですが、**整数を浮動小数点型で表現するときに仮数部に現れる 「$2^{-m}$ の整数倍」という値は、仮数部の m 個目までのbitで正確に表すことができる**、ということになる。この整数倍の値がめちゃくちゃ大きくなってしまうと1を超えて桁あふれが起きてしまうのではないかという心配があるが、これは $k < 2^m$ より仮数部が1未満の数であることが保証されているので大丈夫。

以上が、整数も浮動小数点型で扱う javascript でも整数を正確に表すことができる理由である。これにより、実数の中には浮動小数点型で正確に表せる数と表せない数があるが、整数はすべて正確に表せる数になっているということだ。整数が正確に表せないのではないかという疑問は、「浮動小数点型 = 誤差がある」というなんとなくのイメージによる勘違いであることがわかった。

と言っても、整数も無限個あり、全ての整数が浮動小数点数で正確に表せるはずがないため、 javascript で正確に表すことができない整数も存在するはずである。上の議論から考えると、整数 $2^m + k$ は仮数部の m 番目の bit までを使うことで正確に表すことができる。 IEEE 754 形式では仮数部は全部で 52bit であった。そのため、 m = 53 になるとその整数を正確に表すための bit が足りなくなり、誤差が出てくる可能性があることがわかる。すなわち、 $2^{53}$ 以上の整数は javascript では正確に表せない可能性があるということだ。これが、一番最初に述べた、正確に表せる保証のある整数値の最大値である`Number.MAX_SAFE_INTEGER`が $2^{53} - 1$ であることの原因である。

## 他の説明

ネットで適当に検索しただけですが、以下の記事では同じような話題について大変わかりやすく解説してあります。どちらの記事にも正確に表せる整数の最大値の周辺でどういうことが起きるかという具体例があり良いです。

- http://2ality.com/2012/04/number-encoding.html
- https://note.mu/ruiu/n/ndd60f403e8f2

## まとめ

- javascript では数値を整数も含めてすべて 64bit の浮動小数点型で表す
- そうすると整数が正確に表せずに困るのではないかと思ったが、これは「浮動小数点型 = 誤差がある」というイメージによる勘違いで、浮動小数点型の仕組みを考えれば、一定の範囲内の整数はすべて正確に表すことができることがわかる