K&Rを読もう(26) randの写経。

GCC

疑似乱数がこんなに単純なアルゴリズムで出来ているとは・・・。もっと単純にしてみた。


適当なa、p、qを選んで、

ap + q = a'

とする。次にa'をaに代入する。で、余りを取る。

後はニュートン法のように繰り返すだけ。

#include <stdio.h>
#include <stdlib.h>

unsigned long int next = 1;
#define RAND_MAX_COPY 10

int rand_copy(void)
{
    next = next * 3 + 1;
    return (unsigned int) next % RAND_MAX_COPY;
}

int main(void)
{
    int i;
    for (i = 0; i < 10; i++)
        printf("%10d %d\n", next, rand_copy());
    exit(EXIT_SUCCESS);
}

わかりやすいように、nextを3倍して1を足して10の余りを取りました。

実行結果は・・・。

         4 4
        13 3
        40 0
       121 1
       364 4
      1093 3
      3280 0
      9841 1
     29524 4
     88573 3

0,1,3,4しか出ませんね。。。。(汗

  • 桁が溢れたときに、nextが0になってしまう値を選ぶと一定の値になってしまう。
  • K&Rでは、next % RAND_MAXを,next / (RAND_MAX * 2) % RAND_MAXとしてた。理由がイマイチわからん。
    • わかった。Wikipediaより引用。「十の位から十万の位までを採用することとする。」下の桁を切捨てるために割ったのか!!おぉぉぉぉ。わかった!!
    • 「0,1,3,4しか出ない」というのが解消されそうだ。

10の位を採用してみる。

         4 0
        13 1
        40 4
       121 2
       364 6
      1093 9
      3280 8
      9841 4
     29524 2
     88573 7

おぉぉぉぉぉ。疑似乱数だ!!

疑似乱数の簡単な仕組みがわかった!!

参考