Почему компилятор vc ++ вызывает этот статистический паттерн?

Question

Я запускаю следующую программу:

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <chrono>
using namespace std;

const int N = 200;          // Number of tests.
const int M = 2000000;      // Number of pseudo-random values generated per test.
const int VALS = 2;         // Number of possible values (values from 0 to VALS-1).
const int ESP = M / VALS;   // Expected number of appearances of each value per test.

int main() {
    for (int i = 0; i < N; ++i) {
        unsigned seed = chrono::system_clock::now().time_since_epoch().count();
        srand(seed);
        vector<int> hist(VALS, 0);
        for (int j = 0; j < M; ++j) ++hist[rand() % VALS];
        int Y = 0;
        for (int j = 0; j < VALS; ++j) Y += abs(hist[j] - ESP);
        cout << Y << endl;
    }
}

Эта программа выполняет N тестов.В каждом тесте мы генерируем M чисел от 0 до VALS-1, пока мы продолжаем считать их появления в гистограмме.Наконец, мы накапливаем в Y ошибки, которые соответствуют разнице между каждым значением гистограммы и ожидаемым значением.Поскольку числа генерируются случайным образом, каждое из них в идеале должно отображаться M / VALS раз за тест.

После запуска моей программы я проанализировал результирующие данные (т. Е. 200 значений Y) и понял, что некоторые вещигде происходит, что я не могу объяснить.Я видел, что, если программа скомпилирована с vc ++ и заданы некоторые N и VALS (в данном случае N = 200 и VALS = 2), мы получим разные шаблоны данных для разных значений M. Для некоторых тестов результирующие данные следуют нормальномураспространение, а для некоторых тестов это не так.Более того, результаты такого типа, по-видимому, чередуются, когда M (число псевдослучайных значений, генерируемых в каждом тесте) увеличивается:

• M = 10K, данные не являются нормальными:

• M = 100K, данные в норме:

• и т. Д .:

Как видите, в зависимости от значения M результирующие данные следуют за нормальным распределением или иным образом за ненормальным распределением (бимодальным, кормом для собак или видом униформы), в котором более экстремальные значенияиз Y имеют большее присутствие.

Такое разнообразие результатов не произойдет, если мы скомпилируем программу с другими компиляторами C ++ (gcc и clang).В этом случае, похоже, мы всегда получаем полунормальное распределение значений Y:

Что вы думаете об этом?Какое объяснение?

Я провел тесты через этот онлайн-компилятор: http://rextester.com/l/cpp_online_compiler_visual

Answer 1

Программа будет генерировать плохо распределенные случайные числа (не равномерно, независимо).

1. Функция rand общеизвестно плохая.
2. Использование оператора остатка % для приведения чисел в диапазон эффективно отбрасывает все, кроме младших битов.
3. ГСЧ каждый раз повторяется через цикл.

[править] Я только что заметил const int ESP = M / VALS;. Вместо этого вам нужно число с плавающей запятой.

Попробуйте код ниже и сообщите. Использование нового & LT; random> немного утомительно. Многие люди пишут небольшой код библиотеки, чтобы упростить его использование.

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;

const int N = 200;          // Number of tests.
const int M = 2000000;      // Number of pseudo-random values generated per test.
const int VALS = 2;         // Number of possible values (values from 0 to VALS-1).
const double ESP = (1.0*M)/VALS; // Expected number of appearances of each value per test.

static std::default_random_engine engine;

static void seed() {
    std::random_device rd;
    engine.seed(rd());
}
static int rand_int(int lo, int hi) {
    std::uniform_int_distribution<int> dist (lo, hi - 1);
    return dist(engine);
}
int main() {
    seed();
    for (int i = 0; i < N; ++i) {
        vector<int> hist(VALS, 0);
        for (int j = 0; j < M; ++j) ++hist[rand_int(0, VALS)];
        int Y = 0;
        for (int j = 0; j < VALS; ++j) Y += abs(hist[j] - ESP);
        cout << Y << endl;
    }
}