JavascriptのBigIntの限界値を探る

アルゴリズム
スポンサーリンク
スポンサーリンク

JavascriptのBigIntの限界値はいくつなのか?どうやって探れば良いのか?を解説する。

JavascriptのBigIntの限界値

いきなり結論、JavascriptのBigIntには、明確な限界値(最大値)は定義されておらず、利用するブラウザ(Javascriptエンジン)の作り(実装)や、利用するPCのマシンスペック(主にメモリ容量)に依存する、「環境依存」となる。

ブラウザ別のBigIntの限界値は次となる。
(注)1の位まで正確には求めてません。

  • Firefox(97.0)
    10315,645 (10の約31.6万乗)、21,048,575 (1Mbit)
  • Edge(Chromium版:98.0.1108.43)
    10323,228,483 (10の約3.2億乗)、21,073,741,823 (1Gbit)
  • Chrome(98.0.4758.102) (2022-02-26追記)
    未実施だが、Edge(Chromium版)とJavascriptエンジンが同じV8エンジンのため、同じ結果となると推測する。
    10323,228,483(10の約3.2億乗)、21,073,741,823(1Gbit)

8bit=1Byteのため、1Gbit(ギガビット)は128MB(メガバイト)となる。
1つの数値に128MBのメモリが必要となるため、利用するPCに搭載されたメモリ容量にも依存してしまう。
しかも、目視するためにビットパターン(2進数の文字列)に変換しようとすると、値の1bitあたり’0’または’1’の1バイト文字を必要とするので、1Gbit(2進数約10億桁)のビットパターンを表すには1GB(ギガバイト)が必要となってしまう。
同様に10進数の文字列にしようとすると、約3.2億桁、約300MBが必要となる。
これを実施しようとすると、「Out of Memory」などの例外が発生する場合がある。

Firefoxの精度(10の約31.6万乗=10進数で約31.6万桁、1Mbit)でも、問題となるようなケースはほぼ発生することはないと思うので、ブラウザによる違いは頭の片隅にでも覚えておけばよいいだろう。

限界値のみ知りたい方はここまでで、以下はどうやって探るかの一例を記述する。

JavascriptのBigIntとは

Javascriptで整数値を利用する場合、Number型と言う型を利用することになり、最大値は、Number.MAX_SAFE_INTEGER で定義され、通常 9,007,199,254,740,991(253-1)となっている。

しかし、近年のスマホでも64bitをネイティブ(内部レジスタ)で扱えるようになっており、53bit制度では足りず、これより大きい値を利用したいケースが増えてきている。

このため、近年のブラウザ搭載のJavascriptエンジンでは、Number型とは別にBigInt型と言うより大きな値を扱えるものを実装してある。

しかし、Number.MAX_SAFE_INTEGERのような定義がBigInt型には無く、扱える値の最大値が明確に知られてない。

Javascriptエンジンのソースは公開されているので、ソースを読めば分かるだろうが、そういう人は少数だろうから、もっと多くの人ができるであろう次の方法で探る。

調査方法

アルゴリズム

私が、プログラムのテスト/検証で仕様の限界が不明のとき、その限界値を探るなどの場合に使うテクニックに次のようなものがある。

ある数値を探すとき、まず適当に値を入力する。
それが、OKなら、次は数倍とかにして確認する。
NGなら、OKだったときとの半分ぐらいの値を次の入力して確認する。
これを繰り返していくことで、限界値を探る。

例えば、限界値の正解が6として、5から開始したとして、
5は6より小さいので、OKとなる。
次に5を2倍した10を入力すると、10は6より大きいのでNGとなる。
次は5と10の間の半分ぐらいの7を入力すると、7は6より大きいのでNGとなる。
次は5と7の間の半分の6を入力すると、OKとなる。
これで6が限界値と判明する。

BigIntの限界値は、Number.MAX_SAFE_INTEGER(253-1)より大きいことは分かっているので、基数(底)を2,8,10,16から選択し、指数部の初期値を1,000とした、これらのべき乗を計算できるかどうかを検証する。
OKであれば、指数部を10倍しながら検証し、どこまで指数部が大きくできるかを上記の方法含めて探る。

