okuの日記： 乱数ジェネレータ

ふとした動機で乱数ジェネレータの勉強をしています。

取り敢えず、巡り合ったのが IBM developper works の「ハードウェアがなくても、ソフトウェアを最大限に活用してきわめて安全な乱数ジェネレーターの作成が可能」です。 実際に私が必要としているのは再現性があって、内部状態を persistent にできればそれでよし、なので 「本当に安全なソフトウェアには、正確な乱数ジェネレーターが必要である」 に示されている Random() の実装で十分です。

さて、今宵はこれまでにして明朝に備えましょう。 何しろ 18:00 頃から耐えられなくなって三時間ほど職場で寝込んでしまったくらいですし... (21:00～23:30 まではきちんとお仕事)

とても参考になります

[bluedwarf (11629)]

ブックマークにIBM deverloper worksと「安全なソフトウェアを作成する: ソフトウェアを利用したストラテジー」を加えました^^;

普段なにげなくプログラムで使っている乱数にもこれだけのストーリーが書けるとは知りませんでした。それ以上に、乱数だけでこれだけの考察ができるところがすごいと思います。
だから、IBMはどっかと違って素晴らしいと思うことがしばしば。
# ThinkPadは使ったことないけど。

--
// Give me chocolates!

Re:とても参考になります

[oku (4610)]

Random() で使われている線形合同法自体は良く知られた (というか定番) アルゴリズムで、確か中学生くらいの時に、今は亡き￥290 雑誌の PC マガジンに掲載されているのを読んだ記憶があります。 もっとも、当時よく使われていた Z80 にはリフレッシュレジスタという乱数源に使える便利な代物がありましたから、BASIC な人は素直に RND() を使い、マシン語では R レジスタの値に手を加えて乱数化するというのが一般的だったような気がします。 ということで、記憶がいい加減曖昧模糊としてきたので web 上の資料に当たらせていただくことにしました (大学では物理屋だったのできちんと情報数理をやったわけではない、っていうかやってない)。

通信経路の暗号化キー云々に使うとなると、記事の通り相当注意して乱数を扱わないといけないはずですが、私はちょっとしたミニゲームに使いたいだけですからこれで十分です。:-)

こういうものこそ Layer-8 [layer-8.com] に乗せてくれる人がいるとありがたいんですが、どうも自環境ベタベタなコードが好きな人が多いようで...

Mersenne Twister

[Jitterboogie (10223)]

最近ではMersenne Twister [keio.ac.jp]なんかも有名ですね。
擬似乱数なので暗号乱数としては使えないようですが、
スペクトル拡散とかモンテカルロ法なんかには向くようです。
MD計算用に勉強してみようかなと思っていたので私にはちょうどよいです。
M系列とか忘れてしまったなぁ。

従来の様々な生成法の欠点を考慮して設計されています。
プログラムはCで実装されていて、 このホームページからダウンロードできます。
従来にない長周期, 高次元均等分布を持ちます。 （周期が2^19937-1で、623次元超立方体の中に均等に分布することが証明されています。）
生成速度がかなり速い。 （処理系にもよりますが、パイプライン処理やキャッシュメモリのあるシステムでは、Cの標準ライブラリのrand()より 高速なこともあります。）
メモリ効率が良い。 （32ビット以上のマシン用に設計されたmt19937.cは、624ワードの ワーキングメモリを消費するだけです。1ワードは32ビット長とします。