Go to Qiita Advent Calendar 2024 Top
LoginSignup
38
19

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@shimataro999

JavaScriptの任意精度整数: BigInt vs big-integer （2018年11月2日追記）

Last updated at Posted at 2018-04-29

はじめに

先日Node学園 30時限目に参加して、Node v10で新しく入ったBigIntについて話してきました。

本記事では発表内容の補足というか、時間の都合上「おまけスライド」にしたbig-integerパッケージとの比較について説明します。

スライドどれよ

BigInt あれこれ

この記事を読む前に、軽く目を通しても通さなくてもどっちでもいいです。

基礎知識

まずは、NumberとBigIntとbig-integerについて簡単に説明します。

Number

  • 現在のJavaScriptの数値型
  • 64bit
  • ただし整数部は53bit
  • 詳しくはMDN参照

BigInt

  • TC39でプロポーザルに挙がっている新しい数値型
    • 現在はStage3
    • 採用確定ではない（Stage4になるまでは却下される可能性あり）
  • 任意精度の整数
    • ハードウェアがサポートしているのではなく、各処理系がソフトウェア的に実装する
  • 数値リテラルにnをつけるか、BigInt()関数で生成する
    • 256n, 0x100n
    • BigInt(256), BigInt("256"), BigInt("0x100")
  • Node v10で実験的サポート
    • --harmony-bigintオプションが必要

big-integer

  • 任意精度の整数を扱えるNPMのパッケージ
    • ビルトインの型でもオブジェクトでもないよ！
  • Node v0.6以降で動作
    • 最新バージョンにアップグレードしなくても使える

性能を比較してみる

ベンチマークその1

演算を1億回ひたすら繰り返す雑なベンチマークで速度検証してみます。

benchmark-bigint.js
let i, j, k, val;
for(i = 1n; i <= 100n; i++) {
    for(j = 1n; j <= 100n; j++) {
        for(k = 1n; k <= 100n; k++) {
            for(l = 1n; l <= 100n; l++) {
                val = i;
                val += j;
                val *= k;
                val %= l;
            }
        }
    }
}
benchmark-big-integer.js
const BigInteger = require("big-integer");

let i, j, k, val;
for(i = 1; i <= 100; i++) {
    for(j = 1; j <= 100; j++) {
        for(k = 1; k <= 100; k++) {
            for(l = 1; l <= 100; l++) {
                val = BigInteger(i);
                val = val.plus(j);
                val = val.multiply(k);
                val = val.mod(l);
            }
        }
    }
}

最後が除算ではなく剰余算なのは、（スライドを見てもらえばわかるとおもいますが）もともとNumberとBigIntの性能比較につかったベンチマークだったので、どちらでも結果が変わらない剰余算を使ったのが理由です。
（除算だと1 / 2 === 0.5に対し、1n / 2n === 0nと結果が変わる）

予想

そりゃBigIntのほうが速いでしょう。

big-integerはJavaScript上で実装しているのに対し、BigIntはJavaScriptの言語仕様に含まれている（オーバーヘッドが少ない）上にC++で実装しているんだもの。

結果

$ time node --harmony-bigint benchmark-bigint.js

real    0m22.087s
user    0m24.116s
sys     0m0.355s

$ time node --harmony-bigint benchmark-big-integer.js

real    0m7.587s
user    0m8.001s
sys     0m0.362s

ファッ？big-integerのほうが3倍も高速だと！？

解説

なんとも意外な結果ですが、実はbig-integerはNumber型で収まる範囲の演算についてはNumber型でそのまま演算するので、常にソフトウェアで演算するBigIntよりも速いのです。

ベンチマークその2

というわけで、今度はNumber型の範囲外の整数に対してベンチマークを走らせてみます。

benchmark-bigint-2.js
let i, j, k, val;
for(i = 1n; i <= 100n; i++) {
    for(j = 1n; j <= 100n; j++) {
        for(k = 1n; k <= 100n; k++) {
            for(l = 1n; l <= 100n; l++) {
                val = BigInt(Number.MAX_SAFE_INTEGER) + i;
                val += j;
                val *= k;
                val %= l;
            }
        }
    }
}
benchmark-big-integer-2.js
const BigInteger = require("big-integer");

let i, j, k, val;
for(i = 1; i <= 100; i++) {
    for(j = 1; j <= 100; j++) {
        for(k = 1; k <= 100; k++) {
            for(l = 1; l <= 100; l++) {
                val = BigInteger(Number.MAX_SAFE_INTEGER).plus(i);
                val = val.plus(j);
                val = val.multiply(k);
                val = val.mod(l);
            }
        }
    }
}

結果

$ time node --harmony-bigint benchmark-bigint-2.js

real    0m30.764s
user    0m33.004s
sys     0m0.343s

$ time node --harmony-bigint benchmark-big-integer-2.js

real    0m41.659s
user    0m42.663s
sys     0m0.932s

今度はBigIntがbig-integerより1.3倍高速という結果が出ました。

その他の違い

BigIntとbig-integerの実装には、パックの単位の違いもあります。
BigIntは4バイト単位でパックしているのに対し、big-integerは10000000単位でパックしています。

たとえば123456789012345678901234567890（0x18ee90ff6c373e0ee4e3f0ad2）という数値は

  • BigIntの場合
    1. 下から4バイト単位に切る; 1, 8ee90ff6, c373e0ee, 4e3f0ad2
    2. little-endianで配列に入れる; [0x4e3f0ad2, 0xc373e0ee, 0x0x8ee90ff6, 0x00000001]
  • big-integerの場合
    1. 下から10000000単位に切る; 12, 3456789, 0123456, 7890123, 4567890
    2. little-endianで配列に入れる; [4567890, 7890123, 123456, 3456789, 12]

このことから、次のようにも言えます。

  • 2進表現で高速に計算できるものはBigIntが有利
    • 2の累乗、4の累乗、ビットシフト等
    • 2進文字列、16進文字列等への変換
  • 10進表現で高速に計算できるものはbig-integerが有利
    • 10の累乗等
    • 10進文字列への変換
  • 1パックあたりに詰め込める値はBigIntのほうが大きいため、桁数が多くなるとBigIntが有利

ただし、「BigIntは4バイト単位でパックしている」というのはあくまでV8のBigIntの実装なので、JavaScriptエンジンごとに変わる可能性があります。

結論

どっちも得意分野と不得意分野があるので、条件によってBigIntが速いときもbig-integerが速いときもあります。
結局どっちを使えばいいの？という人のための目安を挙げておきます。

  • BigIntを使えない環境ならbig-integer一択
    • 古いNodeでも動かしたい
    • LTSを使いたい
    • --harmonyオプションを使いたくない
    • Webブラウザでも動かしたい
  • Number型の範囲に収まる可能性があるならbig-integerも検討の余地あり
  • ビットシフトや16進文字列への変換等、2進表現で高速に計算できる演算が多いならBigIntが有利
  • 10倍、100倍や10進文字列への変換等、10進表現で高速に計算できる演算が多いならbig-integerが有利
  • 桁数が何百、何千と多くなるとBigIntが有利

2018年11月2日追記

10月30日にNode v10のLTSがリリースされました。
https://nodejs.org/ja/

LTSで、 --harmony-bigint なしで BigInt を使えるようになりました！

$ node
> process.versions.node
'10.13.0'
> typeof 0n
'bigint'
> 2**100
1.2676506002282294e+30
> 2n**100n
1267650600228229401496703205376n
38
19
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
38
19

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?