附録：乱数
乱数とはランダムな数、つまり予測が不可能な数である必要があります。
本物の乱数は作りにくい
完全なランダムというのは意外と難しいものです。
例えば数学の試験で突然、「サイコロを 100 回振った時の目の出方について具体例を示せ」と問われたらどうすべきでしょうか。六角鉛筆を持っていた人は幸運ですが、それ以外の人は自分の頭で「ランダムな数列」を考えなくてはなりません。
サイコロの目は当然均等に出るべきですが、これは「6 回毎に 1 ～ 6 を適当に並べる」とかやると全然ダメな訳です。何故ならその数列は「5 回目までに 2 以外が出ていれば 6 回目は必ず 2」といった様に、それぞれの回の目が他の回と関係している（独立でない）からです。
こうして考えてみると、多少は「本物の乱数」を作る事の難しさを感じて頂けたでしょうか。
CPU は試験を受ける学生よりも遥かに徹底して決まった入力に決まった出力しか返さず、鉛筆を転がすなんて機能はついていない代物なので、ランダム性を生み出すにはそれなりの工夫が必要となります。
擬似乱数
擬似乱数とは、そんなお堅い CPU に鉛筆転がしの真似事をさせるアルゴリズムです。
擬似乱数にも色々と種類があるのですが、初期値（シード）を与えるとそれに繰り返しややこしい処理をしてランダムっぽい数列を生み出してゆくのが基本です。
シードはコンピュータを起動してからの累積時間を使うのが一般的です。
（逆に言えばシードとアルゴリズムさえ判ってしまえば乱数列を完全に予測できる訳で、或るゲームでは迂闊にも秒単位のシードと線型合同法を用いた為に「乱数調整」なる黒魔術の存在を許す事となりました。）
線型合同法
名前の通り線型関数（掛け算と足し算）そして合同式（余りの計算）で定義されます。
例えばシードをx = 1として
| x = ((x * 1103515245) + 12345) % 2147483648u; |
を繰り返し計算すると（数学的には xn+1 = 1103515245 xn + 12345 mod 231）、xの値は
| 1103527590 | |
| 377401575 | |
| 662824084 | |
| 1147902781 | |
| 2035015474 | |
| ... |
となります。これは一見ランダムっぽいのですが、二進法で見ると下位ビットには明らかに法則性が確認できます。
| # | 十進表記 | 二進表記（31 桁） |
|---|---|---|
| 1 | 1103527590 | 1000001110001100111111010100110 |
| 2 | 377401575 | 0010110011111101011000011100111 |
| 3 | 662824084 | 0100111100000011110010010010100 |
| 4 | 1147902781 | 1000100011010111001101100111101 |
| 5 | 2035015474 | 1111001010010111101111100110010 |
| 6 | 368800899 | 0010101111110110111010010000011 |
| 7 | 1508029952 | 1011001111000101011011000000000 |
| 8 | 486256185 | 0011100111110111010111000111001 |
特に 20 の位が 0 と 1 を繰り返す（つまり偶数と奇数が交互に現れる）辺りは酷いものです。
この場合xは 231 で剰余を取っているのでその値は 231 通りしかなく、生成される擬似乱数は 21 億ちょっとの周期を持つ事になります。
xorshift
2003 年に発表されたアルゴリズムで（Marsaglia, George. Xorshift RNGs. Journal of Statistical Software. 2003, 8(14).）、下記のコードにより 2128 - 1 の周期を持つ擬似乱数が生成できます。
高速でありながら、質は線型合同法より遥かにまともです。
| unsigned long xor128() | |
| { | |
| static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123; | |
| unsigned long t; | |
| t = x ^ (x << 11); | |
| x = y; | |
| y = z; | |
| z = w; | |
| w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); | |
| return w; | |
| } |
メルセンヌ・ツイスタ
自分で実装するのではなくライブラリを利用する場合はこれが定番でしょう。（リンク先は改良版で、オリジナルのメルセンヌ・ツイスタはこちらです。）
219937 - 1 などの非常に長い周期を持ち、乱数としての質もかなり高い事が知られています。
ハードウェア乱数
ゲームなどで使う分には起動時間のシードとまともなアルゴリズムを使えば十分なのですが、暗号の鍵の生成などセキュリティに関わる部分ではあまりにも無防備と言わざるを得ません。こうした領域での乱数の予測は、ゲームの強キャラ・レアアイテムとは比較にならないほど金になるからです。
よりセキュアな乱数生成の為に、例えば Intel の CPU では rdrand というハードウェアで乱数を生成する命令があったり、Linux には /dev/random という仮想デバイスがあったりします。Linux の場合は物理的なデバイスのノイズなどを収集している様です。
セキュアな乱数を追及しようとするとなかなか果てがないのですが（rdrand だって NSA が予測できる様に細工されていないという保証はどこにもない訳です）、通常の用途ならばシードにのみこうしたハードウェア乱数を用いるだけでも十分に予測不可能な乱数を得る事ができるでしょう。
参考
- 良い乱数・悪い乱数
- 様々な処理系の擬似乱数を調査・比較しています。
- 間違いだらけの疑似乱数選び
- 擬似乱数アルゴリズムの歴史について詳しく述べられています。