メルセンヌ・ツイスタをわかった気になる | 6715.jp

メルセンヌ・ツイスタについて。 メルセンヌ・ツイスタ(MT)は擬似乱数列を作るアルゴリズムの一つで、 他の手法と比べると欠点が少なくて高品質な擬似乱数列を高速に作れるんだって。スゴイ！ プログラムをかじった人なら、多分聞いたことがあるんじゃないかと思います。 日本初のアルゴリズムだし、日本語文献あるかな？って思ったんですけど、良い物が見つからなかった（かなしい）ので、 元の論文を読みながらRubyでMTを実装して理解を深めたいと思います。 なんか強いアルゴリズムだ！って聞くとめっちゃ複雑なんじゃないかって思いがちですけど、MTはとっても†単純†です。 MTの定義wwwビットの整数からなる乱数列を生成する場合を考えます。 この時、整数を各ビットで分けてwww次元行ベクトルとして考えることとします。 すると、MTによって生成される乱数列は以下の線形漸化式によって表されます。 xk+n = xk