C言語でボゴソート（無作為に要素をうめてソートできているか確認をくりかえすソートアルゴリズム）を実装したときにrand関数を使用して 、その際に今までよりrand関数について調べたのでそれについてまとめていこうと思います。

1. rand関数とは

rand関数はC言語に標準装備されている擬似乱数を生成する関数です。引数をとらず戻り値として0~RAND_MAXの間の擬似乱数を返します。（RAND_MAXはstdlib.h内で定義されている値） この関数では「線形合同法」といわれるアルゴリズムを用いて擬似乱数を生成しています。「線形合同法」とは

\[X_n+1 = (A \times X_n+B)modM\]

という漸化式で与えられます。（A、B、Mは定数で処理系に依存する） C言語での実装

double Uniform( void ){
	static int x=10;
    int a=1103515245,b=12345,c=2147483647;
    x = (a*x + b)&c;
 
    return ((double)x+1.0) / ((double)c+2.0);
} このコードは $a=1103515245,b=12345,m=2^{31}$ に対応

2. 擬似乱数の精度

C言語で乱数を生成する際に最も簡単な方法は先ほどあげたrand関数を用いることです。 しかし、この線形合同法という考え方は計算が簡単で高速ですが以下のように品質に問題があるといわれています。

  • 周期が $2^{31}$ と短い

これは上の式の定数Mの値

  • 乱数の最下位ビットは0と1の繰り返しで偶数と奇数が交互に生成される。

（下位ビットを捨てて品質をあげているものもある）

  • 多次元分布の均等性がない

一個ずつ乱数を用いればランダムな値がとれるが、いくつかの組に対して用いると分布に特定の構造がある。 （よく分からなかったけど漸化式で次の値が決まってしまうから？）

3. 精度のよいアルゴリズム

精度のよい乱数とはどんなものがあるのか気になり調べてみた

  • メルセンヌツイスタ

周期は $2^{219937}-1$

高次元に均等分布する（623次元まで保証）

  • Xorshift

周期は $2^{128}-1$　

計算がビットシフトとXORだけなので非常に高速

###まとめ rand関数の品質がよくないものということを知らなかったので驚きました。式を見ただけでは周期や乱数の分布などはわからないので今回実装したボゴソートを利用したりして実行時間を比較したり、分布をグラフにしてみてわかりやすいようにしたりしてみたいです。また、メルセンヌツイスタやXorshiftのアルゴリズムについて調べてみたいと思います。

参考文献