はじめに
みなさん、こんにちは。
今日は、昨日の続き、「指定した範囲の乱数を作りたい」を続きに話していきたいと思います。
というか、解答編みたいな感じです。
指定した範囲の乱数を作成したい（前編）
指定した範囲の乱数を作成したい（後編）←いまここっ！
指定した範囲の乱数を作成したい（実戦編）
これまでのおさらい
乱数生成器を用いた場合の問題点
それでは、ちょっとおさらいをしながら進めていきます。
今回は、3ビット（0, 1, 2, 3, 4, 5, 6, 7 の計8種類の数値）の
一様分布の値を出力する乱数生成器random8()を利用して、
0～2の3種類の数字を出力してみましょう。
この3ビットの乱数生成器random8()の性能を表にまとめます。
| 乱数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 確率 | 1/8 | 1/8 | 1/8 | 1/8 | 1/8 | 1/8 | 1/8 | 1/8 |
それでは、前回と同じように3で割った余りを使用します。
y = random8() mod 3
乱数に対して、3で割った余りを求めて
| 乱数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| y (3で割った余り) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 |
確率をまとめると、
| y | 0 | 1 | 2 |
| 確率 | 3/8 | 3/8 | 2/8 |
やはり、前回の2ビット乱数発生器と同様にだめでした。
まあ、ただ2ビットの乱数発生器に比べて誤差は減っています。
乱数発生器のビット数が大きいほど誤差は少なくなるようですね。
正しい乱数を作る方法
乱数生成器を用いて正しい乱数を作る
では、3ビットの乱数生成器では、
当確率で、0から2の数字を出力することができないのでしょうか。
いいえ、出来ます。
気付いている人も多いかと思いますが、
毎回、問題になっているのは「はみ出している」部分なのです。
「はみ出している」というのは、下記の黄色の箇所です。
| 乱数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| y (3で割った余り) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 |
つまり、3ビットの乱数生成器で0～7の値が出力されるが、
そのうち6か、7が出た場合は、
もう1度、3ビットの乱数生成器で出力するのです。
もちろん、計算コストが上がります。
例えば、3ビットの乱数生成器では
| 乱数 | 0～5 | 6～7 |
| 確率 | 6/8 | 2/8 |
| 利用 | する | しない |
それぞれの数字を出力する確率は上記のようになり、
6～7という数字が、2/8の確率で出力され、
もう1度計算する必要が出てくるのです。
しかも、次の乱数も、6~7なら、また乱数作成の計算が必要です((+_+))
乱数生成のアルゴリズムを考える
整数の乱数生成器を用いた方法
次はアルゴリズムの話に移ります。
出力された値が、6~7かどうかはどのように判断したらいいでしょうか。
上記のように、「0～7の8種出力する乱数から、0~2までの3種類の乱数が欲しい！」
と決め打ちされているならば簡単ですが、
乱数のビット数、いくつ未満の数字が欲しいか、いくつもの場合が考えられます。
でも、色々な場合とか考えると、大変なので、やっぱり簡単な乱数で勉強しましょう。
とりあえず、次の表を見てください。
| 乱数値 a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| b=a mod3 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 |
| c = a – b | 0 | 0 | 0 | 3 | 3 | 3 | 6 | 6 |
| d = c + 3 | 3 | 3 | 3 | 6 | 6 | 6 | 9 | 9 |
| e = d > 8 | false | false | false | false | false | false | true | true |
ピーン(^o^)っときませんか？
上の表に出てきている
3は、必要な乱数の種類、0~2までの3種類の3です。
8は、3ビットの乱数発生器の性能、2の3乗の8です。
もうお分かり頂けたと思います。
ちょっと、C言語で上記の考え方で、乱数を作ってみましょう。
C言語では、乱数をrand()で出力するのですが、
この出力する範囲は「0～RAND_MAX」となり、「RAND_MAX + 1」種類の数字を出力します。
int TRUE = 1;
unsigned long n = 3; // 欲しい乱数の種類
unsigned long y = 0; // 出力値
unsigned long random = 0;
while(TRUE) {
random = rand();
y = random % n;
if( ( random - y + n ) > (RAND_MAX + 1) ) {
continue;
}
break;
}
まあ、とりあえず説明にあったような流れで、無理やり書いて、
上記のようなコードになりました。
do文を利用するともっとすっきり書けます。
乱数生成の注意点
実は1つだけ落とし穴があります。
それは、RAND_MAXの値が非常に大きい場合や、
( random – y + n )の値が実は巨大な数字の場合です。
signed long などで計算している場合は、負の値になってしまいますし
unsigned longを使用していたとしても、オーバーフローして、小さな値になってしまう可能性があります。
例として、「signed short」16ビットの正負の範囲を表す整数値を使用しており
さらに、RAND_MAX は 0x7fff の場合、RAND_MAX + 1 は -32768 となり負になってしまいます。
そのため、IF文の結果が思った結果と異なる場合があります。
アルゴリズム自体は分かったと思いますので、
上記の点だけ注意して、値がおかしくならないように設計して下さい。
実数の乱数生成器を用いた方法
最後にJavaScriptのように、0以上、1未満の数字を出力する
Math.random()しかない場合は、どうすればいいでしょうか。
この時も、前編で話したように同様の問題を抱えています。
この場合も、一度整数に戻すしかありません。
疑似乱数は、通常ビット単位で作成されます。
（これまでで話したように、任意の数までの乱数を作るのは面倒だからです。）
そのため、Math.random() を作成している元となる乱数も
元々は、あるビット長の整数を元にしていると思われます。
この場合は、Math.floor(Math.random() * 0x8000) とすれば、
0から32768未満の整数値を、均等な確率で出力します。
あとは、この整数値を利用して、上のC言語で説明したように作成すれば
しっかりとした乱数が作成できます。
ちなみに、Javaの場合は、RandomクラスのnextInt(n)を使用すれば、問題ありません。
さすがJavaです。速度も速いですし。
とりあえず、「指定した範囲の乱数を作成したい」はここで終わりです。
おわりに
話は、少し変わりますが乱数は作成する方法がたくさん考案されてます。
疑似乱数の質とか考えると、よく利用される線形合同法はマズいです。
利用する目的にもよると思いますが、
乱数の種類などを勉強しておくといいかもしれません。
メルセンヌ・ツイスタは、日本人が開発したもので、乱数の質が高いです。
（ただ、MTは、簡単に自分の手で実装できないのがデメリットがあります＞＜）
続きは、HSPを使ったより実践的な話です。
指定した範囲の乱数を作成したい（実戦編）
コメント