2

给定 [0, 2^64) 范围内的均匀分布的随机数生成器，是否有任何有效的方法（在 GPU 上）为某些 k < 2^64 的范围 [0,k) 构建随机数生成器？

一些不起作用的解决方案：

// not uniformly distributed in [0, k)
myRand(rng, k) = rng() % k;

// way too much branching to run efficiently on a gpu
myRand(rng, k) =
    uint64_t ret;
    while((ret = rng() & (nextPow2(k)-1)) >= k);
    return ret;

// only 53 bits of random data, not 64. Also I
// have no idea how to reason about how "uniform"
// this distribution is.
myRand(doubleRng, k) =
    double r = doubleRng(); // generates a random number in [0, 1)
    return (uint64_t)floor(r*k);

如果差异足够小（例如，在 1/2^64 内），我愿意妥协不均匀性。

4

2 回答 2

3

只有两种选择：进行模数（或浮点数）并解决非均匀性，或使用循环进行拒绝采样。真的没有第三种选择。哪个更好取决于您的应用程序。

如果您的k通常非常小（例如，您正在洗牌，因此k大约为 100），那么非均匀性非常小，即使是 32 位也可能没问题。在 64 位上，数百万级的k仍然会给您带来非常小的不均匀性。不，它不会是 1/2^64 的数量级，但我无法想象在实际应用中 1/2^20 数量级的不均匀性是显而易见的。当我为我的 RNG 库编写测试套件时，我故意针对一个已知的错误mod实现运行它，即使是 32 位，它也很难检测到错误。

如果你真的必须完全统一，那么你只需要抽样和拒绝。这可以很快完成，您甚至可以摆脱除法（nextPow2()在拒绝循环之外计算——这就是我在ojrandlib中的做法）。仅供参考，做下一个二次幂掩码的最快方法是：

mask = k - 1;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
mask |= mask >> 32;
于 2013-06-17T18:40:54.620 回答
0

If you have a function that returns 53 bits of random data, but you need 64, call it twice, use the bottom 32 bits of the first call for the top 32 bits of your result, and the bottom 32 bits of the second call for the bottom 32 bits of your result. If your original function was uniform, this one is too.

于 2013-06-24T20:23:17.543 回答