コンピュータの目的の一つに、「現実世界の計算機内での模倣」、いわゆるシミュレーションがある。現実世界は本質的に不確定性を含んでいるため、乱数は多くのシミュレーションにとって不可欠な道具となっている。近年その需要を増している物理・金融などでのモンテカルロシミュレーションでは、一つ一つの素粒子や投資家に乱数を割り振るため、大規模に乱数が消費される。この場合、乱数発生の速度がシミュレーションの速度に、乱数の品質がシミュレーションの信頼度に大きく反映される。本論文の1章では、これら乱数発生法の重要性、ならびに乱数性の評価方法について議論を行っている。

　従来、速度と品質の両面で「良い乱数生成法」と呼べるものは数少なかった。現在でも多くのプログラム言話が標準疑似乱数(例:cのrand())として線形合同法など30年以上前に開発されたものを採用している。これらの多くの生成法の周期は2^31程度であり、現代のコンピュータではすぐ使い切ってしまう。より周期の長い3項GFSR系列(伏見・手塚ら)、Subtract with borrow(Marsagliaら)などの比較的新しい生成法も、物理のIsing Modelシミュレーションなどで有意の誤差を生むなど、統計的欠陥、理論的欠陥が指摘されていた。一方、ran2(L’Ecuyerら)など良質と考えられる発生法は時間コストが大きかった(rand()の4倍ほど遅い)。

　これらの問題に対する解決策として、本論文の2章は、著者が西村拓士氏と共同で開発した、メモリ効率・周期の長さ・乱数性・速度の面で既存の方法をしのぐ乱数発生法MT(Mersenne Twister)を取り扱っている。2.1節では、現存する生成法の問題点をあげ、それらの欠点を解決していくうちにいかにMTに到達したかを記述している。2.2節では、MTの性能を既存の方法と比較している。実装されたCコードmt19937.c(Appendix 4.3参照)は、周期2^19937-1(従来の記録は2^1500程度)、623-次元均等分布性を持ち、実装の仕方によってはcのrand()より4倍ほども高速である。メモリは624ワード(1ワード＝32bit)を消費するだけで、c言語の使えるあらゆる計算機で使用できる。

　MTは、旧来のGFSR生成法に対し、次の4点により大幅な性能向上を実現したものである。

　Twisting:従来のGFSR生成法の消費メモリをワード長分の1に滅らすTwistingという手法を導入した(Twisted GFSR,栗田良春氏との92年の共同研究)。このTwistingは同時に特性多項式の項の数を増やし三項GFSRの欠陥を解消する。数学的には状態変移関数の既約化である(2.1.3節)。

　Tempering:Twisted GFSRの高位ビットの独立性の欠陥を、"Tempering"という、低位ビットの乱数性を高位ビットに汲み上げる手法により解決した(2.5節)。

　Incomplete Array:MTは、Twisted GFSRの周期を2^p-1型の素数(Mersenne素数)にしたものである。周期の最大性の判定を行う際、周期が素数ならば合成数の場合に比べずっと計算量が少ないため、長周期を実現できる。これには、"Incomplete Array"という配列の一部を除去するアイデアが使われた(2.3.1節)。

　Inverse Decimation Method:周期$2^{19937}-1を確認するには19937次多項式の既約性判定が必要となる。従来のアルゴリズムは次数dに対し時間計算量0(d^3)であったが、著者はInverse Decimationと名付けたMTに特有な0(d^2)の算法を考案し、数十年かかるパラメータ探索を1週間に短縮した(2.3.2節)。

　また、著者は乱数性の強力な評価基準であるk次元均等分布性をMTの出力列に対して求めるため、手塚-Couture-L’Ecuyerの格子構造を使った数論的アルゴリズムを、MT向けに効率化した(2.3.3節)。

　MTの高速性は、掛け算・割算をまったく廃し、ビット操作のみで生成を行うこと、キャッシュメモリ・パイプライン処理に適した配列演算の利用など、現代計算機のアーキテクチャを十分反映して設計されていることによる。

　第3章では、並列システム用疑似乱数生成法"Dynamic Creator"を提唱している。これは、利用者を識別するためなどの目的で使用されるIDを疑似乱数のパラメータに埋め込みつつ、動的に疑似乱数発生法を生成するというアイデアである。

　大規模ネットワーク上での分散計算は近年その重要性を増している。これは、一つの大型計算機を多人数で使う旧来のシステムから、一人が一台以上の小型計算機を持ち、それらがネットワーク上で連携して計算を行えるという最近のシステムへの計算機環境の変化に伴うものである。しかし、分散システム上で乱数を発生し、再現性のあるシミュレーションを行うことは容易ではない。通常行われている方法は、一つの疑似乱数発生法を固定し、例えば素粒子シミュレーションなら各素粒子にIDを割り振り、IDによって同一の疑似乱数発生法の初期値を変えて使用するというものである。この場合、特に漸化式が線形であるときには、複数の素粒子の乱数発生法間に比較的単純な線形関係式が成立し、独立性を破壊する恐れがある。著者は、初期値のみを変える代わりに、IDを漸化式に埋め込んで、素粒子ごとに互いに素な特性多項式を持つ異なる疑似乱数発生法を割り振ることを提案した(3.2節)。これならば、異なる素粒子の間で相関が生じる可能性は非常に低いと思われる。

