8

我目前正在使用随机数生成器（gsl或boost）的 C/C++ 项目。整个想法可以简化为一个接收种子并返回结果的非平凡随机过程。我正在计算该过程的不同实现的平均值。

因此，种子很重要：这些过程必须使用不同的种子，否则会使平均值产生偏差。

到目前为止，我正在使用time(NULL)提供种子。但是，如果两个进程在同一秒开始，则种子是相同的。发生这种情况是因为我正在使用并行化（使用openMP）。

所以，我的问题是：如何在 C/C++ 上实现一个提供独立种子的“种子提供者”？

例如，我虽然在使用线程号（thread_num）seed = time(NULL)*thread_num，. 然而，这意味着种子是相关的：它们是彼此的倍数。这会对“伪随机”造成任何问题还是与顺序种子一样好？

要求是它必须在 Mac OS（我的电脑）和类似于 OS Cent（集群）的 Linux 发行版上工作（并且自然会提供独立的实现）。

4

8 回答 8

7

一个常用的方案是有一个“主”RNG 用于为每个流程特定的 RNG 生成种子。

这种方案的优点是整个计算仅由一个种子决定，您可以将其记录在某个地方以便能够重播任何模拟（这可能对调试讨厌的错误很有用）。

于 2012-10-08T12:41:18.673 回答
5

我们在 Beowulf 计算网格上遇到了类似的问题，我们使用的解决方案是将进程的 pid 合并到 RNG 种子中，如下所示：

time(NULL)*thread_num*getpid()

当然，您可以从 /dev/urandom 或 /dev/random 中读取一个整数。

于 2012-10-08T10:04:17.107 回答
3

遇到这个问题时，我经常使用seed_rngBoost.Uuid。它使用time,clock和随机数据/dev/urandom来计算种子。你可以像这样使用它

#include <boost/uuid/seed_rng.hpp>
#include <iostream>

int main() {
  int seed = boost::uuids::detail::seed_rng()();
  std::cout << seed << std::endl;
}

请注意，seed_rng它来自detail命名空间，因此它可以在没有进一步通知的情况下消失。在那种情况下，编写自己的实现seed_rng应该不会太难。

于 2012-10-08T10:13:25.763 回答
1

Mac OS 也是 Unix，所以它可能有/dev/random. 如果是这样，那是获得种子的最佳解决方案。否则，如果生成器是好的，取time( NULL )一次，然后为每个生成器的种子增加它，应该会产生相当好的结果。

于 2012-10-08T10:08:49.337 回答
1

如果您在 x86 上并且不介意使代码不可移植，那么您可以读取时间戳计数器 (TSC)，它是一个 64 位计数器，以 CPU（最大）时钟速率（约 3 GHz）递增，并且用它作为种子。

#include <stdint.h>
static inline uint64_t rdtsc()
{
    uint64_t tsc;
    asm volatile
    ( 
        "rdtsc\n\t"
        "shl\t$32,%%rdx\n\t"       // rdx = TSC[ 63 : 32 ] : 0x00000000
        "add\t%%rdx,%%rax\n\t"     // rax = TSC[ 63 :  0 ]
        : "=a" (tsc) : : "%rdx"
    );
    return tsc;
}
于 2012-10-08T10:16:23.593 回答
1

当比较由相同的伪随机数生成器产生的具有不同种子的两个无限时间序列时，我们可以看到它们相同地延迟了某个时间 tau。通常这个时间尺度比你的问题要大得多，以确保两个随机游走是不相关的。

如果您的随机过程处于高维相空间中，我认为一个好的建议可能是：

seed = MAXIMUM_INTEGER/NUMBER_OF_PARALLEL_RW*thread_num + time(NULL)

请注意，使用方案不能保证时间 tau 很大！

如果您对系统时间尺度有所了解，您可以多次调用随机数生成器，以生成在某个时间间隔内等距的种子。

于 2012-10-08T10:33:12.420 回答
1

也许您可以尝试 C++11 中的 std::chrono 高分辨率时钟：

类 std::chrono::high_resolution_clock 表示系统上可用的最小滴答周期的时钟。它可能是 std::chrono::system_clock 或 std::chrono::steady_clock 的别名，或第三个独立时钟。

http://en.cppreference.com/w/cpp/chrono/high_resolution_clock

但是我不确定 srand(0) 有什么问题；srand(1), srand(2).... 但我对 rand 的了解非常基础。：/

为了疯狂的安全考虑这个：

请注意，下面描述的所有伪随机数生成器都是 CopyConstructible 和 Assignable。复制或分配生成器将复制其所有内部状态，因此原始和副本将生成相同的随机数序列。

http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/reference.html#boost_random.reference.generators

由于大多数生成器都有疯狂的长周期，您可以生成一个，将其复制为第一个生成器，使用原始生成 X 个数字，将其复制为第二个，使用原始生成 X 个数字，将其复制为第三个......如果您的用户调用他们自己的生成器少于 X 次，它们不会重叠。

于 2012-10-08T13:28:55.933 回答
1

我理解您的问题的方式是，您有多个进程使用相同的伪随机数生成算法，并且您希望每个随机数“流”（在每个进程中）彼此独立。我对么 ？

在这种情况下，你猜对了，除非 rng 算法这么说，否则给出不同的（相关的）种子并不能保证任何东西。你基本上有两个解决方案：

简单版

使用具有单个种子的单一随机数源。然后以循环方式向每个进程提供随机数。

此解决方案很慢，但可以保证您提供给流程的数字是可以的。

您可以做同样的事情，但一次生成您需要的所有随机数，然后将此集合分成与您的进程一样多的切片。

使用为此设计的 RNG

您可以在论文和网络上找到几种专门设计用于从单个初始状态提供独立随机数流的算法。它们很复杂，但大多数都提供源代码。这个想法通常是将RNG空间（您可以从初始状态获得的值）“拆分”成各种块，如上所示。它们只是更快，因为如果您跳过给定数量的值，使用的算法可以轻松计算 RNG 的状态。

这些生成器通常被称为“并行随机数生成器”。最受欢迎的可能是这两个：

查看他们的手册以充分了解他们的工作、他们的工作方式以及是否真的是您需要的。

于 2012-10-11T06:20:41.657 回答