播种许多PRNG，然后不得不再次播种，什么是高质量的方法？

Question

我有许多粒子平行地跟随着一个随机过程。对于每个粒子，都有一个与其关联的PRNG。模拟必须经过多次重复才能获得平均结果。对于每个重复，在模拟开始之前，应该为每个粒子选择一个独占的PRNG种子。

这是我第一次将seed = time(NULL)作为particle1的种子。对于其余部分，我只执行particle2 = seed + 1、particle3 = seed + 2等。，所以所有粒子最终都有不同的种子。

在每次重复时，计划是向从time(NULL) (如seed = seed + all_particles_offset; )获得的初始种子添加偏移量，然后使用前面描述的方法为每个粒子指定不同的种子。我的问题是，这种方法是否会带来可接受的随机性质量？我不关心安全性，只关心并行运行的随机数的质量，以及该过程不时重新播种的事实。

顺便说一下，使用的PRNG是PCG。

Answer 1

时间不是一个好的种子，因为它太可预测了。如果你经常需要种子，它也有被重用的风险。为了避免这种情况，通常将时间替换为进程和/或线程ID等其他值。

更好的方法是从操作系统的随机性来源获取种子，比如/dev/random或非阻塞版本的/dev/urandom。这将使用环境噪声和其他来源来为您提供一个很好的随机种子。

您可以将它们组合在一起，这就是Ruby's Random#new_seed所做的。

    /* This gets a seed from /dev/urandom */
    fill_random_bytes(seed, sizeof(*seed));

    /* This further permutes the seed with the time and pid */
    gettimeofday(&tv, 0);
    seed[0] ^= tv.tv_usec;
    seed[1] ^= (uint32_t)tv.tv_sec;
#if SIZEOF_TIME_T > SIZEOF_INT
    seed[0] ^= (uint32_t)((time_t)tv.tv_sec >> SIZEOF_INT * CHAR_BIT);
#endif
    seed[2] ^= getpid() ^ (n++ << 16);
    seed[3] ^= (uint32_t)(VALUE)&seed;
#if SIZEOF_VOIDP > SIZEOF_INT
    seed[2] ^= (uint32_t)((VALUE)&seed >> SIZEOF_INT * CHAR_BIT);
#endif

你可以从random.c中摘取他们的随机种子代码。

为了避免从/dev/random读取这么多信息，这可能会耗尽熵，您可以改为使用@indiv suggested in the comments：seed a PRNG来生成更多的种子。好的一面是你只需要一个好的种子。缺点是它可能会让你容易受到PRNG中的缺陷的影响。

这就是/dev/urandom所做的，它使用/dev/random的真正随机性来播种它自己的PRNG，以确保总是有随机数。你可以从/dev/urandom中读取种子。优点是这增加了另一个PRNG，它可以通过用相同PRNG算法的输出来播种你的PRNG来抵消任何缺陷……或者它可能会让它们变得更糟。缺点是你不知道/dev/urandom是如何生成这些种子的，它会随着平台的不同而改变。

所有这些都比使用time或seed +1、seed + 2等要好。

Answer 2

Cristobal，使用PCG或类似的PRNG (使用快速对数跳过)，您不需要处理多个种子。一个种子就足够了。在所有线程/工作线程启动之前，你给PRNG播种一次，就是这样。

您可以设置每个event - N_part需要多少个RNG调用。您可以设置每个线程的事件的方式- N_evt。

然后在你开始你的工人后，在每个工人中你必须做

pcg rng(seed);
rng.skip_ahead(worker_id*N_part*N_evt); // whatever it is called in PCG

for(int k = 0; k != N_evt; ++k) {
    int used_rngs = simulate_particle();
    // overlap check
    rng.skip_ahead(N_part-used_rngs); // move to the next particle
}

因此，你有一个完全可控的模拟，你知道如果你重叠，每个粒子开始于相同的rng状态，所以它是完全可重现的，用于调试等。