關於亂數產生器

剛好看到 亂數產生器:Random 與 RNGCryptoServiceProvider,想到當年回台中面試 新博 有被問類似的題目。

文中的 產生亂數 的寫法會有一點不均勻的亂,他的做法跟下面的例子是一樣的。

當你中午有四家餐廳想吃,但不知該選那家。於是想用一顆六面骰來幫你決定,你的策略是超過 4 的取餘數。

結果你發現你很常選到第 1, 2 家,因為他們的機率比選 3, 4 的還高。

而原文中的程式碼就出現了這個問題。雖然在指定範圍小的時候,這個誤差可以忽略,但當取值範圍夠大時問題就浮出來。

例如在 0 ~ 2147483647(int.MaxValue) 中取權重比為 1:2:4 但是取的基數範圍不同。則結果如下

基數1/72/74/7
714.2857%28.5714%57.1429%
70014.2857%28.5714%57.1429%
7000014.2860%28.5717%57.1422%
700000014.2958%28.5916%57.1126%
70000000016.1810%27.9397%55.8794%

建議 產生一個非負數的亂數 調整為

1
2
3
4
5
6
7
public static int Next()
{
    rngp.GetBytes(rb);
    int value = BitConverter.ToInt32(rb, 0);
    if (value < 0) value -= int.MinValue;
    return value;
}

產生一個非負數且最大值 max 以下的亂數 調整如下。這部分的數學就不特別解釋了。🤭

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static int Next(int max)
{
    if (max == int.MaxValue) {
        return Next();
    }

    int bound = int.MaxValue - int.MaxValue % (max + 1);

    int value;
    do
    {
        value = Next();
    } while (value >= bound);

    value %= (max + 1);
    return value;
}
updatedupdated2021-12-032021-12-03