Генерация псевдослучайных 16-битных целых

Question

Мне нужно сгенерировать 16-битные псевдослучайные целые числа, и мне интересно, каков лучший выбор.

Очевидный путь, который приходит мне в голову, заключается в следующем:

std::random_device rd;
auto seed_data = std::array<int, std::mt19937::state_size> {};
std::generate(std::begin(seed_data), std::end(seed_data), std::ref(rd));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 generator(seq);
std::uniform_int_distribution<short> dis(std::numeric_limits<short>::min(), 
                                         std::numeric_limits<short>::max());

short n = dis(generator);

Проблема, которую я вижу здесь в том, что std::mt19937 производит 32-разрядные целые числа без знака, так как они определены так:

using mt19937 = mersenne_twister_engine<unsigned int, 
                                        32, 624, 397, 
                                        31, 0x9908b0df,
                                        11, 0xffffffff, 
                                        7, 0x9d2c5680, 
                                        15, 0xefc60000, 
                                        18, 1812433253>;

Это означает, что статическое приведение выполнено, и только наименее значимая часть этих 32-разрядных целых чисел используется распределением. Поэтому мне интересно, насколько хороши эти серии псевдослучайных шорт, и у меня нет математических знаний, чтобы ответить на этот вопрос.

Я ожидаю, что лучшим решением будет использование ваших собственных определенных mersenne_twister_engine движок для 16-битных целых чисел. Однако я не нашел ни одного упомянутого набора для аргументов шаблона (требования могут быть найдены здесь, например). Есть ли?

ОБНОВЛЕНИЕ: я обновил пример кода с правильной инициализацией для распространения.

Answer 1

Твой путь действительно правильный.

Математические аргументы являются сложными (я постараюсь выкопать статью), но использование наименее значимых бит из Mersenne Twister, реализованного в стандартной библиотеке C++, является правильным решением.

Если у вас есть какие-либо сомнения относительно качества последовательности, проведите ее через несгибаемые тесты.

Answer 2

Может быть неправильное представление, учитывая эту цитату из вопроса ОП (выделено мной):

Проблема, которую я вижу здесь, состоит в том, что std::mt19937 производит 32-разрядные целые числа без знака […]. Это означает, что статическое приведение выполнено, и только наименее значимая часть этих 32-разрядных целых чисел используется распределением.

Это не так, как это работает.

Ниже приведены цитаты из https://en.cppreference.com/w/cpp/numeric/random

Библиотека случайных чисел предоставляет классы, которые генерируют случайные и псевдослучайные числа. Эти классы включают в себя:

• Унифицированные генераторы случайных битов (URBG), […];
• Распределения случайных чисел (например, равномерное, нормальное или распределение Пуассона), которые преобразуют выходные данные URBG в различные статистические распределения

URBG и распределения предназначены для совместного использования для получения случайных значений.

Таким образом, генератор случайных битов, как mt19937 или же random_device

является функциональным объектом, возвращающим целые числа без знака, так что каждое значение в диапазоне возможных результатов имеет (в идеале) равную вероятность возврата.

В то время как распределение случайных чисел, как uniform_int_distribution

постобрабатывает выходные данные URBG таким образом, что полученные выходные данные распределяются в соответствии с определенной статистической функцией плотности вероятности.

То, как это делается, использует все биты из источника для получения вывода. В качестве примера мы можем посмотреть на реализацию std::uniform_distribution в libstdc++ (начиная со строки 824), которая может быть примерно упрощена как

template <typename Type>
class uniform_distribution
{
    Type a_ = 0, b_ = std::numeric_limits<Type>::max();
public:
    uniform_distribution(Type a, Type b) : a_{a}, b_{b} {}
    template<typename URBG>
    Type operator() (URBG &gen)
    {
        using urbg_type = std::make_unsigned_t<typename URBG::result_type>;
        using u_type    = std::make_unsigned_t<Type>;
        using max_type  = std::conditional_t<(sizeof(urbg_type) > sizeof(u_type))
                                            , urbg_type, u_type>;

        urbg_type urbg_min = gen.min();
        urbg_type urbg_max = gen.max();
        urbg_type urbg_range = urbg_max - urbg_min;

        max_type urange = b_ - a_;
        max_type udenom = urbg_range <= urange ? 1 : urbg_range / (urange + 1);

        Type ret;
        // Note that the calculation may require more than one call to the generator
        do
            ret = (urbg_type(gen()) - urbg_min ) / udenom;
            // which is 'ret = gen / 65535' with OP's parameters
            // not a simple cast or bit shift
        while (ret > b_ - a_);
        return ret + a_;
    }
};

Это можно проверить ЗДЕСЬ.