アルゴリズム

セカンドライフで綺麗な水面を作る

投稿日:


こんにちは!

セカンドライフ技術系 Advent Calendar 2015」の12月13日(日)担当の なたで です!

木曜日の記事(セカンドライフでジャンプ台を作る)に引き続いて…
今日は、セカンドライフで綺麗な水面を作ります。
けっこう長めなので、理由はともかく作りたいという方は、読み飛ばして、
途中に張ってある画像を保存して、テクスチャに使用していってください。


綺麗な波をつくるには・・・?

綺麗な水面を作るために、水の特徴を考えます。
水といえば波があるということです。

次のように2つの波の衝突を考えます

nami001
1つは、右から左へ流れる大きな波。

nami002
もう1つは、左から右へ流れる小さい波。

nami003
この2つが、衝突しても波と波とが重なり合って、消滅するということはありません。

つまり、波を作るためには、何面もの波を重ねると本物のように作ることができます。

よって、次のように作ると良いことが分かります。
「複数の面を重ねるようにおいて、模様に波(水面)のテクスチャを設定して、それぞれ別の方向へ動かす」

ここでさらに、波のテクスチャについて考えていきます。
単純に、波の模様のテクスチャだけを用意するだけでいいのでしょうか。

一度、波を実際に目で見た時を考えてみます。

nami004
波は、うねうねした形をもっており、うねうねに合わせた法線ベクトルがあります。
光は、波に当たっときに、法線を境に反射をします。
そして、反射した光が目に入った時に、白く輝いて見えることが分かります。

これらから、水面のテクスチャは、法線マップを作成する必要があるのです。
波の模様テクスチャから、法線マップを作ります。


特徴をまとめます

・複数の波を、合成する必要がある。
・それぞれの波を別方向でスクロールさせる。
・法線マップを使用して、リアルな反射を持たせる。


波のテクスチャを用意しよう

波のテクスチャは、シームレスなパーリンノイズが適切です。
シームレスというのは、上下左右につなぎ目のないという意味です。

具体的にシームレスなパーリンノイズを作る方法ですが、
実は検索してもなかなか見つかりませんでした。
一応、下記のようなツールを発見できたものの、登録が必要であるため、ダウンロードをしていません。
Procedural seamless noise texture generator

また、CLIP STUDIOというツールにも、パーリンノイズを作成する機能があるのですが、
こちらは、シームレスなパーリンノイズを作成できません。

そこで、シームレスなパーリンノイズを作成する簡易ツールを作りました。
nami_iconダウンロード

Javaの環境があれば、MacでもWindowsでも動きます。
ここでは、Windowsの環境での説明をしていきます。

【1】
「すべてのプログラム」→「アクセサリ」→「コマンドプロンプト」を実行します。

【2】
次のように、jarファイルがおいてあるディレクトリへ移動します。

cd C:\Users\xxx\Desktop\yyy

【3】
次のように実行してください。(-help と書けば使い方がでます。)

java -jar noise.jar -width 256 -height 256 -persistence 0.6 -lacnarity 2.5 -seed 123456

【4】
noise
これがパーリンノイズ(テクスチャA)です。

次に、このパーリンノイズを「高さ(ハイトマップ)」と見立てて
ノーマルマップを作成していきます。

ノーマルマップの作成ツールは、ハイトマップから自動でノーマルマップを作成できる
NormalMap-Online」を使用させていただきます。

【5】
normalmake
左側の箇所に画像ファイルのアイコンをドラッグ&ドロップして、
画像を読み込ませて、真ん中上部のスライダーで設定をしていきます。

【6】
NormalMap
Downloadを押せば、保存ができます。
これで、ノーマルマップ(テクスチャB)の完成です。

【7】
さらに、色用のテクスチャも用意します。
具体的には、透明度だけを持つ白色テクスチャです。
透明度には、パーリンノイズのテクスチャを使用します。

ovicon64
今回は、高機能な画像補正専用ツールの「オレンジビューア」を使用します。
このツールも、Javaをインストールする必要があります。

