【JavaScript】BigIntの上限

# BigIntの紹介

JavaScriptで普通に使う数は53bitの精度しかない浮動小数点数なので、
`Number.MAX_SAFE_INTEGER`である$2^{53}-1$より大きい数は
計算結果が厳密には正しくならない場合があるので整数として扱うことができません。

でもいつの間にか`BigInt`なるものができていたようです。
書き方は簡単、数字の後ろに`n`とつけるだけです。

```javascript
let bigint = 12345678901234567890n;
```

執筆時点（2019年4月17日〜18日）ではマークアップが不穏ですが、ちゃんと動きます。
Chromeでしか動作確認はしていませんが、
他にも使えるブラウザはあるかと思います。

## Numberとの比較

普通の`Number`でも同じことができると思うかもしれません。

```javascript
let number = 12345678901234567890;
```

ですが、ダメなのです。

```javascript
let number = 12345678901234567890;
console.log(number);  // 12345678901234567000
```

このように、精度が足りないので、
値を正しく表現することができません。

では`BigInt`ではどうでしょうか。

```javascript
let bigint = 12345678901234567890n;
console.log(bigint);  // 12345678901234567890n
```

こんな感じでちゃんと表現できるのです。

##計算してみる

じゃあちょっと簡単な足し算をしてみましょう。

`9007199254740992`に`2`を足すと、いくつになるでしょうか？

```javascript
console.log(9007199254740992+2);    // 9007199254740994
console.log(9007199254740992n+2n);  // 9007199254740994n
```

`Number`も`BigInt`も正しく計算できています。
では`9007199254740992`に`1`を足すとどうなるでしょう？

```javascript
console.log(9007199254740992+1);    // 9007199254740992
console.log(9007199254740992n+1n);  // 9007199254740993n
```

`Number`さんは正しく計算できていませんね。
これもやはりNumberは53bitの精度しかないため、
$2^{53}-1$より大きい$9007199254740992+1\left(=2^{53}+1\right)$という数を
扱うことができなかったのです。
さっき計算がたまたま正しかったのは、2進数を使ってる兼ね合いですね。

`BigInt`さんはこの53bitの精度の壁を超えて整数を扱えるというわけです。

ちなみに`BinInt`は`Number`とはそのまま演算できないようで、
全然ビッグじゃない1とか2でも、`1n`とか`2n`と書く必要があります。

#BigIntの上限は？

無限に大きい数まで扱える仕様になってるかもしれませんが、
メモリは有限なのでどこかに上限はあるはずです。

何かしらのドキュメントに書いてそうですが、
見つけられなかったので自分で調べてみます。

使用したChromeのバージョンは73.0.3683.103（Official Build） （64 ビット）でした。

##トリトリで試す

まずは、小さい巨大数を使って、
どれくらいの数がかけるのか試してみます。

小さい巨大数とは言っても、
ギネスブックに載ってるとかで有名なグラハム数はさすがに荷が重そうなので、
もう少し小さいトリトリと呼ばれる数で試してみましょう。

トリトリというのは、クヌースの矢印記法で、

```math
\begin{eqnarray} 
3\uparrow\uparrow\uparrow3&=&3\uparrow\uparrow3\uparrow\uparrow3\\
&=&3\uparrow\uparrow(3\uparrow\uparrow3)\\
&=&3\uparrow\uparrow(3\uparrow3\uparrow3)\\
&=&3\uparrow\uparrow\left(3^{3^3}\right)\\
&=&3\uparrow\uparrow7625597484987\\
&=&3\uparrow3\uparrow3\uparrow\dots\uparrow3\left(7625597484987個の3\right)
\end{eqnarray} 
```

と表される数です。
3の肩に3を書いて、書いた3の肩に3を書いて、というのを繰り返して、
3がちょうど7625597484987個になった時、それがトリトリです。

JavaScript風に書くとこんな感じ。

```javascript
3**3**3** ... **3 //7625597484987個の3
```

では早速計算してみましょう。

```javascript
let tritri = 1n;
for(let i=0; i<7625597484987; i++){
    tritri = 3n**tritri;  //RangeError: Maximum BigInt size exceeded
}
console.log(tritri);
```

ダメでした。
ちゃんと上限サイズがあるようです。

では何回目のループでダメだったんでしょうか。
`3**3**3`は`Number`でも計算できるので、
その次から試してみましょう。

```javascript
3n**3n**3n**3n //RangeError: Maximum BigInt size exceeded
```

早速ダメでした。
$3^{3^{3^3}}$も表現できないようなら、
巨大数を扱うのに`BigInt`は使えませんね。残念です。

##2の冪から上限を調べる

トリトリの失敗により、`BigInt`の上限$M$が、

```math
2^{53}+2\leq M \lt3^{3^{3^3}}
```

の範囲にあることが今のところわかっています。

3の冪というのはコンピュータには辛いかもしれないので、
2の冪を使って上限を探ってみましょう。

```math
2^N\leq M\lt2^{N+1}
```

を満たす整数$N$を探していきます。

何も考えずに、

```javascript
let n = 0n;
try{
    while(true){
        2n**n;
        n++;
    }
}catch(e){
    console.log(`2^${n-1} <= M < 2^${n}`);
}
```

みたいなのを書くと計算が終わる気配がなかったので、
ひと工夫したものがこちらになります。

```javascript
const f = n=>{
    let i = 0n;
    try{
        while(true){
            2n**(n+2n**i);
            i++;
        }
    }catch(e){
    }
    if(i===0n){
        return n;
    }
    return f(n+2n**(i-1n));
}
console.log(f(0n)); // 1073741823n

//45842.845947265625ms
```

一歩間違えると書類送検されかねない危険なスクリプトなので、
計算時間が30秒を超えた時にはヒヤリとしましたが結果は出ました。

1073741823。見慣れない数字のような気がしますが、
この数字は一体なんなのでしょう。
わからないときはとりあえずWolfram|Alphaさんに聞いてみます。

```math
1073741823\mbox{ has the representation }1073741823=2^{30}-1.
```

$2^{30}-1$らしいです。
指数の$30$が、$31$や$32$に比べると微妙に中途半端な気がしますが、
まぁキリのいい数と言えますね。

というわけで、`BigInt`の上限は、次の範囲にあることになります。

```math
2^{2^{30}-1}\leq M\lt2^{2^{30}}
```

これが仕様上の上限なのか、実装上の上限なのかはわかりませんが、
現状上限とみなしてもいいのではないでしょうか。

##で、結局上限は？

これ以上わかりませんでした。
というのも、先ほど作った$2^{2^{30}-1}$より大きい数を作ろうと、
さらに1を足してみたところ、計算が終わる気配がありませんでした。
2の冪が短時間で計算できたのは、たまたまだったのかもしれません。

上限が$2^{2^{30}-1}$だったとしても、
$2^{2^{30}}-1$だったとしても、
巨大数を扱えないという点では大した差ではありません。
どちらにせよ$10^{10^{10}}$より小さいので
やや有名な不可説不可説転$\left(\gt10^{10^{37}}\right)$すら
扱えないのですから話になりません。
というか巨大数を整数型で扱うのがそもそも間違っています。

`BigInt`という名前は付いているものの、
「JavaScriptにも整数型ができた！」くらいに思っておくのが吉でしょう。
128bitくらいなら普通に動きましたし、bit演算もできるようなので、
オーバーフローしない整数型としてなら、実用上問題なさそうです。

以上が私の調べた結果でした。
もしちゃんと上限をご存じの方がいれば、
教えてもらえると幸いです。