Генерация случайных чисел после нормального распределения в C / C ++

Question

Как я могу легко генерировать случайные числа после нормального распределения в C или C ++?

Я не хочу использовать Boost.

Я знаю, что Кнут подробно об этом говорит, но сейчас у меня нет его книг под рукой.

Answer 1

Существует множество способов генерации распределенных по Гауссу чисел из обычного ГСЧ .

Обычно используется преобразование Бокса-Мюллера . Он правильно выдает значения с нормальным распределением. Математика это легко. Вы генерируете два (равномерных) случайных числа, и, применяя к ним формулу, вы получаете два нормально распределенных случайных числа. Верните одно и сохраните другое для следующего запроса случайного числа.

Answer 2

C ++ 11

C ++ 11 предлагает std::normal_distribution, как я бы поступил сегодня.

C или старше C ++

Вот несколько решений в порядке возрастания сложности:

1. Добавьте 12 равномерных случайных чисел от 0 до 1 и вычтите 6. Это будет соответствовать среднему и стандартному отклонению нормальной переменной. Очевидным недостатком является то, что диапазон ограничен ± 6 - в отличие от истинного нормального распределения.

2. Преобразование Бокса-Мюллера. Это указано выше, и его относительно просто реализовать. Однако, если вам нужны очень точные выборки, имейте в виду, что преобразование Бокса-Мюллера в сочетании с некоторыми равномерными генераторами страдает аномалией, называемой Neave Effect ¹ .

3. Для большей точности я предлагаю рисовать форму и применять обратное кумулятивное нормальное распределение для получения нормально распределенных переменных. Здесь - очень хороший алгоритм для обратных кумулятивных нормальных распределений.

^{1. Х. Р. Нив, «Об использовании преобразования Бокса-Мюллера с мультипликативными конгруэнтными генераторами псевдослучайных чисел», Прикладная статистика, 22, 92-97, 1973}

Answer 3

Быстрый и простой метод - просто сложить количество равномерно распределенных случайных чисел и взять их среднее. См. Центральная предельная теорема для полного объяснения того, почему это работает.

Answer 4

Я создал C ++ проект с открытым исходным кодом для нормально распределенного теста генерации случайных чисел .

Сравнивает несколько алгоритмов, включая

• Метод центральной предельной теоремы
• преобразование Бокса-Мюллера
• Марсалья полярный метод
• алгоритм Зиккурата
• Метод выборки с обратным преобразованием.
• cpp11random использует C ++ 11 std::normal_distribution с std::minstd_rand (на самом деле это преобразование Бокса-Мюллера в clang).

Результаты версии с одинарной точностью (float) на iMac Corei5-3330S@2.70GHz, clang 6.1, 64-bit:

Для корректности программа проверяет среднее значение, стандартное отклонение, асимметрию и эксцесс образцов. Было обнаружено, что метод CLT путем суммирования 4, 8 или 16 равномерных чисел не имеет хорошего эксцесс, как другие методы.

Алгоритм Ziggurat имеет лучшую производительность, чем другие. Тем не менее, он не подходит для SIMD-параллелизма, так как требует поиска таблицы и ответвлений. Box-Muller с набором инструкций SSE2 / AVX намного быстрее (x1,79, x2,99), чем неигровая версия алгоритма зиккурата.

Поэтому я предложу использовать Box-Muller для архитектуры с наборами команд SIMD, и в противном случае может быть ziggurat.

---

P.S. В эталонном тесте используется простейший PRGG LCG для генерации равномерно распределенных случайных чисел. Так что это может быть недостаточно для некоторых приложений. Но сравнение производительности должно быть справедливым, потому что во всех реализациях используется один и тот же PRNG, поэтому тест в основном тестирует производительность преобразования.

Answer 5

Вот пример C ++, основанный на некоторых ссылках. Это быстро и грязно, лучше не изобретать заново и не использовать библиотеку наддува.

#include "math.h" // for RAND, and rand
double sampleNormal() {
    double u = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double v = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double r = u * u + v * v;
    if (r == 0 || r > 1) return sampleNormal();
    double c = sqrt(-2 * log(r) / r);
    return u * c;
}

Вы можете использовать график QQ, чтобы изучить результаты и увидеть, насколько хорошо он приближается к реальному нормальному распределению (ранжируйте ваши выборки 1..x, превратите ранги в пропорции от общего количества x, т. Е. Сколько образцов, получите z-значения и нанесите их на график. Прямой линией вверх является желаемый результат).

Answer 6

Использование std::tr1::normal_distribution.

Пространство имен std :: tr1 не является частью boost. Это пространство имен, которое содержит дополнения к библиотекам из Технического отчета C ++ 1 и доступно в современных компиляторах Microsoft и gcc, независимо от boost.

Answer 7

Так вы генерируете примеры на современном компиляторе C ++.

#include <random>
...
std::mt19937 generator;
double mean = 0.0;
double stddev  = 1.0;
std::normal_distribution<double> normal(mean, stddev);
cerr << "Normal: " << normal(generator) << endl;

Answer 8

Вы можете использовать GSL . Несколько полных примеров приведены , чтобы продемонстрировать, как его использовать.

Answer 9

Если вы используете C ++ 11, вы можете использовать std::normal_distribution:

#include <random>

std::default_random_engine generator;
std::normal_distribution<double> distribution(/*mean=*/0.0, /*stddev=*/1.0);

double randomNumber = distribution(generator);

Существует много других распределений, которые вы можете использовать для преобразования выходных данных механизма случайных чисел.

Answer 10

Посмотрите: http://www.cplusplus.com/reference/random/normal_distribution/. Это самый простой способ создания нормальных дистрибутивов.