2

我试图找到最有效的方法来为我正在研究的 MC 模拟生成随机数。我已经阅读了很多关于双精度 Mersenne Twister 算法的内容，我想在继续之前了解一些基本的东西。

我编译并运行了官方 dSFMT 文件提供的测试，这对我的系统来说是最好的结果：

C:\TDM-GCC-64\C++ Tests\dSFMT>test-sse2-M19937 -s
consumed time for generating 100000000 randoms.
ST BLOCK [0, 1) AVE: 115ms.
ST BLOCK (0, 1] AVE: 108ms.
ST BLOCK (0, 1) AVE: 106ms.
ST BLOCK [1, 2) AVE:  77ms.
ST SEQ [0, 1) 1 AVE: 174ms.
ST SEQ [0, 1) 2 AVE: 207ms.
total = 500014655.815776
ST SEQ (0, 1] 1 AVE: 173ms.
ST SEQ (0, 1] 2 AVE: 205ms.
total = 500035344.184224
ST SEQ (0, 1) 1 AVE: 209ms.
ST SEQ (0, 1) 2 AVE: 247ms.
total = 500014655.815776
ST SEQ [1, 2) 1 AVE: 173ms.
ST SEQ [1, 2) 2 AVE: 204ms.
total = 1500064655.815183

我的问题是：

  1. 为什么生成 [1,2) 比 [0,1) 快？
  2. 为什么块生成比顺序生成快？分配一个大数组并且必须删除和重写它不应该更慢吗？
  3. 如果我需要生成 1e12 数字，最好的策略是什么？如果分块进行，最佳数组大小是多少？
4

1 回答 1

2

库内的数字是从 [1,2) 区间生成的。其他范围表示为该区间顶部的函数。

“基本”区间 [1,2) 生成器：

inline static double dsfmt_genrand_close1_open2(dsfmt_t *dsfmt) {
    double r;
    double *psfmt64 = &dsfmt->status[0].d[0];

    if (dsfmt->idx >= DSFMT_N64) {
        dsfmt_gen_rand_all(dsfmt);
        dsfmt->idx = 0;
    }
    r = psfmt64[dsfmt->idx++];
    return r;
}

区间 [0, 1):

inline static double dsfmt_genrand_close_open(dsfmt_t *dsfmt) {
    return dsfmt_genrand_close1_open2(dsfmt) - 1.0;
}

块生成速度更快的原因有很多，包括缓存局部性、更少的函数调用、循环展开等。在实践中，块操作通常比单个操作组合起来更快。

在这种特殊情况下，块生成也更快，因为数字是成对生成的（W128_T类型）：

union W128_T {
    __m128i si;
    __m128d sd;
    uint64_t u[2];
    uint32_t u32[4];
    double d[2];
};

块版本利用此属性，并将两个数字从W128_T结果数组中复制。顺序版本仅使用第一个数字并丢弃第二个。

至于您的第三个问题，请使用块生成，因为事实证明它在您的计算机上更快。您每 100 毫秒有 1e8 个数字，因此对于 1e12，您需要大约 20 分钟。如果对您来说没问题，那么只需使用NUM_RANDS块大小，任何合理的块大小都不应该有太大差异。否则，请考虑从多个线程中的独立生成器生成数字。

于 2015-07-05T03:36:32.433 回答