64ビット最適均等分布F2-線形発生法

64ビット最適均等分布F2-線形発生法 MGLG-64

64ビット最適均等分布F2-線形発生法、通称MELG-64は、最新の擬似乱数列生成器（PRNG）の一つです。この手法は、原瀬晋と木本貴光によって開発され、2018年にACM TOMSにおいてその成果が発表されました。この技術は、従来の64ビット長周期の線形擬似乱数発生法、特にメルセンヌ・ツイスタ法に比肩する速度で、質の高い擬似乱数列を生成することができます。

特徴と利点

MELG-64の特徴として、まず挙げられるのはその長周期です。周期は219937-1という非常に長い値であり、これは広く採用されているメルセンヌ・ツイスタ法と同じ周期です。この長さは、多様な分野での提案や応用において重要な役割を果たします。また、初期化時に必要なワーキングメモリのサイズに応じて、2521-1から244497-1までの異なる周期の実装が可能です。

特に注目すべきは、高次元均等分布性の完全最適化です。この特性は、擬似乱数の一様性を保証する要素であり、複雑なシミュレーションや多次元解析での使用に非常に有用です。従来の64ビット型生成器では実現されていなかったこの特性により、幅広い応用が可能になります。

構造と性能

さらに、MELG-64は特性多項式の非零項数が大幅に増加しているため、初期状態の配列に0が多く含まれていても、出力列が零超過状態から迅速に復帰できることが期待されます。この性質は、乱数の生成における堅牢性を向上させ、特に重要な応用にとっての信頼性を高める要素となっています。

また、この63ビット生成器は、二元体F2={0, 1}を使用した設計に基づき、理論的な性能評価が行われています。並列計算環境での使用を想定した初期状態のジャンプ機能も標準装備しており、出力列が重ならないよう配慮されています。

高次元均等分布性

高次元均等分布性とは、擬似乱数発生器の性能を測る指標の一つで、vビット精度k次元均等分布性により評価されます。具体的には、周期Pのwビットの2進整数列を考え、そこから取り出した上位vビットが均等に分布しているかどうかを測ります。この特性は、擬似乱数の理論に基づく信頼性の指標の一つであり、出力列の上位ビットが理論的な上限に達している場合、最適均等分布性を持つとされます。

メルセンヌ・ツイスタ法との比較

MELG-64は、64ビットで特性多項式の非零項数が219937-1を持つMELG19937-64と比較されます。従来のメルセンヌ・ツイスタ法と同様に、高次元均等分布を達成しつつ、処理速度も諸条件下で競争力があります。

結論

MELG-64は、品質、速度、柔軟性を兼ね備えた新たな擬似乱数生成技術であり、今後の研究や開発において、シミュレーションやモデリング分野での利用が期待されます。この生成方式は、幅広いアルゴリズムやアプリケーションにおいて、信頼性の高い乱数を提供するソリューションになるでしょう。

もう一度検索