Что я делаю не так с этими случайными числами?

Мне сказали, что rand () mod n дает необъективные результаты, поэтому я попытался сделать этот код, чтобы проверить это. Генерирует s цифры от 1 до l и чем сортирует по вхождению.

#include <iostream>
#include <random>

using namespace std;

struct vec_struct{
int num;
int count;
double ratio;
};

void num_sort(vec_struct v[], int n){
for (int i = 0; i < n-1; i++){
for (int k = 0; k < n-1-i; k++){
if (v[k].num > v[k+1].num) swap(v[k], v[k+1]);
}
}
}

void count_sort(vec_struct v[], int n){
for (int i = 0; i < n-1; i++){
for (int k = 0; k < n-1-i; k++){
if (v[k].count < v[k+1].count) swap(v[k], v[k+1]);
}
}
}

int main(){

srand(time(0));

random_device rnd;

int s, l, b, c = 1;

cout << "How many numbers to generate? ";
cin >> s;

cout << "Generate " << s << " numbers ranging from 1 to? ";
cin >> l;

cout << "Use rand or mt19937? [1/2] ";
cin >> b;

vec_struct * vec = new vec_struct[s];

mt19937 engine(rnd());
uniform_int_distribution <int> dist(1, l);

if (b == 1){
for (int i = 0; i < s; i++){
vec[i].num = (rand() % l) + 1;
}
} else if (b == 2){
for (int i = 0; i < s; i++){
vec[i].num = dist(engine);
}
}
num_sort(vec, s);

for (int i = 0, j = 0; i < s; i++){
if (vec[i].num == vec[i+1].num){
c++;
} else {
vec[j].num = vec[i].num;
vec[j].count = c;
vec[j].ratio = ((double)c/s)*100;
j++;
c = 1;
}
}
count_sort(vec, l);

if (l >= 20){

cout << endl << "Showing the 10 most common numbers" << endl;
for (int i = 0; i < 10; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}

cout << endl << "Showing the 10 least common numbers" << endl;
for (int i = l-10; i < l; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}
} else {

for (int i = 0; i < l; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}
}
}

После запуска этого кода я могу определить ожидаемое отклонение от rand ():

$ ./rnd_test
How many numbers to generate? 10000
Generate 10000 numbers ranging from 1 to? 50
Use rand or mt19937? [1/2] 1

Showing the 10 most common numbers
17  230 2.3%
32  227 2.27%
26  225 2.25%
25  222 2.22%
3   221 2.21%
10  220 2.2%
35  218 2.18%
5   217 2.17%
13  215 2.15%
12  213 2.13%

Showing the 10 least common numbers
40  187 1.87%
7   186 1.86%
39  185 1.85%
42  184 1.84%
43  184 1.84%
34  182 1.82%
21  175 1.75%
22  175 1.75%
18  173 1.73%
44  164 1.64%

Hoover я получаю почти тот же результат с mt19937 а также uniform_int_distribution! Что здесь не так? Не должно быть равномерным, или тест бесполезен?

1

Решение

Нет, оно не должно быть идеально однородным. Таким образом, вышеизложенное не является доказательством какой-либо ошибки.

Они случайны и поэтому должны быть достаточно равномерными, но не совсем.

В частности, вы ожидаете, что каждое число будет встречаться примерно 10000/50 = 200 раз — примерно со стандартным отклонением sqrt (200), которое составляет около 14 — и для 50 чисел вы ожидаете около 2 стандартных отклонений разности — что + — / 28.

Смещение, вызванное использованием модуля для RAND_MAX, меньше, чем это; так что вам понадобится намного больше образцов, чтобы обнаружить смещение.

1

Другие решения

Вы должны использовать больше образцов для таких тестов случайных чисел. Я попробовал 50000 с вашим кодом, и результат:

Сколько чисел сгенерировать? 50000

Генерация 50000 номеров в диапазоне от 1 до? 50

Использовать rand или mt19937? [1/2] 2

Показаны 10 самых распространенных номеров

36 1054 2,108%

14 1051 2,102%

11 1048 2,096%

27 1045 2,09%

2 1044 2,088%

33 1035 2,07%

21 1034 2,068%

48 1034 2,068%

34 1030 2,06%

39 1030 2,06%

Показаны 10 наименее распространенных чисел

47 966 1,932%

16 961 1,922%

38 960 1,92%

28 959 1,918%

8 958 1,916%

10 958 1,916%

30 958 1,916%

32 958 1,916%

18 953 1,906%

23 953 1,906%

0

Насколько я могу судить по
http://www.cplusplus.com/reference/random/mersenne_twister_engine/ mt19937 будет страдать от того же смещения, что и rand ()

Смещение происходит из-за того, что rand () генерирует целое число без знака в некотором диапазоне [0-MAX_RAND], когда вы берете модуль, это делает меньшие числа немного более вероятными (если ваш делитель не является целочисленным делителем MAX_RAND)

Рассматривать:

Range [0-74]:
0 % 50 = 0
40 % 50 = 40
50 % 50 = 0
74 % 50 = 24
(numbers less than 25 occur twice)
-1
По вопросам рекламы [email protected]