std :: mersenne_twister_engine и генерация случайных чисел

Question

Какое распределение (равномерное, пуассоновское, нормальное и т. Д.) Генерируется, если я сделал ниже? Выходные данные указывают на равномерное распределение. Но тогда зачем нам std::uniform_int_distribution?

int main()
{
  std::mt19937_64 generator(134);
  std::map<int, int> freq;
  const int size = 100000;
  for (int i = 0; i < size; ++i) {
    int r = generator() % size;
    freq[r]++;
  }
  for (auto f : freq) {
    std::cout << std::string(f.second, '*') << std::endl;
  }
  return 0;
}

Спасибо!

Answer 1

Поскольку generator() является равномерным распределением по [generator.min(), generator.max()], generator() % n не является равномерным распределением по [0, n) (если generator.max() не является точным кратным n, предполагая generator.min () == 0).

Давайте рассмотрим пример: min() == 0, max() == 65'535 и n == 7.

gen() будут давать числа в диапазоне [0, 65'535] и в этом диапазонеявляются:

• 9'363 числа, такие как gen() % 7 == 0
• 9'363 числа, такие как gen() % 7 == 1
• 9'362 числа, такие как gen() % 7 == 2
• 9'362 чисел, таких как gen() % 7 == 3
• 9'362 чисел, таких как gen() % 7 == 4
• 9'362 чисел, таких как gen() % 7 == 5
• 9'362 числа такие, что gen() % 7 == 6

Если вам интересно, откуда я взял эти числа, подумайте об этом так: 65'534 является точным кратным 7 (65'534 = 7 * 9'362). Это означает, что в [0, 65'533] есть ровно 9'362 числа, которые сопоставляются с каждым из {0, 1, 2, 3, 4, 5, 6}, выполняя gen() % 7. Это оставляет 65'534, который отображается на 0 и 65'535, который отображается на 1

Таким образом, вы видите, что есть смещение в сторону [0, 1], чем к [2, 6], т.е. *

0 и 1 имеют немного более высокий шанс (9'363 / 65'536 ≈ 14.28680419921875 %) появления, чем 2, 3, 4, 5 и 6(9'362 / 65'536 ≈ 14.2852783203125‬ %).

std::uniformn_distribution не имеет этой проблемы и использует некоторое математическое вудо с возможностью получения большего числа случайных чисел из генератора для достижения действительно равномерного распределения.

Answer 2

Случайный механизм std::mt19937_64 выводит 64-битное число, которое ведет себя как равномерно распределенное случайное число. Каждый из случайных механизмов C ++ (в том числе из семейства std::mersenne_twister_engine) выводит равномерно распределенное псевдослучайное число определенного размера, используя определенный алгоритм.

В частности, std::mersenne_twister_engine соответствует RandomNumberEngine *Требование 1007 *, которое, в свою очередь, соответствует требованию UniformRandomBitGenerator ;следовательно, std::mersenne_twister_engine выводит биты, которые ведут себя как равномерно распределенные случайные биты.

С другой стороны, std::uniform_int_distribution полезен для преобразования чисел из случайных механизмов в случайные целые числа пользователя-определенный диапазон (скажем, от 0 до 10). Но обратите внимание, что uniform_int_distribution и другие дистрибутивы (в отличие от механизмов случайных чисел) могут быть реализованы по-разному от одной реализации стандартной библиотеки C ++ к другой.

Answer 3

Одним из главных достижений <random> было отделение дистрибутивов от двигателей.

Мне кажется, что это похоже на STL Александра Степанова, который отделял алгоритмы от контейнеров с помощью итераторов. Для случайных чисел я могу реализовать реализацию однобитового генератора (движка) Blum-Blum-Shub, и он все равно будет работать со всеми распределениями в <random>. Или я могу сделать простой линейный конгруэнтный генератор, x_ {n + 1} = a * x_ {n}% m, который при правильном заполнении никогда не сгенерирует 0. Опять же, он будет работать со всеми распределениями. Кроме того, я могу написать новый дистрибутив, и мне не нужно беспокоиться об особенностях любого движка, если я использую только интерфейс, указанный в UniformRandomBitGenerator.

В общем, вы всегда должны использовать дистрибутив,Также пришло время выйти на пенсию, используя «%» для генерации случайных чисел.

Answer 4

std::mt19937_64 генерирует псевдослучайную взаимно независимую последовательность чисел long long / unsigned long long. Предполагается, что он равномерный, но я не знаю точных деталей двигателя, хотя на данный момент это один из лучших обнаруженных двигателей.

Взяв % n, вы получите приближение к псевдо-случайное равномерное распределение по целым числам [0, ... ,n] - но оно по своей сути неточно. У некоторых чисел вероятность появления немного выше, в то время как у других - чуть меньше, в зависимости от n. Например, поскольку 2^64 = 18446744073709551616, поэтому при n=10000 первые 1616 значения имеют немного более высокий шанс возникновения, чем последние 10000-1616 значения. std::uniform_distribution заботится о неточности, беря новое случайное число в очень редких случаях: скажем, если число выше 18446744073709550000 для n=10000, возьмите новое число - это сработает. Тем не менее, конкретные детали до реализации.