乱数を生成するアルゴリズムを勉強してみた！！

アプリやゲームをプログラミングする時、しばしば乱数を使用する。
ほとんどのプログラミング言語で、乱数を生成する標準ライブラリが準備されているが、内部的にどのように生成しているのかを考えたことはなかった…

そこで乱数を生成するアルゴリズムを勉強してみようと思った。

擬似乱数

PC, プログラム自らは情報を生み出すことはできず、何らかの計算式を使って、見かけ上ランダムな数値を生成する。このような乱数を「擬似乱数」と呼ぶ。

例えば、C言語の標準ライブラリには0〜32767の範囲で乱数を生成するrand関数がある。
乱数生成前のウォーミングアップとして、rand関数を使用してみる。以降では、擬似乱数を単純に「乱数」と表現する。

rand関数を使用する前に準備すべきことがある。それは乱数を生成する式の中で使われる最初の値を変えることである。この値を「乱数の種」と呼ぶ。

乱数の種

「乱数の種」を変えないと、rand関数は毎回同じパターンの数列を返す。
C言語は、srand関数を使って乱数の種を設定できる。srand関数の引数に、乱数の種を与える。

乱数の種には、time関数の戻り値を使うのが定番テクニック。

time関数は、1970年1月1日0:00からの経過時間を返す。この値は、プログラムを起動するたびに異なるため、毎回値を変えるべき乱数の種として好都合。

srand関数とrand関数の使い方を示すプログラムを示す。実行すると10個の乱数を表示する。

どのような乱数になるか？はプログラムを実行したタイミング（時間）次第。

ちなみに、8行目を"/* */"で囲んでコメントアウトしてみると、面白い結果が得られる。
何度プログラムを実行しても、毎回同じ結果が表示される。

#include <stdio.h>
#include <stdlib.h> //srand関数とrand関数のため
#include <time.h>   //time関数のため

int main(int argc, char* argc[]) {
    int i;
    //乱数の種を設定する
    srand((unsigned int)time(NULL));

    //乱数を10個生成、表示する
    for (i = o; i < 10; i++) {
        printf("%d\n", rand());
    }
    return 0;
}

乱数生成アルゴリズム⑴　ー線形合同法

C言語のrand関数内部で使用されていることで有名な「線形合同法」。
以下の斬化式（数列の１つ前の値で、その次の値を求める式）で乱数を生成する方法。

この式は、n番目の乱数Xnを、その１つ前の乱数X(n-1)を使った計算で得ることを示している。

modは割り算のあまりを求める演算子(C言語では%演算子)。

Xn = (A x Xn-1 + B) mod M

この式において、A, B, Mは、0より大きな整数の定数。
X0が「乱数の種」に相当する。

X0を式の右辺において得られる計算結果が、最初の乱数X1になる。
以下同様に、X1を右辺においてX2を得る。X2を右辺においてX3を得る…と繰り返し計算する。

#include <stdio.h>

//１つ前の乱数
int random;

//乱数の種を設定する関数
void srand2(unsigned int seed) {
    random = seed;
}

//乱数を生成する関数
int rand2() {
    random = (2 * random + 3) % 7;
    return random;
}

