主页 / 问题 / 1357115
Accepted
Harry
Asked:2022-05-04 21:28:08 +0000 UTC2022-05-04 21:28:08 +0000 UTC

在小范围内生成随机数的 rand()%N 方法有多糟糕？

  • 772

实际上，一切都在标题中说明。
人们经常认为这种方法不好，特别是对于小值N。但我想了解它有多糟糕？
是否可以使用它还是绝对不能接受？

c++

2 个回答

  1. 语言标准没有指定std::rand()函数用来生成随机数的算法，所以一般来说，在不知道底层算法或要解决的问题的情况下，我不会对函数生成的随机数rand()。

    例如，考虑函数的几个实现rand()。

    glibc

    man 3 rand文档指出该函数使用rand与 相同的随机数生成器random()，因此生成值的低位与高位一样随机：

    rand()Linux C 库中的和版本srand()使用与 和 相同的随机数生成器random(3)，srandom(3)因此低位应该与高位一样随机。

    man 3 random文档解释说，“非线性加性反馈随机数生成器”被用作生成算法。虽然没有具体说明具体细节。只是说使用该函数initstate()可以将生成器内部状态的大小设置为8, 32, 64, 128, 甚至128字节。

    要了解它的具体作用random()，您可以查看

    对引用的来源的一项研究表明，文档巧妙地保持沉默，如果您initstate()在帮助下将内部状态的大小设置为 8 个字节，那么与其使用具有良好低位的棘手生成器，不如使用具有不太好的低位的线性同余生成器位将被使用。​​​

    程序：

    #include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
    constexpr size_t state_size = 8;
    char state[state_size] = {};
    unsigned int seed = 1;
    
    initstate(seed, state, state_size);
    
    for (int N = 2; N <= 8; N *= 2)
    {
        cout << "N: " << N << "    ";
        for (int i = 0; i < 8; ++i)
        {
            for (int j = 0; j < N; ++j)
                cout << rand() % N << " ";
            cout << "  ";
        }
        cout << "\n";
    }
}

    rand() % N以及它为一些生成的漂亮随机序列N：

    N: 2    0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1   

N: 4    2 3 0 1   2 3 0 1   2 3 0 1   2 3 0 1   2 3 0 1   2 3 0 1   2 3 0 1   2 3 0 1   

N: 8    6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1   6 7 4 5 2 3 0 1

    @Harry 在相邻答案中建议，卡方测试序列数据成功通过：

    Values count = 10
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.00  ok          1.60  ok  
 3     5.9      0.80  ok          0.80  ok  
 4     7.8      0.40  ok          0.40  ok  
 5     9.5      8.00  ok          8.00  ok  
 6    11.1      5.60  ok          3.20  ok  
 7    12.6      6.80  ok         12.40  ok  
 8    14.1      1.20  ok          9.20  ok  
 9    15.5      4.40  ok         11.60  ok  


Values count = 100
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.00  ok          1.44  ok  
 3     5.9      0.32  ok          0.74  ok  
 4     7.8      0.00  ok          1.68  ok  
 5     9.5      5.80  ok          0.70  ok  
 6    11.1      5.84  ok          6.80  ok  
 7    12.6      2.34  ok          4.02  ok  
 8    14.1      0.16  ok          4.80  ok  
 9    15.5     24.74  fail        6.74  ok  


Values count = 1000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.00  ok          0.32  ok  
 3     5.9      1.09  ok          1.23  ok  
 4     7.8      0.00  ok          6.37  ok  
 5     9.5      2.79  ok          1.27  ok  
 6    11.1      1.62  ok          2.90  ok  
 7    12.6      6.87  ok          2.34  ok  
 8    14.1      0.00  ok          8.00  ok  
 9    15.5      7.64  ok          9.17  ok  


Values count = 10000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.00  ok          0.18  ok  
 3     5.9      2.19  ok          0.76  ok  
 4     7.8      0.00  ok          4.75  ok  
 5     9.5      8.32  ok          6.32  ok  
 6    11.1      2.56  ok          0.48  ok  
 7    12.6      2.83  ok          3.89  ok  
 8    14.1      0.00  ok          2.38  ok  
 9    15.5      4.97  ok          7.56  ok  


Values count = 100000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.00  ok          0.66  ok  
 3     5.9      2.62  ok          4.50  ok  
 4     7.8      0.00  ok          1.61  ok  
 5     9.5     15.34  fail        2.23  ok  
 6    11.1      1.73  ok          5.98  ok  
 7    12.6      2.51  ok          9.07  ok  
 8    14.1      0.00  ok          6.20  ok  
 9    15.5      8.17  ok          8.45  ok

    MSVCRT

    vc++ 还使用了一个线性同余生成器（了解 Visual C++ 的 rand() 函数的算法）。为了提高生成序列的属性，一些位被丢弃。在接收值的 32 位中，16 位低位和 1 位高位 ( (val >> 16) & 0x7fff) 被丢弃。这略微延长了由最低有效位形成的序列的周期。

    让我们形成一个具有像素高度256和像素宽度的图像image_width，其中每个像素的颜色由片段中的整数[0; 255]根据以下算法给出：

    const int N = ...;
