パソコン活用研究シリコンバレー（C、C++、の活用研究）

乱数を使うための準備

=======================================================================================
Cで乱数を使うための準備。ゲームの中で使うサイコロを作りたい（＝1〜6の乱数を得たい）というような
場合はほとんど問題にはならないのですが、コンピュータが作る疑似乱数は本当に偏りのないランダムな
値なのかという問題があり、２次元においてランダムな座標(x,y)を得るというような目的の場合には、品質が
悪くて使えない・・ということもあるようです。
ということで、乱数を使う前の心の準備としてコンピュータの作り出す乱数（疑似乱数）は、どの程度本当に
ランダムなのか、というようなことを少しばかり。
ゲームの中のサイコロ作りたいだけ、という人は読み飛ばしてもらってカマイマセん。（たぶん）
乱数を使うその１で実際に乱数を使うプログラムを作ってみます。
=======================================================================================

１　乱数関数

ゲームの中で、サイコロのマネをしたいときは、1〜6がランダムに出るようにしたいわけですが、
そんなランダムな数値が欲しい時に使うのが、乱数関数　rand です。

サイコロを作りたい、というような場合にはほとんど問題にはならないと思いますが、乱数関数は
少しやっかいな問題をはらんでいます。
例えば、
(1) randの仕様がどのように実装されているのかは、コンパイラによって異なります。→自分の使っている
コンパイラのrandの仕様を知っておく必要がある。
(2) randの仕様によっては、発生する乱数の品質が悪く、実用に耐えないことがある。
というようなことがあります。
発生する乱数の品質が悪いとは、得られる乱数がランダムではなく偏った結果になる、というようなことです。
そういえば以前、ゲーム中のサイコロが奇数と偶数が交互に出るゲームがあり、次の目が予見できるということで
回収されたゲームがありましたよね。極端に品質の悪い乱数はゲームのサイコロにも使えないわけです。
この乱数の品質の問題については、２．線形合同法のところで少しだけ掘り下げて説明してみます。（少しだけね）

ちなみに、LSI C-86、　Turbo C、　Borland C/C++　などでのrandの書式を一応書いておきます。

rand
【書式】 #include <stdlib.h>
　　　　　
　　　　　int rand( )

返り値　0〜32767の整数値の乱数を返します。　　　　　

乱数の最大値はLSI C-86ではstdlib.hの中で以下の通り　RAND_MAXとして定義されています。
#define RAND_MAX 32767


randで乱数を表示するプログラムです。

#include <stdio.h>
#include <stdlib.h>

main() {
int i,r;
for (i=0; i<10; i++) {
r=rand();
printf("%d:",r);}
}

rand.c

Borland C/C++ ver5.5でコンパイルしたプログラムでの実行結果ですが、毎回同じ乱数が
発生しています。

c:\bcc55\Bin>rand
130:10982:1090:11656:7117:17595:6415:22948:31126:9004:
c:\bcc55\Bin>rand
130:10982:1090:11656:7117:17595:6415:22948:31126:9004:
c:\bcc55\Bin>rand
130:10982:1090:11656:7117:17595:6415:22948:31126:9004:


以下はLSI C-86でコンパイルしたプログラムでの実行結果です。
Borland C/C++とは違う乱数列が生成されています。LSI C-86も毎回同じ乱数列が発生してますね。

D:\c>rand
16838:5758:10113:17515:31051:5627:23010:7419:16212:4086:
D:\c>rand
16838:5758:10113:17515:31051:5627:23010:7419:16212:4086:


毎回同じ乱数が発生するといことは、コンピュータの中で、小人君がサイコロ振ってる・・
わけはなく・・数学的に計算しているんだろうという推測ができるわけですが・・。
まあ、その通りです。

コンピュータは乱数を計算によって求めており、その方法はいくつかありますが一番代表的なのが
線形合同法と呼ばれる方法です。
というわけで、サイコロを振るように完全にランダムなわけではなく、コンピュータの計算
する乱数は規則性があり、このため疑似乱数と呼ばれています。



２　線形合同法

最も古くから、最もよく知られている疑似乱数アルゴリズムに線形合同法(Linear congruential generator : LCG)
があります。
他の疑似乱数生成アルゴリズムは数学的に理解するのが難しいのですが、この線形合同法のアルゴリズムは
以下のような漸化式であり、これならプログラミング言語への実装も容易で、処理速度も高速です。
このため、多くの場合、乱数発生アルゴリズムとして、線形合同法が使われてきましたが、欠点もあるわけです。
このアルゴリズムと欠点について、少し実例で検証しながら掘り下げてみます（とは言っても、ごく浅くですが）

線形合同法
Xn+1 =(A*Xn + C) mod M
なおM>A, M>C, A>0, C>=0　

例えば、A=2, C=1, M=7 とし、初期値を1とすると
X(0) =1
X(1) = (2*1+1) mod 7 = 3
X(2) = (2*3+1) mod 7 = 0
X(3) = (2*0+1) mod 7 = 1
X(4) = (2*1+1) mod 7 = 3
...

