Upgrade to Pro — share decks privately, control downloads, hide ads and more …

BigInt あれこれ / overview about BigInt

BigInt あれこれ / overview about BigInt

Node学園 30時限目の発表資料です
https://nodejs.connpass.com/event/83639/

shimataro

April 27, 2018
Tweet

More Decks by shimataro

Other Decks in Technology

Transcript

  1. 背景 背景 Number型 64bit(ただし 整数部は53bitまで ) 9007199254740991 (約9千兆)が限界 もっと大きな整数を扱いたい! 全世界の負債総額は

    2京円以上 だってさ TwitterのIDも53bitでは表現しきれない 時代は64bit DBにも64bit整数とかあるよね
  2. 背景 背景 BigInt 登場! 現在はStage3 Node v10 でサポート ただし --harmony-bigint

    が必要 64bitではなく 任意精度 https://tc39.github.io/proposal-bigint/
  3. さっそく使ってみる さっそく使ってみる まずはビルド 正式リリースされたから公式ページからインストール! $ git clone --depth 1 https://github.com/nodejs/node.git

    $ cd node $ ./configure $ make -j4 # 並列ジョブ数はCPUのコア数に合わせる $ ./node -v # バージョン確認! v10.0.0-pre https://nodejs.org/
  4. さっそく使ってみる さっそく使ってみる BigIntの生成 100n, 0x100n BigInt(100), BigInt("100"), BigInt("0x100") 型変換: Number(100n),

    100n.toString() 小数点以下は切り捨てられる: (1n / 2n) === 0n Number型との共演はNG ビットシフトすら 1n << 10n と書く 文字列結合は "a" + 1n でOK
  5. 速度検証 速度検証 現在最大の (2^77232917 - 1) 超速い! メルセンヌ素数 $ time

    node --harmony-bigint -e "2n ** 77232917n - 1n" real 0m0.110s ←0.11秒!! user 0m0.094s sys 0m0.016s
  6. 速度検証 速度検証 底を変えてみる $ time node --harmony-bigint -e "3n **

    77232917n - 1n" real 124m47.252s ←2時間!? user 124m43.277s sys 0m0.260s $ time node --harmony-bigint -e "4n ** 77232917n - 1n" real 0m0.161s ←0.16秒! user 0m0.132s sys 0m0.029s
  7. 速度検証 速度検証 10進文字列に変換してみる 16進文字列に変換してみる $ time node --harmony-bigint -e "(2n

    ** 77232917n - 1n).toString( real 473m33.712s ←8時間!! user 473m32.767s sys 0m0.208s $ time node --harmony-bigint -e "(2n ** 77232917n - 1n).toString( real 0m0.165s ←0.16秒! user 0m0.125s sys 0m0.040s
  8. NUMBER型との速度比較 NUMBER型との速度比較 雑なベンチマーク 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 = i; val += j; val *= k; val %= l; } } } }
  9. 本番環境で使うには? 本番環境で使うには? 多分こういうこと ↓バベるとこうなる(多分)↓ 全部の演算子を置き換えなきゃアカン a += b; // a,

    bがBigInt型かどうかわからない class BigInt { ... } // ラップ用のクラス if (typeof a === "BigInt") { a = a.plus(b); } else { a += b; }
  10. まとめ まとめ Node v10で BigInt に対応したよ ただし --harmony-bigint が必要だよ 2進表現で高速に計算できるものは速いよ

    Numberよりはかなり遅いよ 現時点では big-integer を使おう 関西Node学園もよろしく! 登壇者大募集! 手品に興味があったら声をかけてね!
  11. ROUND 1: 雑ベンチ再び ROUND 1: 雑ベンチ再び big-integer版 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); } } } }
  12. ROUND 2: 場外乱闘 ROUND 2: 場外乱闘 big-integer版 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); } } } } real 0m41.659s user 0m42.663s sys 0m0.932s
  13. ROUND 2: 場外乱闘 ROUND 2: 場外乱闘 BigInt版 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; } } } } real 0m30.764s user 0m33.004s sys 0m0.343s