Edited at

【JavaScript】BigIntの上限


BigIntの紹介

JavaScriptで普通に使う数は53bitの精度しかない浮動小数点数なので、

Number.MAX_SAFE_INTEGERである$2^{53}-1$より大きい数は

計算結果が厳密には正しくならない場合があるので整数として扱うことができません。

でもいつの間にかBigIntなるものができていたようです。

書き方は簡単、数字の後ろにnとつけるだけです。

let bigint = 12345678901234567890n;

執筆時点(2019年4月17日〜18日)ではマークアップが不穏ですが、ちゃんと動きます。

Chromeでしか動作確認はしていませんが、

他にも使えるブラウザはあるかと思います。


Numberとの比較

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

let number = 12345678901234567890;

ですが、ダメなのです。

let number = 12345678901234567890;

console.log(number); // 12345678901234567000

このように、精度が足りないので、

値を正しく表現することができません。

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

let bigint = 12345678901234567890n;

console.log(bigint); // 12345678901234567890n

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


計算してみる

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

90071992547409922を足すと、いくつになるでしょうか?

console.log(9007199254740992+2);    // 9007199254740994

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

NumberBigIntも正しく計算できています。

では90071992547409921を足すとどうなるでしょう?

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の精度の壁を超えて整数を扱えるというわけです。

ちなみにBinIntNumberとはそのまま演算できないようで、

全然ビッグじゃない1とか2でも、1nとか2nと書く必要があります。


BigIntの上限は?

無限に大きい数まで扱える仕様になってるかもしれませんが、

メモリは有限なのでどこかに上限はあるはずです。

何かしらのドキュメントに書いてそうですが、

見つけられなかったので自分で調べてみます。

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


トリトリで試す

まずは、小さい巨大数を使って、

どれくらいの数がかけるのか試してみます。

小さい巨大数とは言っても、

ギネスブックに載ってるとかで有名なグラハム数はさすがに荷が重そうなので、

もう少し小さいトリトリと呼ばれる数で試してみましょう。

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

\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風に書くとこんな感じ。

3**3**3** ... **3 //7625597484987個の3

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

let tritri = 1n;

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

ダメでした。

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

では何回目のループでダメだったんでしょうか。

3**3**3Numberでも計算できるので、

その次から試してみましょう。

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

早速ダメでした。

$3^{3^{3^3}}$も表現できないようなら、

巨大数を扱うのにBigIntは使えませんね。残念です。


2の冪から上限を調べる

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

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

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

3の冪というのはコンピュータには辛いかもしれないので、

2の冪を使って上限を探ってみましょう。

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

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

何も考えずに、

let n = 0n;

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

みたいなのを書くと計算が終わる気配がなかったので、

ひと工夫したものがこちらになります。

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さんに聞いてみます。

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

$2^{30}-1$らしいです。

指数の$30$が、$31$や$32$に比べると微妙に中途半端な気がしますが、

まぁキリのいい数と言えますね。

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

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演算もできるようなので、

オーバーフローしない整数型としてなら、実用上問題なさそうです。

以上が私の調べた結果でした。

もしちゃんと上限をご存じの方がいれば、

教えてもらえると幸いです。