const int image_width = ...;
for (int row = 0; row < 256; ++row)
    for (int col = 0; col < image_width; ++col)
        image[row][col] = std::rand() % N * (255 / (N-1));

    结果是以下图像。

    N = 8; image_width = 509;

    兰德()%N; N = 8; 图像宽度 = 509;

    N = 4; image_width = 511;

    兰德()%N; N = 4; 图像宽度 = 511;

    N = 2; image_width = 512;

    兰德()%N; N = 2; 图像宽度 = 512;

    作为对比，如果我们在上面的代码中替换std::rand()为std::mt19937，则得到如下图像：

    N = 8; image_width = 509;

    mt()%N; N = 8; 图像宽度 = 509;

    N = 4; image_width = 511;

    mt()%N; N = 4; 图像宽度 = 511;

    N = 2; image_width = 512;

    mt()%N; N = 2; 图像宽度 = 512;

    • 8
  2. Best Answer

    N为了检验值偏向小值的假设，我草绘了一个简单的程序，该程序对不同的值和不同数量的生成值rand()%N应用卡方检验。N

    程序本身可以在这里找到，它的工作结果（VC++ 2019）如下。

    正如你所看到的，事实上，这两种方法 - 旧rand()%N的和新的uniform_int_distribution+ 标准生成器 - 都给出了非常相似的结果。

    均匀分布的假设几乎没有被违反，如果不小心被拒绝，那么在两种情况下都同样成功。

    因此，在我看来，这种方法不应该被拒绝。但是对于每个特定的编译器，我会用这个程序检查它以确保确实如此。

    Values count = 10
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      3.60  ok          0.40  ok  
 3     5.9      2.60  ok          3.20  ok  
 4     7.8      2.00  ok          3.60  ok  
 5     9.5      3.00  ok          4.00  ok  
 6    11.1      3.20  ok          4.40  ok  
 7    12.6      6.80  ok          8.20  ok  
 8    14.1      9.20  ok          4.40  ok  
 9    15.5     15.20  ok          0.80  ok  


Values count = 100
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.36  ok          0.00  ok  
 3     5.9      1.46  ok          1.34  ok  
 4     7.8      1.36  ok          0.56  ok  
 5     9.5      1.90  ok          3.70  ok  
 6    11.1      2.72  ok          2.12  ok  
 7    12.6      5.56  ok          2.62  ok  
 8    14.1      8.32  ok          4.96  ok  
 9    15.5      7.82  ok          7.10  ok  


Values count = 1000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.48  ok          0.48  ok  
 3     5.9      0.60  ok          0.51  ok  
 4     7.8      4.47  ok         10.07  fail
 5     9.5      3.02  ok          1.75  ok  
 6    11.1      3.92  ok          3.48  ok  
 7    12.6      9.99  ok          6.71  ok  
 8    14.1     19.12  fail        9.94  ok  
 9    15.5      5.91  ok          8.90  ok  


Values count = 10000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.29  ok          1.64  ok  
 3     5.9      0.35  ok          0.19  ok  
 4     7.8      3.02  ok          3.10  ok  
 5     9.5      5.93  ok          7.44  ok  
 6    11.1      3.42  ok          3.60  ok  
 7    12.6      6.59  ok          3.97  ok  
 8    14.1      4.85  ok          4.31  ok  
 9    15.5      5.74  ok         10.13  ok  


Values count = 100000
 N  xi(0.05)    rand()%N          uniform
-----------------------------------------
 2     3.8      0.18  ok          0.13  ok  
 3     5.9      0.21  ok          0.24  ok  
 4     7.8      2.57  ok          0.57  ok  
 5     9.5      0.55  ok          2.89  ok  
 6    11.1      4.19  ok          1.54  ok  
 7    12.6      2.71  ok         11.04  ok  
 8    14.1     15.91  fail       11.78  ok  
 9    15.5      5.87  ok          4.27  ok

    为了完全自给自足，代码是：

    #include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <random>

using namespace std;


double Xi[20][2] = // For \alpha = 0.10 && 0.05
{
    {  2.7,  3.8 },         // 1
    {  4.6,  5.9 },
    {  6.3,  7.8 },
    {  7.8,  9.5 },
    {  9.2, 11.1 },
    { 10.6, 12.6 },
    { 12.0, 14.1 },
    { 13.4, 15.5 },
    { 14.7, 16.9 },
    { 16.0, 18.3 },
    { 17.3, 19.7 },
    { 18.5, 21.0 },
    { 19.8, 22.4 },
    { 21.1, 23.7 },
    { 22.3, 25.0 },
    { 23.5, 26.3 },
    { 24.8, 27.6 },
    { 26.0, 28.9 },
    { 27.2, 30.1 },
    { 40.3, 43.8 }   // > 30...
};


default_random_engine g(random_device{}());


void Experiment(int N, int Count = 10000)
{
    uniform_int_distribution<> dis(0, N-1);
    vector<int> r(N), u(N);
    for(int i = 0; i < Count; ++i)
    {
        r[rand()%N]++;
        u[dis(g)]++;
    }
    double rs = 0, us = 0;
    for(int i = 0; i < N; ++i)
    {
        double d = double(r[i])/Count - 1./N;
        rs += d*d;
        d = double(u[i])/Count - 1./N;
        us += d*d;
    }

    rs = rs * Count * N;
    us = us * Count * N;

    double xi = (N < 20) ? Xi[N-2][1] : Xi[19][1];


    cout << setw(2) << N << "   " << fixed << setprecision(1)
        << setw(5) << xi << "   " << setprecision(2)
        << setw(7) << rs << ( rs < xi ? "  ok  " : "  fail")
        << "     "
        << setw(7) << us << ( us < xi ? "  ok  " : "  fail")
        << endl;
}



int main(int argc, char * argv[])
{
    srand(time(0));
    for (int Count = 10; Count <= 100000; Count *= 10)
    {
        cout << "\n\nValues count = " << Count << "\n";
        cout << " N  xi(0.05)    rand()%N          uniform\n";
        cout << "-----------------------------------------\n";
        for(int N = 2; N < 10; ++N) Experiment(N,Count);
    }

}
    • 6

相关问题