色々な乱数 - ttki's diary

暗号について調べているうちに、乱数が必要になったのでしらべてみました。

乱数とは、5,2,7,3,7,9... のように次の数が予測できないバラバラな数。ですが、
コンピューターで乱数を得るときは、よっぽどのことがない限り、擬似乱数という計算によって
得られる乱数を使います。(計算によって得るので、予測ができる)
擬似乱数には周期があり、しばらく使っていると、また同じ数列が出てきてしまうことがあります。
この周期が長いほどいいといわれています。
ガイガーカウンタとかがあれば真の乱数が得られますけどね＾＾

ということで、C/C++ C# などで使えそうな擬似乱数アルゴリズムをまとめました。

・stdlib rand()

C/C++ 標準ヘッダのstdlib(cstdlib)内の rand()関数です。
　　0...RAND_MAX までの乱数を返します。
　　アルゴリズムは線形合同法なので、周期が短いのが欠点です。(2^32 ぐらい)

・C# System.Random.Next()

System.Random 内の Next()関数です。
　　C/C++ のrand() よりは多少いいものの、満足のいくものではありません。
　　どんなアルゴリズムを使っているかは、わかりませんでした。(ググってくださいww)

・メルセンヌ・ツイスター(MT)

　　自分の知っている中でもっとも周期の長い、メルセンヌ・ツイスター。
　　何と周期が 2^19937 - 1 もあります。
　　ほぼ、無限大です。(Mersenne Twister: A random number generator (since 1997/10))

・XorShift

意外と知られていない？ XorShift。その名の通り、XOR と SHIFT を使います。
　　周期も 2^128 - 1 と長く、いい感じです。(計算速度も速い)

・M系列

　　M系列という物もあります。メルセンヌ・ツイスターも中核部分はこれです。
　　面白そうなので、コードを探していたら Wikipedia に載っていました。(線形帰還シフトレジスタ - Wikipedia)

#include <iostream>
using namespace std;
// Wikipedia にあったものを少し改造
unsigned Mrand(int Max)//Max 最高値
{
	static unsigned int lfsr = ( 1 >> 1) ^ ( -(1 & 1u) & 0xd0000001u);
	if(lfsr != 1)
	{
		lfsr = (lfsr >> 1) ^ ( -(lfsr & 1u) & 0xd0000001u);
	}
	return lfsr % Max;
}

int main(void)
{
	int i=0;
	while(i<10000)
	{
		cout << Mrand(100) << endl;
		i++;
	}
	return 0;
}

乱数って面白いですね。今度、乱数のクラスを作ろうと思います。

それでは＾＾
　　