はじめに
みなさん、こんにちは！
今回は引き続き「指定した範囲の乱数を作る際の罠」の後編で、「解答編」となります。
- 指定した範囲の乱数を作る際の罠（前編）
- 指定した範囲の乱数を作る際の罠（後編）←いまここ
- 指定した範囲の乱数を作る際の罠（実戦編）
これまでのおさらい
乱数生成器を用いた場合の問題点
前編までのおさらいをします。3ビット（0, 1, 2, 3, 4, 5, 6, 7の8種類）の一様分布の値を出してくれる乱数生成器 random8() を使って、0〜2 の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 |
y = random8() % 3
このとき、各乱数値が3で割った余り（y）は：
| 乱数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| y | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 |
| y | 0 | 1 | 2 |
|---|---|---|---|
| 確率 | 3/8 | 3/8 | 2/8 |
このように値ごとに出現確率に差ができてしまい、乱数に偏りが生まれます。3ビットの乱数生成器だと、前回の2ビット乱数生成器に比べて偏りは小さくなっていますが、それでも完璧に均等にはなりません。つまり、乱数生成器のビット数（出せるパターン）が多ければ多いほど偏りは目立ちにくくなりますが、割り切れない余りが出ている限り、偏りをゼロにすることはできないのです。
正しい乱数を作る方法
乱数生成器を用いて偏りのない乱数を作るには
「じゃあ、3ビットの乱数生成器では0～2を正確に均等な確率で出すのは無理なの？」と思うかもしれませんが、実は方法があります。毎回問題になるのは「はみ出している部分」、つまり余りです。下の表だと、6と7が“余分”な部分です。
| 乱数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| y | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 |
この場合、6や7が出たら、その値は捨ててもう一度乱数を引き直します。シンプルですが、これで偏りを解消できます。
例えば、こんなイメージです。
| 乱数 | 0～5 | 6～7 |
|---|---|---|
| 確率 | 6/8 | 2/8 |
| 利用 | する | しない |
乱数生成のアルゴリズムを考える
整数の乱数生成器を用いた方法
これまで説明した内容を踏まえて偏りのない乱数を作るアルゴリズムを考えます。
たとえば「8通り(0～7)を出す乱数生成器から、0～2までの3種類の乱数が欲しい！」と決まっていれば判定も簡単ですが、実際には欲しい乱数の範囲や、乱数生成器のビット数が色々変わることもあります。そうなると、「どこまでが使ってよい範囲なのか」「どこからが余分なのか」をしっかり見極める必要が出てきます。
そこで、具体的に乱数値がどういう流れで判定されていくのかを順を追って確認してみましょう。
以下の表では、乱数生成器から出てきた値が、どのように“使っていい範囲”か“はみ出し”なのかが分かるように、計算過程を段階的に示しています。この流れを整理した下の表をご覧ください。
| a（元の乱数値） | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| b = a % 3 | 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 | F | F | F | F | F | F | T | T |
この「d = c + 3」が8を超えた場合（つまり e が true になる場合）は、余分な範囲にはみ出していることを示しており、このロジックをC言語で書くと、こんなイメージになります。
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;
}
流れとしては、ランダムな値を取り出し、そのまま使ってOKか、はみ出しているかを判定して、はみ出していればやり直します。do-while文を使えば、もう少しスッキリ書くこともできます。
乱数生成の注意点
一つ気を付けたいのが、「使う変数の型」や「値の大きさ」に関する問題です。たとえば RAND_MAX の値が非常に大きい場合や、(random - y + n) の計算結果が予想外に大きな値になる場合、signed long のような符号付きの変数を使っていると、計算結果がマイナス（負の値）になってしまうことがあります。
また、unsigned long のような符号なしの変数を使っていても、今度は「オーバーフロー」といって、値が大きすぎて最小値に戻ってしまい、意図しない小さい数字になってしまうこともあります。
たとえば、「signed short」（16ビット）の場合で RAND_MAX が 0x7fff だと、本来なら RAND_MAX + 1 は32768になるはずですが、16ビットの signed だと-32768になってしまい、if文の判定が正しく働かなくなることがあります。
つまり、アルゴリズム自体は単純でも、変数の型や取りうる値の範囲を意識しないと、思わぬバグの原因になります。実装するときは、変数の型やオーバーフローに十分注意しましょう。
実数の乱数生成器しか使えない場合
最後に、JavaScriptの Math.random() みたいに「0以上1未満の小数」しか出せない乱数生成器しか使えない場合はどうすればいいか？これも前編で話した通り、範囲指定でそのまま使うと偏りが出てしまいます。
この場合は、一度整数値に変換してから使うのがベターです。実際、疑似乱数は内部的にビット単位の整数をベースに作られています。たとえばJavaScriptなら、こう書くと0～32767の整数が得られます。
// 0〜32767 の整数を生成 let value = Math.floor(Math.random() * 0x8000);
この整数値を使って、先ほど説明したC言語の方法と同じく「余りが出たらやり直す」方式で偏りのない乱数を作ればOKです。
しっかりした乱数生成が用意されている場合
JavaならRandomクラスのnextInt(n)は上記で説明したアルゴリズムが採用されており、これまでの説明などを気にせず均等な乱数が作れます。
Random random = new Random(); int value = random.nextInt(n); // nは欲しい乱数の種類
さすがJavaです。
おわりに
乱数の生成方法には本当にいろいろな種類があります。有名な線形合同法（Linear Congruential Generator）は昔からよく使われているものの、乱数の「質」という点ではあまり高くありません。使いどころによっては問題になる場合もあるので、乱数のアルゴリズムについて少し調べてみるのもおすすめです。
高品質な乱数生成器としては「メルセンヌ・ツイスタ（Mersenne Twister）」が有名です。これは日本人が開発したもので、多くのプログラミング言語やツールでも採用されています。ただ、MTは自分で一から実装しようとするとちょっと大変かもしれません（ライブラリを利用するのが無難です）。
さて、次回はHSP3を使った、より実践的な乱数生成について紹介します。「指定した範囲の乱数を作る際の罠（実戦編）」もぜひご覧ください。
コメント