ということで、得られる結果は　1,3,0,1,3,0 ...の繰り返しとなり、たった周期3の乱数列になってしまいます。
これでは何の役にもたちませんね。

数学的にみると、Mで割った余りなので、周期は最大でもMにしかならないわけです。
が、せめて最大周期Mの乱数列を得たいですよね。というわけで、そんな条件があるのかというと
以下の条件を満たす時に最大周期Mが得られます。
・CとMが互いに疎
・A-1がMの持つ全ての素因数で割り切れる
・Mが4の倍異数の場合、A-1も4の倍数である。

このようなA,C,Mの組み合わせには、例えば　A=13, C=5, M=24があります
この組み合わせで作成した、乱数発生プログラム

krand1.c
#include<stdio.h>
#include<conio.h>
main(){
int x;
printf("%d:",x);
while(!kbhit()) {
x=(x*13+5)%24;
printf("%d:",x);
}
}


これを実行した結果の抜粋が以下の通りですが、
1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20　
の乱数列を繰り返します。0〜23まで全て１回生成しています。めでたし、めでたし・・って
こんなレベルじゃ、サイコロにも使えないですね。

............1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5
:22:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1:18:23:1
6:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1:18:23:16:21:14:19:12:17:1
0:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9
:2:7:0:5:22:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1
:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1:18:23:16:21:14:19
:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:
6:11:4:9:2:7:0:5:22:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:2
2:3:20:1:18:23:16:21:14:19:12:17:10:15:8:13:6:11:4:9:2:7:0:5:22:3:20:.......

ちなみに各種コンパイラでは、以下のアルゴリズムで実装されているようです。
（ようです・・、というのは自分で確かめたわけではないので）
long x;
int rand() { x=x*A+C; return(int)(x>>16)&32767; }

LSI-C A=1103515245, C=12345
TurboC 1.5 A=22695477, C=1
Visual C++ A=214013, C=2531011
Borland C++ A=22695477, C=1

この式の　x=x*A+C　は漸化式
Xn+1 =(A*Xn + C) mod 4294967296
と同じことになります。
xはlong型（32ビット）なので、最大とれる値は符号なしで4294967296です。
xがそれ以上の値になった場合はオーバーフローした部分は無視されるので、結果としてxは
4294967296で割った余りになります。
この線形合同法では下位ビットの周期性の欠点（周期が短い）があるため、さらに下位16ビットを捨てて、
上位16ビットを右シフトして乱数列を得ています。x>>16　の部分ですね。
そして32767とANDの論理演算して、符号付き16ビットの整数値として乱数を得ています。

下位16ビットを捨てるのは、下位ビットの周期が短く乱数として欠点があるためです。
例えば、上記のアルゴリズムの場合、AもCも奇数のため、
・xが偶数の場合　　偶数×奇数＋奇数　→奇数
・xが奇数の場合　　奇数×奇数＋奇数　→偶数
となり、最下位ビットは常に0と1が交互に現れることになります。これが下位ビットの周期性の欠点です。
このように下位ビットの周期性の欠点が現れないように、下位16ビットを捨てて乱数の品質を向上させて
います。


もうひとつ、初期値（乱数の場合シード＝種といいますが）が同じだと、毎回同じ乱数列が発生
してしまうという問題があります。上記で、rand.cの結果を見た通りです。
せっかく乱数を使ってランダム性をゲームに取り入れても、これでは毎回同じパターンになって
しまいます。
そのために、初期値（シード）を変えてやらねばなりませんね。
C言語では、大抵のコンパイラでシードを変えるための関数として　srand という関数が用意されています。

srand
【書式】 #include <stdlib.h>
　　　　　
　　　　　void srand(unsigned int seed)

発生する乱数列を初期化する。seedには0〜65535の整数を
与える。　　　　

Turbo CやBorland c/c++にはrandom( )という関数や、srandと同じような機能の関数として、randomize()
という乱数関数も用意されてます。

random(int num) はnum未満の整数をランダムに生成します。

randomizeは、Borland c/c++のstdlib.hには以下のようにrandomizeが定義されています。
#define randomize() srand((unsigned) time(NULL))

seedにtimeを与えて乱数列を初期化する関数になっていますね。

srandの使い方や、乱数列の初期化については乱数を使うその１に書いてます。


これらの問題は、どのプログラム言語であっても共通の話で、BASICの場合は、
パソコン活用研究５番街/乱数　にBASICでの乱数の同様の話を記載しています。

ということで、乱数を使う準備として線形合同法による乱数を使う場合、こういう欠点があることを
理解しておいたほうがいい場合があります、というお話でした。

◆線形合同法や、乱数の品質についての参考になるページ。
Linear congruential generator
線形合同法
良い乱数悪い乱数

ＴｏｐＰａｇｅ