生成伪随机的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位整数的最低有效部分进行分布。因此，我想知道这些伪随机shorts序列有多好，但我没有数学专业知识来回答。

我期望更好的解决方案是使用您自己定义的mersenne_twister_engine引擎用于16位整数。然而，我没有找到任何提及的模板参数集（可以在此处找到要求）。有吗？

更新：我使用适当的初始化方式更新了代码示例。

- Marius Bancila

---

为什么不适当设置std::uniform_int_distribution的分布范围：std::uniform_int_distribution<short> dis(std::numeric_limits<short>::min(), std::numeric_limits<short>::max()); - Some programmer dude

我原本以为使用默认构造函数会有相同的效果。 - Marius Bancila

不行，因为默认的构造函数将0作为范围的底部。 - Some programmer dude

据我回想，这个理论认为生成器只是一个随机比特的来源，而分配器可以持有状态。因此，分配器可以自由地持有从生成器中读取的比特缓存，并按需分配任意大小的块。因此，在您的情况下，与配置为提供32位数字的分配器相比，16位的分配器可能只调用生成器一半的次数。 - Galik

@vandench 如果你所说的“稍微差一点”是指“糟糕透顶”，那么我们在这一点上都是同意的。在我的 dieharder 实例中，rand() 在前10个统计测试中只通过了3个，而 mt19937 则通过了9个并且一个是弱通过。有时候，提问者已经知道如何正确使用 <random>，但你还是引诱他加入黑暗面...这真是令人费解。至于过早优化，顺便说一下，return 0; 是一个非常快的 PRNG。（哦，而 rand() 只提供15位有效数字。） - Arne Vogel

Answer 1

您的方法确实是正确的。

数学论证很复杂（我会试着找一份论文），但是采用C++标准库实现的Mersenne Twister的最低有效位是正确的方法。

如果您对序列的质量有任何疑问，可以通过diehard测试来验证。

- Bathsheba

---

这真的那么复杂吗？如果你从随机的两位数中取最后一位数字，那么它们也是随机的。我知道这只是一个粗略的简化，但考虑到比特而不是数字可能并没有那么不同。期待看到论文 ;) - 463035818_is_not_a_number

对于一个真正的随机数生成器是正确的，但对于其他类型的生成器则不然。例如，对于线性同余生成器，其产生的序列通常是奇数->偶数->奇数->偶数，这意味着最低有效位相当确定性！ - Bathsheba

添加到_odd->even->odd->even_序列：据我所知，rand()函数对于2的幂取模更容易出现问题。幂次越小，它就变得更加确定性。我曾经在实践中意识到这一点，当时我想用4种棕色和rand()函数制作沙纹理。然而它给出了一个重复的图案（看起来像一个奇怪的70年代壁纸）。将颜色增加到5（一个质数），进而获得了完全令人满意的结果。 :-) - Scheff's Cat

Answer 2

这里可能存在误解，考虑到 OP 问题中的这句话（强调是我的）：

“我在这里看到的问题是 std::mt19937 生成 32 位无符号整数[...]。这意味着进行了静态转换，并且分布只使用了这些 32 位整数的最低有效部分。”

事实并非如此。

以下是来自 https://en.cppreference.com/w/cpp/numeric/random 的引用：

“随机数库提供了生成随机和伪随机数的类。这些类包括：均匀随机比特发生器(URBGs)，[...]; 将 URBGs 的输出转换为各种统计分布的随机数分布（例如均匀、正态或泊松分布）”

“URBGs 和分布被设计为一起使用以产生随机值。”

因此，像 mt19937 或 random_device 这样的均匀随机比特发生器与随机数分布配合使用，可以产生各种随机值。

这是一个函数对象，返回无符号整数值，使得可能结果范围内的每个值都具有（理想情况下）相等的返回概率。

而像uniform_int_distribution这样的随机数分布，

会以一种定义好的统计概率密度函数的方式后处理URBG的输出。

完成此操作的方式使用源中的所有位来产生输出。例如，我们可以查看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_;
    }
};

这可以在这里进行测试。

- Bob__