　これを実現する方法として、Dynamic Creator(DC)というプログラムを提唱した。これは、ユーザーが仕様(ワードサイズ、周期など)とIDを指定すると、そのIDを埋め込んだ仕様を満たすMTのパラメータを返すプログラムである。3.3節では、DCが現実的に稼動するかどうかを実験によって確かめている。周期の長い(2^4423-1)MTを一つ生成するのに27時間程度、比較的短い周期2^521-1のMTの生成に2.6秒ほどが費やされている。素粒子シミュレーションなど、繰り返し乱数発生法を生成しなおす応用では、生成にこのような時間を費やすことは現実的でない。この場合、あらかじめ乱数生成法のパラメータをテーブルにして持つなどの工夫が必要である。

　3.4節では、同様の動的生成を合同法で実現するのが困難であることを解説し、DCがMTのGF(2)上での線形性をいかに利用しているかを述べている。実際、MTのパラメータ選択の柔軟性がDCを実現する鍵となっている。

　Appendix 4.1ではMTの状態遷移行列の具体的な形を求めている。Appendix 4.2ではMTの高次元均等分布性が周期から来る理論的上界に一致しないことを証明している。Appendix 4.3はMTのc言語による実現を記述している。

　近年のコンピュータの性能の飛躍的向上に伴い,乱数を使って複雑なシステムの特性などを実験的に解析する大規模なモンテカルロシミュレーションが広範に行われるようになってきた.この場合の基本的な道具として,大量の良質な乱数を高速に供給する手段が重要であり,従来いろいろな方法が提案され,使用されてきたが,それらに対しては種々の難点も指摘されている.本論文は,これらの難点を克服する新しい乱数発生法を提案するものであり,「M系列を用いた高次元均等分布性を持つ乱数の発生法とその動的生成」と題し,英文で記述され,本文3章および付録から構成されている.

　第1章「An Overview on Random Number Generation」では,既存の方法,それらの出力に対する統計的検定法,以下の議論のための数学的定義などを述べている.

　第2章「Mersenne Twister」は本論文の主要部であり,著者が提案したメルセンヌツイスター(MT)と称する乱数生成法について述べている.

　2.1節では,既存の乱数生成法である線形合同法やGFSR法の問題点をあげ,後者のもつ問題点を解決しようと試みるうちにMTに到達した経緯と,MTのアルゴリズムを述べている.

　2.2節では,MTの性能を比較的新しいいくつかの方法と比較し,MT19937と名付けたものは,生成速度がほぼ等しい生成法の中でとびぬけて長い周期(2の19937乗-1)と,高次元での均等分布特性を持つことを示している.必要とする記憶容量は624ワード(1ワード＝32ビット)で比較的大きいが,現在のコンピュータでは,とくに問題とすべき大きさではない.

　2.3-2.5節では,MTを実現するために考案した4つの技巧について述べている.Twistingは,従来のGFSR法に対して,ワード長分の1の記憶容量で同一の周期を達成する手法である.これによって生成されるTwisted GFSRと称する数列に生ずる高位ビットの独立性の欠陥をTemperingという手法により除去する.高位ビットの独立性の判定は,多次元均等分布性の判定につながるが,そのために他の著者達が提案している数論的方法をMT向けに効率化して使用している.長い周期の判定を行う際に,周期が合成数の場合よりは素数の場合の方がずっと計算量が少ないため,記憶しているビットの一部分を除去することによって周期の候補を素数(メルセンヌ素数)にするのがIncomplete Arrayという技巧である.実際に周期を確認するためには,19937次の多項式の既約性を判定する必要がある.一般の多項式に対して現在知られている判定法は,次数の3乗のオーダの時間計算量を必要とするが,著者はMTに特有な2乗のオーダの判定法を考察し,Inverse Decimationと名付けている.

　第3章「Dynamic Creation of PRNG」では,種々のパラメタを持つMTの動的生成の方法を提案している.これは,異なるアーキテクチャを持つコンピュータ用の乱数生成法,あるいは並列計算機上での複数の乱数列生成法が欲しいという要請に応えるものである.そのために,利用者がIDとワードサイズと周期などの仕様を与えると,そのIDを埋め込んだ仕様を満たすMTのパラメタを返すプログラムを開発している.数値実験によりMTを一つ生成するための所要時間を測定し,数秒-27時間程度という結果を得ている.長時間を要するものは「動的生成」という目的には合わないが,事前に計算して得られたパラメタの値を保存しておくことにすれば,この難点は克服できる.

　付録では,MTのC言語による実現案を記述している.

　以上を要するに,本論文は有限体上の種々の理論とアイディアを駆使して,従来の乱数生成法に比べてはるかに長い周期と高次の均等分布性を有する乱数列を高速に生成する方法を開発したものであり,数理工学上の貢献が大きい.よって本論文は博士(工学)の学位論文として合格と認められる.