乱数を生成するアルゴリズムを勉強してみた！！
アプリやゲームをプログラミングする時、しばしば乱数を使用する。
ほとんどのプログラミング言語で、乱数を生成する標準ライブラリが準備されているが、内部的にどのように生成しているのかを考えたことはなかった…
そこで乱数を生成するアルゴリズムを勉強してみようと思った。
擬似乱数
PC, プログラム自らは情報を生み出すことはできず、何らかの計算式を使って、見かけ上ランダムな数値を生成する。このような乱数を「擬似乱数」と呼ぶ。
例えば、C言語の標準ライブラリには0〜32767の範囲で乱数を生成するrand関数がある。
乱数生成前のウォーミングアップとして、rand関数を使用してみる。以降では、擬似乱数を単純に「乱数」と表現する。
rand関数を使用する前に準備すべきことがある。それは乱数を生成する式の中で使われる最初の値を変えることである。この値を「乱数の種」と呼ぶ。
乱数の種
「乱数の種」を変えないと、rand関数は毎回同じパターンの数列を返す。
C言語は、srand関数を使って乱数の種を設定できる。srand関数の引数に、乱数の種を与える。
乱数の種には、time関数の戻り値を使うのが定番テクニック。
time関数は、1970年1月1日0:00からの経過時間を返す。この値は、プログラムを起動するたびに異なるため、毎回値を変えるべき乱数の種として好都合。
srand関数とrand関数の使い方を示すプログラムを示す。実行すると10個の乱数を表示する。
どのような乱数になるか？はプログラムを実行したタイミング（時間）次第。
ちなみに、8行目を"/* */"で囲んでコメントアウトしてみると、面白い結果が得られる。
何度プログラムを実行しても、毎回同じ結果が表示される。
#include <stdio.h>
#include <stdlib.h> //srand関数とrand関数のため
#include <time.h> //time関数のため
int main(int argc, char* argc[]) {
int i;
//乱数の種を設定する
srand((unsigned int)time(NULL));
//乱数を10個生成、表示する
for (i = o; i < 10; i++) {
printf("%d\n", rand());
}
return 0;
}乱数生成アルゴリズム⑴ ー線形合同法
C言語のrand関数内部で使用されていることで有名な「線形合同法」。
以下の斬化式（数列の１つ前の値で、その次の値を求める式）で乱数を生成する方法。
この式は、n番目の乱数Xnを、その１つ前の乱数X(n-1)を使った計算で得ることを示している。
modは割り算のあまりを求める演算子(C言語では%演算子)。
Xn = (A x Xn-1 + B) mod M
この式において、A, B, Mは、0より大きな整数の定数。
X0が「乱数の種」に相当する。
X0を式の右辺において得られる計算結果が、最初の乱数X1になる。
以下同様に、X1を右辺においてX2を得る。X2を右辺においてX3を得る…と繰り返し計算する。
#include <stdio.h>
//１つ前の乱数
int random;
//乱数の種を設定する関数
void srand2(unsigned int seed) {
random = seed;
}
//乱数を生成する関数
int rand2() {
random = (2 * random + 3) % 7;
return random;
}
int main(int argc, char* argv[] {
int i;
//乱数の種を設定する
srand2(3);
//乱数を10個生成する
for (int i = 0; i < 10; i++) {
printf("%d\n", rand2());
}
return 0;
}上記において、A = 2, B = 3, M = 7 として生成した乱数生成rand2関数と、乱数の種を設定するsランD２関数。
C言語の標準ライブラリの関数と間違えないように、関数名の末尾に2を付けた。
グローバル件数randomに格納するだけ。rand2関数は、線形合同法の式に従って乱数を計算し、その値をグローバル変数randomに格納し、戻り値として返す。
テスト用のmain関数では、srand2関数の引数に、time関数の戻り値ではなく3（適当に選定）を与えている。
擬似乱数には周期性がある
rand2関数の
random = (2 * random + 3) % 7;の部分を見れば、乱数生成の仕組みがわかる。
直前に生成された値を2倍して3を加えることによってできる数列が、乱数のようにみえる。
ただし7で割った余りのため、生成される乱数の範囲は、0~6に制限される。
この結果、同じ数列が繰り返されることがわかる。
擬似乱数の特徴であり、「周期性」と呼ばれている。
