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

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

それでは、ちょっとおさらいをしながら進めていきます。
今回は、3ビット(0, 1, 2, 3, 4, 5, 6, 7 の計8種類の数値)の
一様分布の値を出力する乱数生成器random8()を利用して、
0~2の3種類の数字を出力してみましょう。

この3ビットの乱数生成器random8()の性能を表にまとめます。

乱数値01234567
確率1/81/81/81/81/81/81/81/8

それでは、前回と同じように3で割った余りを使用します。
y = random8() mod 3

乱数に対して、3で割った余りを求めて

乱数値01234567
y (3で割った余り)01201201

確率をまとめると、

y012
確率3/83/82/8

やはり、前回の2ビット乱数発生器と同様にだめでした。
まあ、ただ2ビットの乱数発生器に比べて誤差は減っています。
乱数発生器のビット数が大きいほど誤差は少なくなるようですね。

さて、では3ビットの乱数生成器では、
当確率で、0から2の数字を出力することができないのでしょうか。
いいえ、出来ます。

気付いている人も多いかと思いますが、
毎回、問題になっているのは「はみ出している」部分なのです。
「はみ出している」というのは、下記の黄色の箇所です。

乱数値01234567
y (3で割った余り)01201201

つまり、3ビットの乱数生成器で0~7の値が出力されるが、
そのうち6か、7が出た場合は、
もう1度、3ビットの乱数生成器で出力するのです。

もちろん、計算コストが上がります。
例えば、3ビットの乱数生成器では

乱数0~56~7
確率6/82/8
利用するしない

それぞれの数字を出力する確率は上記のようになり、
6~7という数字が、2/8の確率で出力され、
もう1度計算する必要が出てくるのです。
しかも、次の乱数も、6~7なら、また乱数作成の計算が必要です((+_+))

さて、次はアルゴリズムの話に移ります。
出力された値が、6~7かどうかはどのように判断したらいいでしょうか。
上記のように、「0~7の8種出力する乱数から、0~2までの3種類の乱数が欲しい!」
と決め打ちされているならば簡単ですが、
乱数のビット数、いくつ未満の数字が欲しいか、いくつもの場合が考えられます。
でも、色々な場合とか考えると、大変なので、やっぱり簡単な乱数で勉強しましょう。

とりあえず、次の表を見てください。

乱数値 a01234567
b=a mod301201201
c = a – b00033366
d = c + 333366699
e = d > 8falsefalsefalsefalsefalsefalsetruetrue

ピーン(^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を使ったより実践的な話です。
指定した範囲の乱数を作成したい(実戦編)

関連記事

  • 指定した範囲の乱数を作成したい(前編)指定した範囲の乱数を作成したい(前編) みなさん。 指定した範囲の乱数を作りたい場合は、どうしているでしょうか。 今日は、指定した範囲の乱数生成の小ネタを紹介します。 指定した範囲の乱数を作成したい(前編)←いまここっ! 指定した範囲の乱数を作成したい(後編) 指定した範囲の乱数を作成したい(実戦編) ・ さて、例えばサイコロを作りたいと思います。 サイコロの目は1~6ですね。 そして乱数生成器が用意されてい […] Posted in アルゴリズム
  • JScriptバッチ処理用ライブラリ 20130825公開JScriptバッチ処理用ライブラリ 20130825公開 私のサイトで公開している JScriptバッチ処理用ライブラリのバージョン「20130825」を公開しました。 主な内容は、JavaのString.formatを、JScriptでも使用できるようにするというものです。 JavaのString.formatは、大体はCのsprintfと似ているのですが、もっといろいろできます。 ただ、今回JScriptで使用できる […] Posted in ライブラリ制作
  • 指定した範囲の乱数を作成したい(実戦編)指定した範囲の乱数を作成したい(実戦編) みなさん、こんにちは。 さて、前回、前々回にわたって、 指定した範囲の乱数の作成の仕方を書きました。 改めて奥が深いですね。 読み忘れた方のためにリンクしますっ(^o^) 指定した範囲の乱数を作成したい(前編) 指定した範囲の乱数を作成したい(後編) 指定した範囲の乱数を作成したい(実戦編)←いまここっ! これまでの話では、 小さなより精度が […] Posted in アルゴリズム
  • Fizz-Buzz問題を解いてみた!Fizz-Buzz問題を解いてみた! 今日はネットでFizz-Buzz問題という面白そうなものを見つけた。 Fizz-Buzz問題 はじめに どうしてプログラマに・・・プログラムが書けないのか? http://www.aoky.net/articles/jeff_atwood/why_cant_programmers_program.htm かなりの試行錯誤の末に、コードを書こうともがいている人たちとい […] Posted in アルゴリズム
  • HSPでsleep sortを実装してみたHSPでsleep sortを実装してみた この前、sleep sort(元ネタ)というのを知って、 HSPでSetTimerでそれっぽいのを作ったのですが、 掲示板のwait0000さんが作ったのと普通に被ってしまったので寝かせてました。 うん。 でも5月に1度も投稿してなかったので、投稿します(^^) 実用性とかそういうのなしで、発想力がすごい。 //sleep […] Posted in アルゴリズム
  • Bresenhamアルゴリズムで線分の計算は早いのかなBresenhamアルゴリズムで線分の計算は早いのかな 以前、直線を描くのにこんなのを作った。 特に工夫点もない、素直な方法である。 #module "linem" #deffunc line2 int line_x1,int line_y1,int line_x2,int line_y2 line_xabs = abs(line_x1-line_x2) line_yabs = […] Posted in アルゴリズム
  • 男は黙ってボゴソート男は黙ってボゴソート 男は黙ってボゴソート! 馬鹿らしいソートなんだけど、アイデアが面白い! しかし、O(n*n!)ってすごいですね。 下のサンプルはとりあえずWikipediaにかいてあったトランプの例をやってみました。 #include <stdio.h> #include <stdlib.h> #include <string.h> […] Posted in アルゴリズム
  • 3DCGの座標系の紹介3DCGの座標系の紹介 はじめに こんにちは! 今日は、3DCGにかかせない座標系の話をするよ! 座標系の種類 では、オブジェクトから画面まで、どのような座標系があるか紹介します。 . 座標系一覧 呼び方が変わりますが、細かく分けると次のような流れになっています。 各々の変換とよばれている部分が行列を掛け算することに相当します。 座標はベクトルとし、このベクトルに座標を掛け算して、次の座標系 […] Posted in アルゴリズム
  • RSA暗号の解説に出てくる数値の逆数のmod RSA暗号に紹介には、必ず次のような式がでてきます。 これ 今日は、この式について解説します。 といっても・・・すみません。言い訳になりますが、 数学科出身ではなく、間違ったこというかもしれません。 それをふまえていただいて・・・解説させていただきます。 まず、m = (p - 1)(q - 1) […] Posted in アルゴリズム
  • 麻雀の待ち判定問題 part1麻雀の待ち判定問題 part1 昨晩は、話題の「あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定」をやってました。 意外に時間がかかって大変でした。 こんな時期にやるんじゃなかった。眠たい。(p_-) 正直3時間ちょっとかかってしまいました。 テンパイ(1113335558888)とチートイツ判定なしです。 以下は、作った後の感想です。 3時間が短いと感じまし […] Posted in アルゴリズム