nami100
今回は、256×256のパーリンノイズなので、256×256の白色の画像を作成して
ビューアで読み込みを行います。

nami101
「色」→「アルファチャンネル」→「ファイルから読み込む…」で
さきほどの256×256のパーリンノイズを指定します。

nami102
これで、パーリンノイズのアルファチャンネルを持つ白い画像を作成できました。
「ファイルを名前を付けて保存」で、「xxx.png」と拡張子を「png」にして保存してください。
このソフトは、保存するときの拡張子によって自動で、その形式で保存されます。
pngにする理由は、透明度情報を持たせるためです。

noise2

完成した画像がこちらになります。(テクスチャC


テクスチャを設定しよう

立方体を作成して、薄くします。
これを水面にします。

nami200
色は水のような青色にします。

nami201
テクスチャの拡散反射の設定は「テクスチャC」を使います。

nami202
バンプマップの設定は、「テクスチャB」を使います。

nami203
鏡面反射の色成分の設定は「テクスチャA」を使います。

水平スケール、垂直スケールは、面の面積に合わせて、適度な値にしておきましょう。

nami301
この時点で、だいぶ水面のようになります。

nami302
あとは、2枚重ねておきましょう。
また、2枚目に関しては、あとでスクロールの関係上、180度回転させておきましょう。


スクロールさせる

波テクスチャを設定した重ねたオブジェクトの2つ、
それぞれにスクリプトを入れて、テクスチャをスクロールさせます。

スクロールは、かなり遅いほうがそれっぽいです。
スクリプトはこんな感じです。

start() {
	integer	mode	=	ANIM_ON | SMOOTH | LOOP;
	integer	face	=	ALL_SIDES;
	integer	sizex	=	0;
	integer	sizey	=	0;
	float	start	=	0.0;
	float	length	=	0.0;
	float	rate	=	0.005;
	llSetTextureAnim(0, face, 0, 0, 0.0, 0.0, 0.0);
	llSetTextureAnim(mode, face, sizex, sizey, start, length, rate);
}
default{state_entry(){start();}}

これを入れ込んで、実行させるとスクロールが始まります!

これで綺麗な水面の完成です!

テテーン!

これで私の「セカンドライフ技術系 Advent Calendar 2015」の記事は終わりです。
このような発表のきっかけを用意していただきました、sabroさんありがとうございました。

今回の記事を通して、3Dのテクスチャの作成や設定のテクニックに興味を持っていただければ幸いです・・・!

広告

RSA暗号の解説に出てくる数値の逆数のmod

投稿日: 更新日:


RSA暗号に紹介には、必ず次のような式がでてきます。

これ
inv_1
今日は、この式について解説します。
といっても・・・すみません。言い訳になりますが、
数学科出身ではなく、間違ったこというかもしれません。
それをふまえていただいて・・・解説させていただきます。

まず、m = (p – 1)(q – 1) とすると、式は次のようになります。
inv_2
さて、この式、意味が分かりますでしょうか。
ここで、mod mというのは、mで割った余りとなります。
つまり、式通りの意味を考えると x-1 =(1/x) を計算して、
m で割った余りが y となります。

しかし、よく考えてください。
言い忘れていましたが、x, y, m とも整数なのです。
x が整数の時点で、 x-1 =(1/x) という式を計算すると、
小数点付きの数値となり、小数点付きの数値に対して、
整数 m で割る?というよく分からないことが起きます。

じつは、これは逆数とはいってもモジュラ逆数と呼ばれるものなのです。
つまり、(1/x)みたいなことをしてはいけないのです。たぶん?

さて、モジュラ逆数となると、
上記のこれまでの式は一体どういう意味なのか。
実は、次のような意味になります。
inv_3
x と y を掛け算して、m で割った後の余りが 1 となります。

つまり、これまでの式は、
上記の計算結果を満たすような y を求める式なのです。

例題と行きましょう。
x = 3, m = 10 としたときの y は一体いくつでしょうか。
inv_4
これの y を求めてみましょう。

・・・

求める過程は、モジュラ逆数の紹介にある
拡張ユークリッド互除法最大公約数など、
いくつか値を求める必要がありまして、
ここでは省略します。

そして、答えを求めると y = 7 が導かれます。

実際に計算してみると・・・
inv_5
余りが 1 となり、ぴったりとなります。

なお、Java などでは、
この y の値を BigInteger の modInverse メソッドで計算することが可能です。

	public static void main(String[] args) {
		System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
	}

セカンドライフでHSVとRGBを相互変換してみよう

投稿日: 更新日:


HSVというのは、いわゆるHSV色空間のことです。
これは、Hue(色相)、Saturation(彩度)、Value(明度)を表しておりましています。

ご存知?の通りRGBの色空間から、HSVの色空間へ変換が可能でして、
これを利用すれば、今のRGBの色から、少し濃い色にしたり、逆に薄い色にしたり、
明るい色にしたり、暗い色にしたり、色相を反転させたり、いろいろできるわけです。

そしてこちらが、関数と逆関数です。スキニツカテイイヨー(あんまりテストしてないので・・・)

float	fractF(float x) { if(x >= 0) { return(x - (integer)x); } else { return(1.0 + (x - (integer)x));}}

vector getRgbFromHsv(vector hsv) {
	vector rgb = <hsv.z, hsv.z, hsv.z>;
	if(hsv.y > 0.0) {
		hsv.x *= 6.0;
		integer	i = (integer)hsv.x;
		float	f = fractF(hsv.x);
		if(i == 0) {
			rgb.y *= 1.0 - hsv.y * (1.0 - f);
			rgb.z *= 1.0 - hsv.y;
		}
		else if(i == 1) {
			rgb.x *= 1.0 - hsv.y * f;
			rgb.z *= 1.0 - hsv.y;
		}
		else if(i == 2) {
			rgb.x *= 1.0 - hsv.y;
			rgb.z *= 1.0 - hsv.y * (1.0 - f);
		}
		else if(i == 3) {
			rgb.x *= 1.0 - hsv.y;
			rgb.y *= 1.0 - hsv.y * f;
		}
		else if(i == 4) {
			rgb.x *= 1.0 - hsv.y * (1.0 - f);
			rgb.y *= 1.0 - hsv.y;
		}
		else if(i == 5) {
			rgb.y *= 1.0 - hsv.y;
			rgb.z *= 1.0 - hsv.y * f;
		}
	}
	return(rgb);
}

vector getHsvFromRgb(vector rgb) {
	float min = llListStatistics(LIST_STAT_MIN, [rgb.x, rgb.y, rgb.z]);
	float max = llListStatistics(LIST_STAT_MAX, [rgb.x, rgb.y, rgb.z]);
	vector hsv = <max - min, max - min, max>;
	if(hsv.x > 0.0) {
		if(max == rgb.x) {
			hsv.x = (rgb.y - rgb.z) / hsv.x;
			if (hsv.x < 0.0) {
				hsv.x += 6.0;
			}
		}
		else if(max == rgb.y) {
			hsv.x = 2.0 + (rgb.z - rgb.x) / hsv.x;
		}
		else {
			hsv.x = 4.0 + (rgb.x - rgb.y) / hsv.x;
		}
	}
	hsv.x /= 6.0;
	if(max != 0.0) {
		hsv.y /= max;
	}
	return(hsv);
}

default {
	state_entry() {
	}
	touch_start(integer total_number) {
		vector color	= <0.5, 0.7, 0.2>;
		vector hsv		= getHsvFromRgb(color);
		vector rgb		= getRgbFromHsv(hsv);
		llOwnerSay((string) hsv);
		llOwnerSay((string) rgb);
	}
}

色相は0→1が360度に対応していますので、
1を超えたら、また0→1へを繰り返します。

余談ですが、HLS色空間というものもあります。
こちらは少し、また計算式が変わってきています。詳しいことはこちらに。

以上


そしていつものおまけ
GLSL でおなじみの lerp や fract はよく使用するので、準備しておくと便利です。

float	fractF(float x) { if(x >= 0) { return(x - (integer)x); } else { return(1.0 + (x - (integer)x));}}
float	minF(float x, float xmin) { if(x > xmin) { return xmin; } else {return x;}}
float	maxF(float x, float xmax) { if(x < xmax) { return xmax; } else {return x;}}
vector	lerpV(vector A, vector B, float r) { return(A * (1.0 - r) + B * r); }
float	lerpF(float  a, float  b, float r) { return(a * (1.0 - r) + b * r); }
integer	lerpI(float  a, float  b, float r) { return((integer)(a * (1.0 - r) + b * r)); }
float	limitF(float x, float xmin, float xmax) { if(x > xmax) { return xmax; } else if(x < xmin) { return xmin; } else {return x;}}
integer	limitI(float x, float xmin, float xmax) { if(x > xmax) { return (integer)xmax; } else if(x < xmin) { return (integer)xmin; } else {return (integer)x;}}
float	normalizeF(float x, float xmin, float xmax) { return (x - xmin) / (xmax - xmin); }

セカンドライフで被らないチャンネルの作り方

投稿日: 更新日:


セカンドライフで物づくりしてますと、
llSay / llRegionSayTollListen 使ってコマンドで物を操作することありますよね。
そんなときに、どの出力チャネル使おうか迷うことありませんか。

例えばですが、適当に25135034 という数値を使ったとします。
これは恐らく他のものと被ることはないと思われます。
しかしですよ、このチャネルを使用した物を配るとします。

すると、もらった誰かがそのオブジェクトを操作しようとすると、
他にもらった誰かも、そのチャネルを受信してしまいます。
llListen でフィルターもかけられますが、
今回はチャネル番号をアバター固有の情報から作成する方法を紹介します。

ハッシュ関数 パンパカパーン

はい。以上です。
文字列から数値を作り出すあれです。

え?
SLって、16進数の文字列から数値へ変換する関数なんてないんじゃないの?

と思う方もいるかもしれませんが、実は (integer)”0x1234″ とすれば、
文字列を16進数の数値とみなして変換できるわけです。

とりあえず、keyから整数を変換できる関数を2種類作ってみました。

integer i;

/* 線形合同法によるハッシュ関数 */
integer getKey2HashLCGs(key src) {
	integer start_pos = 0;
	integer seed = 0x32123;
	integer hash = seed;
	// xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
	// 32ビットずつ取り出してハッシュを作成
	for(i = 0; i < 8; i++) {
		hash = hash * 0x1234321 + (integer)("0x" + llGetSubString(src, start_pos, start_pos + 3));
		start_pos += 4;
		if(	(start_pos == 8) ||
			(start_pos == 13) ||
			(start_pos == 18) ||
			(start_pos == 23) )	{
			start_pos++;
		}
	}
	return(hash);
}

/* SHA1+線形合同法によるハッシュ関数 */
integer getKey2HashSHA(key src) {
	integer start_pos = 0;
	integer seed = 0x32123;
	integer hash = seed;
	string buffer = llSHA1String((string)src);
	for(i = 0; i < 40; i += 4) {
		hash = hash * 0x1234321 + (integer)("0x" + llGetSubString(buffer, i, i + 3));
	}
	return(hash);
}

default {
	state_entry() {
	}
	touch_start(integer total_number) {
		key x;
		x = llGetOwner();
		llSay(0, (string)x
			+ "\n-> " + (string)getKey2HashLCGs( x )
			+ "\n-> " + (string)getKey2HashSHA( x )
			);
		x = llGenerateKey();
		llSay(0, (string)x
			+ "\n-> " + (string)getKey2HashLCGs( x )
			+ "\n-> " + (string)getKey2HashSHA( x )
			);
	}
}

恐らく上のgetKey2HashLCGsの方が、llSHA1Stringを使わない分、速いです。
お好きな方をどうぞ。

SHA1で作った関数は、引数の key を string に型を変更すれば、
何でも好きな文字列から32ビットの整数を取得できるようになります。

それと、両方の関数とも seed を引数に追加するこでとることで、
色々なアプリケーションでアバターごとに被らないチャンネル番号の作成を
利用できるようになると思います。

以上!

あ!
注意点として、
運が悪いと取得したチャンネル番号が「0」になることもあるかもしれませんので、
その点だけはお気を付け下さい・・・。

それを踏まえてこんな感じに使いましょう。

integer	i;
string	MY_PROJECT_NAME = "test tool";

integer getOriginalKey(string src) {
	integer start_pos = 0;
	integer seed = 0x32123;
	integer hash = seed;
	string buffer = llSHA1String((string)llGetOwner() + (string)src);
	for(i = 0; i < 40; i += 4) {
		hash = hash * 0x12344321 + (integer)("0x" + llGetSubString(buffer, i, i + 3));
	}
	if(hash == 0) {
		hash = 0x43019768;
	}
	return(hash);
}

default {
	state_entry() {
	}
	touch_start(integer total_number) {
		llSay(0, (string)MY_PROJECT_NAME
			+ "\n-> " + (string)getOriginalKey( MY_PROJECT_NAME )
			);
	}
}

オマケというメモ

線形合同法の乱数は、
X_n+1 = ( A * X_n + B ) mod M
という式から作成できます。

ここで、数値は32ビットの整数なので、
M = 0x100000000 = 4294967296 となります。
M の素因数分解は、2 ^ 32 です。
ここで A-1 が、Mの素因数分解の全て割り切れると、
この乱数の周期性が最大となることが知られています。
2 ^ 15 + 1 = 0x8001 = 32769 とかを設定すると、周期性が最大となります。

ですが、今回はハッシュ値を求めるためなので、
好きな値を入れても構わないです。
Bの値なんてどんな値がくるか分からないのですから。


追記 2015/3/25

listenに入ってくるチャンネル番号は
オブジェクトのUUIDなので、人でフィルターができないと思っていました。
ところが実はいい方法がありまして、これをある方から教えていただきました。
所有者を調べる llGetOwnerKey という関数があるのです。
たしかにこれを使えば、オブジェクトのUUIDだとしても誰が持っている
オブジェクトが発言したのか分かりますね!すっすごい!
&nbsLlGetOwnerKeこ

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

投稿日: 更新日:


みなさん、こんにちは。
さて、前回前々回にわたって、
指定した範囲の乱数の作成の仕方を書きました。
改めて奥が深いですね。

読み忘れた方のためにリンクしますっ(^o^)
指定した範囲の乱数を作成したい(前編)
指定した範囲の乱数を作成したい(後編)
指定した範囲の乱数を作成したい(実戦編)←いまここっ!


これまでの話では、
小さなより精度が低い乱数発生器を使用していたため、
実用上は、そんなに関係ないんじゃないかな。
と思う方も多いかもしれません。

今回の話はかなり短いですが、
実際の実用例を考えて、
乱数の落とし穴にはまっていきたいと思います。(^o^)丿

あなたは、ネットワークゲームを設計しています。
モンスターを倒すと、レアアイテムを落とします。
確率は、0.01%刻みで設定できるようにしたいです。
言語は、VC++、またはHSPを使用することとします。

ほら、ちょっと本当にありそうな雰囲気になってきましたよね。
さて、どのように設計するでしょうか、
VC++の乱数発生器だったら、みんな使ってるし大丈夫だろう。
乱数作成の高速化も考えて、 x = rand() % 10000 こんな感じにして、
で、if(x < 1000) で 10% みたいに計算しちゃおう。

では、実際にコードを書いてみましょう。
とりあえず、HSPが好きなので、HSPで書きます。
まず、 HSP には rnd(n) という関数があるのですが、
これはCで rand() % n という文章にすぎません。

#define multiplier 214013
#define addend 2531011

x = 1

goto *start

#defcfunc rnd2 int s
	x = x * multiplier + addend
	return (((x >> 16) & 0x7FFF) \ s)

*start

mes "HSPの rnd(n) は、余りを使用して乱数を切り出している。"
mes "HSPの rnd -> " + rnd(100) + " は"
mes "上記の rnd2 -> " + rnd2(100) + " と同じ。"

上記をふまえて、
乱数の値がどのように分布するか度数分布表を作ってみましょう。

size = 100000
dim bin, 10

repeat size
	x = rnd(10000)
	bin(int(x / 1000))++	
loop

repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

実行すると、

範囲 回数
[ 0, 1000) 12401
[1000, 2000) 12176
[2000, 3000) 11618
[3000, 4000) 9079
[4000, 5000) 9088
[5000, 6000) 9107
[6000, 7000) 9150
[7000, 8000) 9048
[8000, 9000) 9316
[9000,10000) 9017

つまり、10%を作るつもりが、12%になってしまいます!!
さらに、if(rnd(10000) < 3000) で 30.00% みたいに計算しちゃおうと思うと 36%になります。

棒グラフを作ると分かりやすい。
histogram

そんなこんなで、
今回は、ちょっと身近に感じそうな話を作ってみました。
みなさん、乱数には十分に気を付けましょう!

ちなみに、HSPの機能の中でより正しい乱数を作りたい場合は、
これまでの話をふまえると下のような感じ。(色々と追加しました。)

#module

#defcfunc rnd15 int s
	// 15ビットの実数の乱数を作成
	return int(((double(rnd(0x8000))) / 0x8000) * s)

#defcfunc rnd30 int s
	// 30ビットの実数の乱数を作成
	return int(((32768.0 * rnd(0x8000) + rnd(0x8000)) / 0x40000000) * s)

#defcfunc rnd52 int s, local a
	// 52ビットの実数の乱数を作成
	a = double(rnd(0x8000))
	repeat 3
		a *= 32768
		a += rnd(0x8000)
	loop
	return int(a / 1152921504606846976.0 * s)

#defcfunc rnd4 int s, local a, local b
	// 繰り返して範囲外は捨てる
	repeat
		a = rnd(0x8000)
		b = a \ s
		if(a - b + s <= 0x8000) {
			break
		}
	loop
	return b

#global

font "MS ゴシック", 12
pos 5, 5

// 作成する乱数の範囲によって、
// 乱数のビットを大きいものを選ぶか、
// 上記の rnd4() を利用するといいです。

randomize
size = 1000000

mes "通常版"
dim bin, 10
repeat size
	x = rnd(10000)
	bin(int(x / 1000))++	
loop
repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

mes "工夫したもの"
dim bin, 10
repeat size
	x = rnd15(10000)
	bin(int(x / 1000))++	
loop
repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

mes "誤差が少ない"
dim bin, 10
repeat size
	x = rnd30(10000)
	bin(int(x / 1000))++	
loop
repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

pos 200, 5

mes "最も誤差が少ない"
dim bin, 10
repeat size
	x = rnd52(10000)
	bin(int(x / 1000))++	
loop
repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

mes "正しい乱数"
dim bin, 10
repeat size
	x = rnd4(10000)
	bin(int(x / 1000))++	
loop
repeat 10
	mes strf("[%5d ,%5d) ... %5d回", (cnt * 1000), ((cnt + 1) * 1000), bin(cnt))
loop

上記の「正しい乱数」のアルゴリズムについては、下で紹介していますが、前編から読むとより勉強になるかもしれません。
指定した範囲の乱数を作成したい(後編)

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

投稿日: 更新日:


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

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

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

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

投稿日: 更新日:


みなさん。
指定した範囲の乱数を作りたい場合は、どうしているでしょうか。
今日は、指定した範囲の乱数生成の小ネタを紹介します。

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

さて、例えばサイコロを作りたいと思います。
サイコロの目は1~6ですね。

そして乱数生成器が用意されていると思います。
この乱数生成器は、4バイト=32ビットの一様分布する整数値が出力されるもので、
random32()と関数を呼び出せば、出力されるものとします。
( random32() は、C言語の乱数 rand()と似たような関数だと思ってください。 )

どのような、コードを思い浮かべるでしょうか。
恐らく最も簡単なコードは、次のようなコードです。

サイコロの目 = random32() mod 6 + 1
(mod 6 は、6で割った余りの数とします)

はい。
たしかに、「random32() mod 6」で0~5の範囲の値を作成して、
1を足して、1~6の乱数が出ると思います。

今度は、実数の乱数生成器で、サイコロを作る話です。
この実数の乱数生成器は、64ビットのdouble型の実数を作成するもので
[0, 1) = {x | 0 ≤ x < 1} の乱数、つまり0以上、1未満の乱数を得ることができます。
randomf()と関数を呼び出せば、出力されるものとします。
( randomf() は、JavaScript の Math.random() と似たような関数だと思ってください。)

この場合も、どのような、コードを思い浮かべるでしょうか。
最も簡単なコードは、次のようなコードです。

サイコロの目 = floor(6 * randomf()) + 1
(floor() は、床関数です)

はい。
これも、たしかに、「6 * randomf()」で[0, 6)の乱数を作成して、
床関数で0~5の整数値にして、1を足すことで、1~6の乱数が出力されます。

簡単で、すぐに乱数が欲しいという目的であれば、これまでの話は正しいと思います。

ただし、知っている方も多いかと思いますが、
本当に本当に正確な乱数を欲しい場合は、問題があるコードなのです。
何が問題なのでしょうか。

まずは、整数の乱数を使用した場合です。

問題を分かりやすく考えるため誤差を大きくしましょう。
2ビットの乱数生成器(0~3までの4パターンの数字を出力する)random4()が用意されており、
ここから0~2まで、3パターンの数字を出力する乱数を作り出したいと思います。

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

乱数値 0 1 2 3
確率 1/4 1/4 1/4 1/4

それでは、先ほど同じような考え方で
y = random4() mod 3
を計算してみるとどうでしょうか

乱数値 0 1 2 3
y (3で割った余り) 0 1 2 0

つまり、出力される0~2の値は、
「random4() mod 3」の計算で作成すると、
下記のように0が出る確率が高くなってしまうのです。

残念な乱数出力結果1

y 0 1 2
確率 2/4 1/4 1/4

今度は、実数の乱数生成器の話です。
「 floor(6 * randomf()) + 1」とサイコロを作成した場合、同じように偏りが生まれる問題があるのです。
浮動小数点型に限界があるのです。
一様乱数な0から1未満の浮動小数点を作成したとしても、仮数部のビット数分の種類しかないのです。
(ただ、出力値がdouble型ならば、
先ほどの、randomf()は、約2^52ビット=9007兆の数字のパターンを持っています。
これだけ大きければ実際は、問題はないと思います。)

分かりやすく考えるため、しょぼい乱数生成器を使用します。
2ビット整数の乱数生成器の話と同じように仮数部が、
2ビットの実数の乱数生成器randomf4()を使用して、0~3の整数を作ってみましょう。
(randomf4()は、0から1未満を生成するが、0.00 0.25 0.50 0.75の4パターンしか出力されない)

この仮数部2ビットの実数乱数生成器の性能を表にまとめます。

乱数値 0/4 1/4 2/4 3/4
確率 1/4 1/4 1/4 1/4

それでは、先ほど同じように
y = randomf4() * 3
z = floor(y)
を計算してみるとどうでしょうか

乱数値 0/4 1/4 2/4 3/4
y (3倍した) 0/4 3/4 6/4 9/4
z (床関数) 0 0 1 2

つまり、出力される0~2の値は、
「random4() % 3」の計算で作成すると、
0が出る確率が高くなってしまうのです。

残念な乱数出力結果2

y 0 1 2
確率 2/4 1/4 1/4

では、どうすればいいんじゃあって思うかもしれません。
まあ、普通に使用する分は、最初の話があったような方法で十分です。
ただし、使う人を選ばない乱数生成器を作成したいとか、
どのような乱数生成器の性能でも、しっかりした乱数を作りたいといった場合は、
工夫して上記の問題を解決する必要があります。

指定した範囲の乱数を作成したい(後編)へ続くッ!!!