通用随机数生成

Question

C++ 11为C推出了一个非常优越的随机数库rand().在C中,您经常会看到以下代码:

srand(time(0));
rand() % MAX + MIN;

因为time(0)以秒为单位返回当前时间,所以对程序的快速连续调用将产生相同的数字序列.对此的快速解决方法是在纳秒内提供种子:

 struct timeval time; 
 gettimeofday(&time,NULL);
 srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

当然,这并没有改变rand()普遍被认为是坏的和优越的替代品要么不可移植(如Linux random())或依赖第三方库(如Boost)的事实.

在C++ 11中,我知道产生良好随机数的最短程序是:

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<int> dist(1, 10);
    std::cout << dist(mt);
}

std::random_device是不便携的,std::default_random_engine因为它可能会选择一个糟糕的引擎,例如std::rand.实际上,由于这个原因,std::random_shuffle它已被弃用并且std::shuffle是首选.一般来说,我看到有人说使用计时器提供种子代替:

std::chrono::high_resolution_clock::now().time_since_epoch().count()

这不仅难以记住,而且当我们想要使用纳秒时看起来更加丑陋:

using namespace std::chrono;
std::mt19937 mt(duration_cast<nanoseconds>(high_resolution_clock::now()
                                      .time_since_epoch()).count());

• C方法看起来很理想,因为它不需要那么多的样板.

• random_device 是最容易的,因为它不需要丑陋的单行,即使它是不便携的.

• mt19937比记忆更难记住default_random_engine.

哪种方法最好？

Answer 1

(1) 了解可用的发电机并选择最适合工作的发电机

(2) 煮种子熵，绘制一个标准度量（如256位），将其打印到日志中

(3) 将您的标准种子块转换为适合相关生成器大小的seed_seq，并为 genny 提供种子

关于（1）：标准库中的生成器使用起来有点棘手，因为它们都有一些特殊性，并且它们都系统地未能通过像TestU01 这样的标准 PRNG 测试。您必须了解它们的具体缺陷才能判断它们的适用性。如果做不到这一点，请选择 mt19937 或 ranlux，为它们做好种子并希望获得最好的结果。使用 typedef（您自己的）可以让您切换并尝试不同的精灵。识破伪装并记录真实姓名。typeid(rng_t).name()

关于（2）：你不能将原始的、块状的熵传递给播种程序；如果你这样做，那么小的种子差异只会导致小的状态差异。熵必须被煮成光滑的糊状物，其中每一位都以 50% 的概率取决于原始输入的每一位。这包括 1、2、3 等输入……采用固定标准量的位汤可以使整个事情变得易于管理，例如打印到屏幕或日志以确保必要时的可重复性。不用说，如果您使用 1、2、42 等种子编号而不是随机种子，那么您可以将它们打印到日志中，而不是位汤提取物。使用您自己的钻头研磨机意味着您不会受到半途而废的播种功能的支配，甚至像 1、2、3 等“有缺陷的”种子也会给您带来截然不同的生成器状态（序列）。

关于 (3)：某些生成器（例如 mt19937）具有巨大的内部状态，因此您需要大量拉伸 256 位（或其他）标准种子。不幸的是，标准库不包含任何非常适合此任务的生成器，并且也没有用于将生成器转换为 Seed_seq 的适配器。

我会使用xorshift*、 KISS 、 ran （数值食谱）或 4x32 Tausworthe （又名lfsr113），但这些都不在库中。该库也没有任何合适的混合功能（钻头研磨机）。

我在类似的主题中发布了杂音混合器的代码 - 一个简单且极其高效的位混合功能；我在这里给出了经典的 KISS 和 Tausworthe，因为我在网上找不到合适的、干净的参考资料。

struct KISS {  uint32_t a, b, c, d; ... };

uint32_t KISS::cycle ()
{
   a = (a & 0xFFFF) * 36969 + (a >> 16);         // 16-bit MWC, a.k.a. znew()
   b = (b & 0xFFFF) * 18000 + (b >> 16);         // 16-bit MWC, a.k.a. wnew()
   c = c * 69069 + 1234567;                      // 32-bit LCG, a.k.a. CONG()(
   d ^= d << 13;  d ^= d >> 17;  d ^= d << 5;    // 32-bit XorShift a.k.a. SHR3(), corrected

   return (((a << 16) | (b & 0xFFFF)) ^ c) + d;  // mixing function (combiner)
}

合并后的陶斯沃斯：

struct LFSR113 {  uint32_t a, b, c, d; ... };

uint32_t LFSR113::cycle ()
{
   a = ((a ^ (a <<  6)) >> 13) ^ ((a & ~0x01) << 18);  // 31 bits
   b = ((b ^ (b <<  2)) >> 27) ^ ((b & ~0x07) <<  2);  // 29 bits
   c = ((c ^ (c << 13)) >> 21) ^ ((c & ~0x0F) <<  7);  // 28 bits
   d = ((d ^ (d <<  3)) >> 12) ^ ((d & ~0x7F) << 13);  // 25 bits

   return a ^ b ^ c ^ d;
}

要用作主要生成器，您必须调整禁止种子（粘性状态），但对于种子拉伸（制作 Seed_seq），可以安全地忽略它。有很多替代方案，例如使用 std::vector 和一个简单的生成器（LCG）来制作一个不错的种子序列，但我更喜欢尝试过的、值得信赖的和彻底分析的解决方案，以最少的代码量获得最大的效果。

这里显示的两个 4x32 生成器可以使用中国剩余定理进行步进，相反，任何状态都可以映射到整个序列中的唯一点（暂时忽略轨道之类的东西）。这使得它们和其他类似的发电机在不需要 xorshift1024*（或 mt19937）等大枪时作为一般用途的主要发电机具有吸引力。

在任何情况下，您都需要相当多的代码 - 例如头文件中的模板 - 以使标准<random>生成器使用起来简单、舒适和安全。但这是100%值得付出的努力。发电机不太热，但可以使用；其余的基础设施都相当不错，它可以对解决您的问题大有帮助。

PS：一些实现（VC++）允许将任何生成器传递给seed()函数，这使得事情变得非常简单。其他 - gcc - 则不需要，这意味着如果您希望代码可移植，则必须执行 seed_seq 操作。如果你想让事情变得超级简单，只需将你选择的种子传递给 murmur_mix() ，然后将它们交给 Seed() 并继续。

恐惧的代价：一旦你将你的魔法塞进标题中，实际应用就很容易了。

#include "zrbj/rng_wrapper.hpp"
#include <random>
#include <typeinfo>

int main ()
{
   zrbj::seeded<std::mt19937> rng(42);

   std::cout << typeid(rng.wrapped_rng).name() << " -> " << rng();
}       

这会将生成器、42 和实际种子打印到日志中，除了将碎片粉碎并将其填充到 mt19937 中之外。编码一次，靠在椅背上，享受吧。