生成伪随机 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 位整数引擎。但是，我还没有找到任何提到的模板参数集（例如可以找到要求 here）。有没有？

更新：我更新了代码示例，并为分发进行了适当的初始化。

Answer 1

你的方法确实是正确的。

数学论证很复杂（我会尝试挖掘出一篇论文），但是采用 C++ 标准库实现的 Mersenne Twister 的最低有效位是正确的做法。

如果您对序列的质量有任何疑问，请运行通过顽固的测试。

Answer 2

考虑到 OP 问题中的这段引述（强调我的），可能存在误解：

The problem I see here is that std::mt19937 produces 32-bit unsigned integers […]. That means static casting is done and only the least significant part of these 32-bit integers is used by the distribution.

事情不是这样的。

以下引自https://en.cppreference.com/w/cpp/numeric/random

The random number library provides classes that generate random and pseudo-random numbers. These classes include:

Uniform random bit generators (URBGs), […];

Random number distributions (e.g. uniform, normal, or poisson distributions) which convert the output of URBGs into various statistical distributions

URBGs and distributions are designed to be used together to produce random values.

所以一个统一的随机位生成器，比如mt19937或random_device

is a function object returning unsigned integer values such that each value in the range of possible results has (ideally) equal probability of being returned.

虽然是随机数分布，比如uniform_int_distribution

post-processes the output of a URBG in such a way that resulting output is distributed according to a defined statistical probability density function.

它的完成方式使用所有来自源的位来产生输出。举个例子，我们可以看libstdc++中std::uniform_distribution的实现（从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_;
    }
};

这可以测试HERE。

生成伪随机 16 位整数

Generating pseudo-random 16-bit integers

c++

c++11

random

mersenne-twister