(cache) 乱数生成アルゴリズム

乱数生成アルゴリズム

標準ライブラリの乱数の雲

　乱数の雲とは、乱数の分布の度合いを３次元の分布図で表したものです。
　標準ライブラリの乱数の雲をみてみましょう。驚きの結果です。

これのどこが乱数ですか？
これは直線といいませんか？
あえて言おう、カスであると！
　いままで結構、srand() と rand() は信用していたのですが、裏切られた感じで、ちょっとショックです。
　というわけで、このページを作りました。

　ちなみに、「rand()は最初のデータを捨てなければならない」という故事があります。
　srand() の後のデータを１００個捨てた状態での乱数の雲（１００歩奥に進んだ時の３次元分布）は、こうなります。

多少捨てたところで、気休めです。
偉い人にはそれが分からんのですよ。
　１０００個ほど捨てると、なぜか筋っぽい感じが復活します。所詮はカスであります。
１０００歩奥に進んだ時の乱数の雲

乱数の雲を生成するプログラム

　以下の様なプログラムで、生成しています。

int i, j;
int H = 32767 / height;
for( i = 0; i < width; i++ )
{
    srand( i );
    for( j = 0; j < 1000; j++ ) rand(); // 100個捨てる
    for( j = 0; j < 50; j++ )
    {
        dc.SetPixel( i, rand() / H, RGB( 255 - j * 5, 0, 0 ) );
    }
}

　３２７６７はrand()の最大値です。heightで割って比率にしています。
　横軸が乱数の種、縦軸が乱数、奥行きが乱数生成の回数となる、３次元の分布図をSetPixelで描画します。
　奥に行くにしたがって暗くなるようにすることで、２次元の絵において奥行きを表現しています。

あゆしゃの乱数の雲

　まずは、この雲を見てください。

直線どころか、周期性も見受けられません。
通常の乱数の３倍の分布です！

あゆしゃの乱数生成アルゴリズム

　以下のプログラムで、乱数を生成しています。
　XORがいっぱいありますが、全然、難しいことは行っていません。


UINT arand( UINT r )
{
    r ^= ( 0x65AC9365UL >> ( r & 3 ) );
    r ^= ( r >> 4 ) ^ ( r >> 3 ) ^ ( r << 3 ) ^ ( r << 4 );
    return r;
}

　本当に簡単ですね。３０分で作った簡単なアルゴリズムです。
最初の１回目は筋ができますが、捨てています。それは内緒です。
１０００回ほど実行すると、種＝乱数というケースの出現率が高いことが分かりますが、内緒です。
　たったこれだけであれだけの分布を得られるとすれば、十分に実用的といえるでしょう。

　グローバル変数を持つ必要がないように、毎回、前回値をもらうようにしてみました。
　それが初回である場合、まさに種となります。
　種が連続する数列である場合も、実用的な乱数を生成します。
　「AC9365」というのは、ビットを満遍なく配置した数字です。
　これを右シフトしていますが、これがないと、最初に強い筋がでるようになります。
右シフトがない場合の乱数の雲
　１０回ほど捨てれば筋が消えるので、捨てることを前提として使用するならば、シフト部分は必要ありません。

　あとは、適当にビットをかき回しているだけです。
　暗号化のアルゴリズムもそうですが、単純に、ビットをかき回すだけです。
　暗号化は元に戻らなければならないのに対して、乱数は生成するだけですから、乱数のほうが簡単といえます。

　難しいことを考えなければ、な～んにも、難しいことはありません。

「アルゴリズムは難しさの道具ではないわ」
ララァがそう言っていました。

あゆしゃの乱数生成クラス

　arand をクラスにまとめました。ただ、それだけですが。

class CARand
{
private:
    UINT r;
public:

    CARand()
    {
        Init( 0 );
    }

    CARand( UINT seed )
    {
        Init( seed );
    }

    void Init( UINT seed )
    {
        r = seed;
        for( int i = 0; i < 20; i++ ) arand();
    }

    UINT arand()
    {
        r ^= 0x65AC9365UL;
        r ^= ( r >> 4 ) ^ ( r >> 3 ) ^ ( r << 3 ) ^ ( r << 4 );
        return r;
    }
};

　初期化を行うことを前提としているため、シフトを省略しています。
　これを使用する例

int H = ( int )( 0xFFFFFFFFUL / ( UINT )height );
for( i = 0; i < width; i++ )
{
    CARand ar( ( UINT )i );
    for( j = 0; j < 50; j++ )
    {
        dc.SetPixel( i, ar.arand() / H, RGB( 0, 0, 255 - j * 5 ) );
    }
}

　この出力結果

乱数はあと１０年は戦えます。

あゆしゃの乱数生成アルゴリズム VS メルセンヌ・ツイスター

戦闘結果を見る

一つ前に戻る

メインページへ戻る