c++ - 使用 Boost PRNG 制作一个巨大的随机数查找表

Question

我正在尝试使用 Boost 的正态分布在给定不同种子的情况下生成随机数。换句话说，我需要为 seed1、seed2 等生成相同的随机数；在模拟过程中，数以千计的种子将被传递给函数。随机数生成器永远不会在没有种子的情况下使用。 [编辑:“ key ”这个词比“种子”更好——请参阅下面的最终描述 block 。]我不确定生成单个 RNG 并重新播种是否最有意义(如果是这样，如何)或者是否每次都更容易生成一个新的。到目前为止，这是我所拥有的，其中涉及在每次请求随机正态数时构建一个新的种子 rng:

double rnorm( int thisSeed ) {
  boost::mt19937 rng( thisSeed );
  boost::normal_distribution<> nd( 0.0, 1.0 ); // (mean, sd)
  boost::variate_generator > var_nor( rng, nd );
  return var_nor();
}

这是傻逼吗？我是 PRNG 的新手，尤其是 Boost 的实现。

---

对我这样做的原因的更详尽的描述:

我正在创建一个巨大的随机能量景观来模拟蛋白质相互作用:每个序列都有一个特定的能量，它被计算为淬火高斯随机数的总和，这些随机数取决于特定位置的特定氨基酸的值(以及一些其他序列属性)。我想使用 PRNG 来计算这些伪随机值是什么:这些值必须是一致的(相同的序列应该产生相同的值)，但是存储的方法太多了。作为一个简单的例子，我可能有一个序列 ARNDAMR 并根据两个子能量计算它的总能量:一个是随机正态数，它取决于 A 在位置 1 和 D 在位置 4，另一个子能量是一个随机数取决于最后三个氨基酸。我正在将配置转换为 key 以用作我的 PRNG 的种子(参数)。将构建和变异数以千计的序列，因此我需要一种快速计算能量的方法——因此我需要知道如何最好地播种和调用我的 RNG。除了这些能量值“查找”之外，我不会将 Boost RNG 用于任何其他用途。

---

进一步(tl;dr)解释:

我将使用 1 到 10^6 或 10^7 之间的整数作为“关键”值。我希望每个映射到一个高斯随机数。键值与其数字之间不应存在任何互相关(例如，键 145-148 不应映射到自相关的“随机”数字)。

每次在模拟中调用它( key )时，我都需要一个给定的 key 来返回相同的随机数。我不想将 key -随机数对存储在查找表中。

Answer 1

您的方法从根本上误解了 PRNG 的工作原理。如果你在每次使用时重新播种，那么你根本不会得到随机数，你只会得到一个糟糕的种子散列函数。特别是，即使您调用 PRNG 的正态分布函数，您的数字也不会呈正态分布，因为 PRNG 仅保证从特定种子生成的随机数是正态的。 p>

如果您需要大量随机数以针对一组特定的输入重复，则生成一个作为这些输入函数的数字，将其作为 PRNG 的种子，然后以可预测的方式从 PRNG 中获取数字顺序;它将为相同的输入产生相同的序列，并且数字将由 PRNG 正确分配。

如果您用来确定随机序列的输入集很大(尤其是大于 PRNG 种子的大小)，那么您将不会为每组输入提供唯一的序列。这可能适合您的应用程序，或者您可能想要使用具有更大种子的 PRNG。

看看我的公共(public)领域ojrandlib .它使用大种子，并使用快速 Ziggurat 算法生成正态分布的数。

---

看到你的说明后编辑:

啊，我明白了。没有“a”高斯随机这样的东西。分布只对一个种子的整个序列有意义，所以你需要做的是创建并播种一个单一的生成器，然后从该生成器中为你的每个键 N 获取第 N 个随机值。如果你不这样做这按顺序(也就是说，如果您完全随机地从键中获取而不是作为序列的一部分)这将非常慢，但仍然可能。您可能想看看是否可以强制执行一个序列，比如在获取键之前对键进行排序。

ojrandlib 也有一个函数discard()，所以如果你需要找到一个序列中的第 1,000,000 个数字，你可以播种 PRNG 并丢弃其中的 999,999 个，这样更快比实际生成它们，但仍然会很慢。

可能更好:不是使用您的 key 为高斯生成器提供种子，而是计算 key + 固定种子的良好散列函数(这将导致均匀分布的随机位)，然后将这些散列位解释为两个统一的 float ，然后用那些来改变分布的 Box-Muller 或 Ziggurat。这样，您获得的数字将全部来自同一个“种子”(这是哈希的输入)，但呈正态分布。您不需要加密安全散列，因此 MurMurHash 之类的东西可能会很好用，尽管您最好自己为这种特殊目的推出自己的散列。

---

认为我图书馆的用户可能会遇到与您类似的问题，因此我调查了一些可能性。以下是一些可能对您有用的代码:

/* Thomas Wang's 32-bit integer hash */
uint32_t nth_rand32(uint32_t a) {
    a -= a << 6;
    a ^= a >> 17;
    a -= a << 9;
    a ^= a << 4;
    a -= a << 3;
    a ^= a << 10;
    a ^= a >> 15;
    return a;
}

/* Marsaglia polar method */
double nth_normal(int index) {
    double f, g, w;
    int skip = 0;
    uint64_t x, y;

    do {
        x = (uint64_t)nth_rand32((index & ~1) + skip);
        y = (uint64_t)nth_rand32((index | 1) + skip);
        skip += 0x40000001;

        x = (x << 20) | 0x3ff0000000000000ull;
        f = *(double *)(&x) * 2.0 - 3.0;
        y = (y << 20) | 0x3ff0000000000000ull;
        g = *(double *)(&y) * 2.0 - 3.0;

        w = f * f + g * g;
    } while (w >= 1.0 || w == 0.0);

    w = sqrt((-2.0 * log(w)) / w);

    if (index & 1) w *= f;
    else w *= g;
    return w;
}

散列没有通过死忠，但它非常好。我生成了 10,000,000 个随机法线，并得到了这个分布(如果这个图像上传有效):

不完美，但也不算太差。使用更昂贵的哈希会好得多，但我会让你决定速度/准确性的权衡在哪里。