hapint: 設計, 特徴, アルゴリズム

精度

hapint.es は ECMAScript (JavaScript, ActionScript, etc.) のための任意精度整数演算ライブラリです。 最大桁数は本当に任意です。すなわち,ECMAScript の仕様に忠実なエンジンで実行するならば, メモリの許す限り,表現できる整数値に上限/下限はありません

多くの多倍長整数演算ライブラリは,その実装方法に起因して,扱える数の範囲にメモリの限界よりも小さな上限/下限があります。 (ただし多くの利用場面では実用上問題のない制限かもしれません。)

設計

hapint は2種類のインターフェイスを提供することを目的として作成されています。 1つは,Java の java.math.BigInteger クラスとの互換性 (すなわち,Java のプリミティブな整数演算および java.lang.Math のメソッドと互換)を目指したインターフェイスです。 ライブラリのドキュメントではこれを BigInteger インターフェイスと呼んでいます。 もう1つは,ECMAScript のプリミティブな数値演算との互換性を目指したインターフェイスです。 ドキュメントではこれを arith インターフェイスと呼んでいます。 両者の違いはいくらかありますが,顕著な例を1つ挙げると,ECMAScript の数値は負のゼロを持ちます。

hapint は signed magnitude 表現を採用しています。magnitude の表現には片方向リンクリストを採用しています。 これによって任意精度や負のゼロ表現を実現します。リンクリストは下位の桁から順に並びます。 hapint は,java.math.BigInteger と同様に,immutable オブジェクトとして使われることを意図しています。 演算によってオペランドにも変更が伴うことはありません。 ただし,演算ごとに結果として完全に別のオブジェクトを作成するのではなく,magnitude を表すオブジェクトはできるかぎり共有されます。 例えば,大きな数に 1 を加えた場合,上位の桁を表すオブジェクトのほとんどは,オペランドと戻り値の間で共有されるでしょう。 つまり,片方向リンクリストによってメモリが節約されます。 一方で,エンジンによっては,他の種類の実装(例えば配列を用いた実装)よりも幾分実行速度を犠牲にするかもしれません。

hapint の現在のバージョンには4種類の BigInteger クラスが実装されていますが,その内の1つがメインであり, 残りの3つはメインの内部で使うために用意されています。 というのも,hapint は magnitude の各桁を表すのにも BigInteger オブジェクトを使用します: 言うなれば,BigInteger の入れ子です。 この内部 BigInteger クラスは,ファクトリメソッドを通じてユーザが任意に入れ替えることができます。 BigInteger インターフェイスに準じているならば,他のライブラリのクラスを使うことも可能です。 当然,hapint の演算の実行速度は,内部 BigInteger クラスのビット長や演算速度に大きく依存します。

アルゴリズム

hapint では,多くの演算にて,オプションの引数を使うことでユーザが演算アルゴリズムを切り替えられます。 複数のアルゴリズムの組み合わせで構成される演算もありますが,配列リテラルを用いたLISPスタイルの引数指定によって,複雑なアルゴリズム構成やアルゴリズムパラメタの最適化が容易に行えます。 デフォルトのアルゴリズムやパラメタもファクトリメソッドを通じて変更できます。

このドキュメントとソースコードは別々にメンテナンスされているため,下に列挙されているのは hapint に使われている有名なアルゴリズムのすべてではありません。

乗算

Schoolbook multiplication
いわゆる筆算
Squaring algorithm
A. Menezes, P. van Oorschot, and S. Vanstone. 1996. Handbook of Applied Cryptography. Chapter 14
カラツバ法
Toom–Cook multiplication
FFT 乗算

除算

Schoolbook division
いわゆる筆算
Knuth's algorithm
3 types implemented
Divide and conquer division
Division using reciprocal by Newton-Raphson method
Restoring division

最大公約数

ユークリッドの互除法
Binary gcd algorithm
拡張ユークリッド互除法
Extended binary gcd algorithm

冪乗

Left-to-right 2k-ary exponentiation
Left-to-right 2k-ary exponentiation with lazy precomputation
Left-to-right sliding window exponentiation
Left-to-right sliding window exponentiation with lazy precomputation

モジュラー算術

Multiplicative inverse by the extended Euclidean algorithm
Multiplicative inverse by the extended binary gcd algorithm
モンゴメリリダクション
Montgomery multiplication and exponentiation.
Barrett reduction
Modified Barrett reduction
Exponentiation over even moduli using Chinese remainder theorem

素数判定

ミラー-ラビン素数判定法
エラトステネスの篩
Lucas-Lehmer primality test
computed with Jacobi symbol
Optimizations
A. Menezes, P. van Oorschot, and S. Vanstone. 1996. Handbook of Applied Cryptography. Chapter 4

FFT乗算

hapint は高速フーリエ変換 (FFT) を用いた乗算を実装しています。 このFFTの実装にはランダムアクセスと浮動小数点数演算が必要です。 ECMAScript には配列長の上限があり,また,プリミティブ数値は IEEE 754 の 64 ビット二進形式であるため,FFT乗算には適用の上限が生じます。

現在の実装では,1桁あたりのビット長を k として,およそ 2 min( (26 - k) * 2 - 1, 31 )がオペランド2つの合計桁数の上限です。 前者は浮動小数点数の精度によるものであり,後者は配列長によるものです。

FFT が適用できない場合,フォールバックの乗算アルゴリズムが使われます。 このことから,場合によっては,桁のビット長を短く設定したほうが速いということが起こりえます。

インスタンスキャッシュ

magnitude を構成する内部 BigInteger オブジェクトのキャッシュ機構が実装されています(デフォルトでは off です)。 キャッシュが働いている場合,例えば 1 個の 1 と 100 個の 0 の桁からなる hapint オブジェクトでは,使用される内部 BigInteger オブジェクトは 2 個です。 このように,場合によってはキャッシュはメモリの節約になりますが,この機能は主として比較的小さな桁ビット長における高速化を目的として実装されたものです。

hapint オブジェクト自体のキャッシュ機構はパフォーマンスを落とすため実装されていません。

反復メソッド

素数に関するいくつかのメソッドは計算時間が多くかかります。 現在の ECMAScript エンジンのほとんどは単一スレッドで走るので,ユーザは実践的にはこれらのメソッドを非同期的に実行する必要があるかもしれません。 この目的のために,hapint はこれらのメソッドについて途中で中断できる代替メソッドをサポートしています。 それらは 'yield' を用いて実装され,ジェネレータイテレータと呼ばれます。 もしこの機能を使うなら,エンジンは ECMAScript 4 の特徴をサポートしている必要があります。 この機能に用がない場合,ECMAScript 3 環境は yield キーワード を外部の関数名と見なすので hapint ライブラリは支障なく動くでしょう。