int main(int argc, char* argv[] {
    int i;
    //乱数の種を設定する
    srand2(3);
    //乱数を10個生成する
    for (int i = 0; i < 10; i++) {
        printf("%d\n", rand2());
    }
    return 0;
}

上記において、A = 2, B = 3, M = 7 として生成した乱数生成rand2関数と、乱数の種を設定するsランD２関数。
C言語の標準ライブラリの関数と間違えないように、関数名の末尾に2を付けた。

グローバル件数randomに格納するだけ。rand2関数は、線形合同法の式に従って乱数を計算し、その値をグローバル変数randomに格納し、戻り値として返す。

テスト用のmain関数では、srand2関数の引数に、time関数の戻り値ではなく3（適当に選定）を与えている。

擬似乱数には周期性がある

rand2関数の

random = (2 * random + 3) % 7;

の部分を見れば、乱数生成の仕組みがわかる。
直前に生成された値を2倍して3を加えることによってできる数列が、乱数のようにみえる。

ただし7で割った余りのため、生成される乱数の範囲は、0~6に制限される。
この結果、同じ数列が繰り返されることがわかる。

擬似乱数の特徴であり、「周期性」と呼ばれている。

多くの選択肢から最適解を見つける方法を勉強してみた！！

最適化問題とも言われ、たくさんある選択肢の中から、最適な解を選び出す手法で、「グリーディ法」と呼ばれている。

グリーディ法は近似アルゴリズムの一種で、最適解ではなくてもそれほど悪くない解を（近似解）を得る手順のことで、"BEST"より"BETTER"を探し出す手法と言うとわかりやすいと思う。

最適解を得るのに、膨大な計算を要する場合、短時間で解を得るために、近似アルゴリズムが用いられることがある。

実際において、近似解であっても無駄がなければ（誤差が一定以内）十分と判断できるはずであり、短時間で効率的に「解を得る」場合に用いられることになる。

まずは【硬貨の交換問題】から！

問題

あるお店で、、税込213円の商品を購入した場合、お客さんは1000円札を出しました。
お釣りは、

1000 - 213 = 787円

です。
できるだけ少ない枚数でお釣りを返すには、どのような組み合わせにすべきでしょうか？

解答例

この問題の答えは、

• 500円 x 1
• 100円 x 2
• 50円 x 1
• 10円 x 3
• 5円 x 1
• 1円 x 2

となる。この解を得るためには、「できるだけ大きな硬貨を使う」と考えたと思う。

つまりこれが『グリーディ法』である。

グリーディ(Greedy)とは、「貪欲な」という意味で、「可能な限り大きな硬貨を使う」というアイデアを『貪欲』と表現しているのである。

プログラム例

ではこれを実際のプログラムにするとどのようになるのか？
例を以下に記してみる。

#include <stdio.h>

int main(int atgc, char* argv[]) {
    //お釣り、枚数、枚数の合計、ループカウンタ
    int change, n, sum, i;

    //硬貨の種類
    int val[] = {500, 100, 50, 10, 5, 1};

    printf("お釣りは？");
    scanf("%d", &change);

    sum = 0;
    for (i = 0; i < 6; i++) {
        n = change / val[i];
        printf("%d円硬貨 : %d枚", val[i], n);
        sum += n;
        change %= val[i];
    }

    printf("硬貨の合計枚数: %d枚\n", sum);

    return 0;
}

このように、"%"の計算を用いて、除算の余りを得る演算を繰り返すことで、より小さい硬貨へ交換するための残金を求めることができる。

現在の日本の硬貨であれば、「できるだけ大きな硬貨を使う」というグリーディ方で、最適解が得られる。

もしも新たにな硬貨が追加されたらどうなる？

グリーディ法では最適解が得られない場合が生ずる。

例えば、400円硬貨が追加された場合どうだろう？

先ほどのプログラム例で、

int val[] = {500, 400, 100, 50, 10, 5, 1};

に

for (i = 0; i < 6; i++)

の部分を

for (i = 0; i < 7; i++)

に健康して、お釣り800円を置き換える硬貨の枚数を求めてみる。

400円硬貨があるなら、

• 400円 x 2

が、最適解となるが、プログラム実行の結果は、

• 500円 x 1
• 400円 x 0
• 100円 x 3
• 50円 x 0
• 10円 x 0
• 5円 x 0
• 1円 x 0

となる。「できるだけ大きな硬貨を扱う」というグリーディ法では、最適解を得られないことがあるというのが特徴。
ただし、

• 1円 x 800

といったおかしな解にもなりません。

これと比較した時、今回の例では、硬貨の枚数が２枚でも４枚でも大きな差はないと言え、「4枚という近似解は十分に実用的」と言える。

以上から、

「プログラミングをする以上、正確無比な最適解を常に求めなければならない！！」と思いがちではあるが、実生活において、「最適解を求めるまでに、時間を要するのであれば、近似解を１秒で求めた方が実用的だ！」と判断する場面は多い。

このことからプログラムにおいても、『実用性』を考慮した設計・仕様が重要と言える。