基数(底)指数部(2022-05-10修正)が開始時の値(初期値1000)より小さくする機能は実装してません
※基数(底)を2,8,10,16から選択できるは、10つまり10進数であれば一般人が、その他はプログラマーが直感的に理解しやすいため。

検証時の判定方法

プログラミングの処理は、ざっくりと次の種類に分類することができると、私は考えている。

  • 数値演算処理
    ロード/ストア(この2つは別項目にするべきか?)/四則演算/論理演算/ビット操作など
  • 比較処理
    if文
  • 分岐処理(場合によっては「比較分岐処理」として上記とまとめてもよい)
    ループ/ジャンプ(関数/メソッドコールなどを含む)
  • 例外処理(特殊な処理)
    割り込み/トラップ(意図的に例外を発生)など

この中の「例外処理」はとても重要なものなのだが、あまり説明されておらず、今まで「授業など」で学んだことはほぼ無く、「実務/実践」による経験で学んだことが多い。

今回は、限界値より大きい値の判定に、この「例外処理」を利用する。

Javascriptでの例外処理は、try { } catch {} を利用しする。
try部分の処理の実行に挑戦(try)し、問題がなければよいが、想定外の問題(例外)が発生したとき、その問題を捕まえてcatch部分で処理する。

let success = true;
let radix = 10n; //基数(底):数値の最後に'n'が付くとBigInt型
let exp = 1000n; //指数部
let val = 0n;
try {
	val = radix ** exp;
} catch ( error ) {
	success = false;
	//error に例外の情報が入っているが今回は利用しない
}
if ( success == true ) {
	//"OK"を表示
} else {
	//"NG"を表示
}

「val = radix ** exp;」のべき乗の演算で、限界値を超えなければsuccessは trueのままとなり、限界値を超えれた(Javascriptエンジンが想定した範囲外の値となった)ら、例外が発生しcatch側の処理が動作、successは falseとなる。

実施例

以下は、コラッツ予想演算 ブラウザ(BigInt)版を作るときの事前調査にて手作業でやったことをプログラム化したものです。

JavascriptのBigIntの限界値を探る


基数(底): ※10を選択して演算したとき結果が表示されるまでそれなりに時間がかかります。
開始時指数部: ※半角数値(‘0’~’9’)以外は削除して処理します。
※通信は発生せずブラウザ上のみで演算します。
※演算結果がクリアされます。

ここに演算結果が入ります。

考察など

実行速度について

以下に、基数を’2’および’10’を指定して実行した例を各ブラウザ別に示します。

  • Firefox
    基数に’2’を指定したとき

    基数に’10’を指定したとき
  • Edge
    基数に’2’を指定したとき

    基数に’10’を指定したとき

その他の基数を含めた実行時間を表にまとめる。

ブラウザ281016
Firefox5(ms)4(ms)6,434(ms)4(ms)
Edge509.9(ms)398,833.3(ms)409,904.3(ms)333,786.7(ms)

Firefoxが1Mbit、Edgeが1Gbitと求める値に1024倍の差があるため、FirefoxとEdgeの実行時間を直接比較する意味はあまり無い。

Firefoxの結果は、基数が10(=10進数)のときのみ6,434(ms)=約6(s)で、他は4または5(ms)と約1200~1600倍と高速であり基数が2,8,16による違いは誤差程度しかない。
現在のコンピューターは内部をすべて2進数で処理している関係上、2のべき乗を効率よく処理するようにプログラミングすることは可能であり、これがうまく機能しているものと推測できる。

Edgeの結果は、基数が2(=2進数)のときのみ509.9(ms)=0.5(s)で、他は約333~409(s)と約600~800倍と実行時間が大きい。
基数が2のときに対しての処理は効率よくなるように作られているが、他の2のべき乗 8=23,16=24の処理は効率よくなるようには作られないものと推測できる。

2のべき乗を見つけて効率よく処理するプログラミングをすることは、現代のコンピューターでも数百~千倍の効果が出ることが分かる。

関連投稿

コラッツ予想演算 ブラウザ(BigInt)版

ご意見、ご要望、不具合などのご連絡

ご意見、ご要望、不具合などのご連絡は次からお願いします。

コメント

タイトルとURLをコピーしました