bigint.js v0.5 beta 21

2004-01-22

bigint.js v0.5 は、JavaScript で巨大な数を扱うための汎用ライブラリです。 このライブラリを使って、例えば、RSA暗号、楕円曲線暗号、巨大な階乗などを実装できます。

このページでは、ばかばかしいほど大きな数が関係する「階乗」のデモをお楽しみください。 別ページに、0から20万のあいだの好きな数の階乗を自由に計算できるデモもあります。 JavaScriptだけで10万の階乗を一桁残らず計算した記録、 「10ⁿの階乗の末尾の0の個数」についてのエッセイをお読みください。

bigint.js v0.5 は現在、開発テスト中のベータで、不具合や未実装の部分も多々あります。 前回からの更新。 お気づきの点があれば掲示板にお願いします。

更新履歴

• Bigint.stirling() は、スターリンの式で、引数の階乗を近似する。 内部的には単なる浮動小数点演算であり、引数が巨大になると、指数部も近似値になる（つまり何桁ある数なのかさえ正確には分からなくなる）。 それでも、おおざっぱな大きさを素早く知るのに便利。
• Bigint.getFactorial10E()は、10^n 型の数について、スターリンの公式を1000桁の有効桁数で実行する。 したがって、例えば、10の100乗や500乗の階乗でも、正確な桁数と、上位数桁を報告できる。
• Bigint.getFactorialTrailingZeros()を実装。 任意の階乗の末尾の0の個数を正確に報告する。 引数が10^1000程度でも計算でき、所要4分で、 次の答えを得た。 2499999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 ... 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999785 (1000-digit) 引数が10のべきのときは、実際には、getFactorialTrailingZeros10E() を使ったほうがはるかに速い。
• Bigint.getFactorialTrailingZeros10E()は、10^n 型の数に対して、階乗の末尾の0の個数を高速に計算する。 例えば、Bigint.getFactorialTrailingZeros10E( 1000 ) は、 上記 Bigint.getFactorialTrailingZeros に 10^1000 を入れたのと同じことだが、 約100倍も速い2秒程度で同じ答えを出す。 (10^10000)!の末尾の0の個数を調べると、4分少々で、次の答えを得た。 2499999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 ... 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999999999 9999997873 (10000-digit)
• 論理シフトを利用してオブジェクトの値を2倍にする Bigint.prototype.twice() を導入した。 通常のかけ算より速い。
• 文字列の「シフト」で 10ⁿ をかける Bigint._shift(n) を導入した。 右シフト（割り算）でシフト量が巨大のとき、通常の割り算よりかなり速い。 左シフトでは、ふつうのかけ算よりかなり遅いので、右シフト（nが負のとき）にのみ使うべき。
• 割り算のアルゴリズムが失敗するパターンを修正。 途中で余りが0になって、かつ下位の桁に非常に長い0があると、 従来の方法では割り算の続行に失敗した。
• 引き算のアルゴリズムの不具合を修正。 テーブル長が違う引き算でも結果テーブルの最上位に値0のセルが1つ以上発生する可能性があることを考慮していなかった。
• 現在、内部のメソッド Bigint.serio() が v0.4 と v0.5 で挙動が変わってしまっている。 入力が Bigint のインスタンスの場合、 v0.4 では入力そのものへの参照を返すが v0.5 では、入力の実体をコピーして、コピーへの参照を返す。 絶対に引数を破壊しないためだが、 その必要がないのにコピーをとるのはコスト的にむだなので、 v0.4 と同じ動作に戻すべきだ。 どこかでコピーを返すことに依存する内部実装を使ってしまったかもしれないので、 今後しばらく、全部のつじつまを合わせるまでの間だけ、コピーを返す Bigint.serio() とそのものを返す Bigint.misha() を使い分けることにする。

[index]