指定した範囲の乱数を作成したい(後編)

投稿日: 更新日:

みなさん、こんにちは。
今日は、昨日の続き、「指定した範囲の乱数を作りたい」を続きに話していきたいと思います。
というか、解答編みたいな感じです。

指定した範囲の乱数を作成したい(前編)
指定した範囲の乱数を作成したい(後編)←いまここっ!
指定した範囲の乱数を作成したい(実戦編)

それでは、ちょっとおさらいをしながら進めていきます。
今回は、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を使ったより実践的な話です。
指定した範囲の乱数を作成したい(実戦編)

広告

コメントをどうぞ(承認された後に公開されます。メールアドレスの記入は自由ですが、記入した場合でも一般公開されることはありません)

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中