bigint.js v0.5 beta 24

2004-02-24 ... 2004-03-01

bigintライブラリ自身のインスタンスメソッド isProbablePrime は任意の巨大整数を受け付けますが、 getPseudoprimeTable は現在、作れる表の最大値 2²⁷ です。 もちろん遅くてもいいならいくらでも拡大できますが……。10⁸以下の底2の擬素数2057個を一覧表示するのに約5時間かかりました （PCを他のことに使っていたせいもあるかもしれません）。1万以下とか10万以下とかのデモならわりと一瞬なので試してみてください。 底は2以外でも任意の数にできます。

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

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

更新履歴

• 2004-02-24 10万以下の擬素数をリストアップするデモ
• 2004-02-27 IEで高速化（10万まで約60秒→6秒台）。100万までの擬素数リストを1分程度で生成できる。
• 小さい数に対する Bigint.prototype.isProbablePrime() を10倍以上高速化。 ただし、Bigint._isProbablePrime_typeN を直接呼び出したほうが、さらに2倍速い。
• Bigint.getPrimeTable( min, max )は、指定された範囲の素数表を生成する。 Bigint.countPrimes( max )は、指定された数以下の素数の個数を数える。
• 2004-02-28 JavaScript自身の組み込み関数を使って擬素数を数える方法には、2**26.5=94906265の壁があり、 10**8にぎりぎり到達できない。これを一応できるようにした。この場合、bigint.jsを使うと遅すぎる。 逆に、bigint.jsの繰り返し二乗法はもっと速くなるのではないか。この速度には不満と疑問が残る。 10**8までの擬素数のリストを作るのに約4時間かかった。
• Bigint.getPseudoprimeTable( min, max, base ) を実装。指定範囲内の底 base のすべての擬素数を配列として返す。デモ付き。 さしあたって、引数の上限は 134217728 （ライブラリ的にはいくらでも大きくできるが、あまり速くない）
• 2004-02-29 昨日、Bigint._isProbablePrime_typeN の検査可能範囲を2**27=134217728まで拡張した Bigint._isProbablePrime_typeN2 を作ったが、内部的に 2**53 の壁を越えて計算精度が失われ、 擬素数かどうか判定できなくなる場合があった。このバグを修正した。

The number of Primes less than 100000000: 5761455
DEBUG: tableSmallPrimes.length : 1229
DEBUG: ** Total Cost: 1817.964 seconds

[index]