一次不使用所有位时的PRNG质量

我目前在我的项目中使用xorshift128 +，我知道它通过了Big Crush，并被认为能够为其速度生成相当高质量的随机数。 然而，它产生64位数，我需要的绝大多数随机数是小整数（在0到100之间）。

现在，使用％将64位随机数减少到所需的范围会导致非均匀分布（某些数字出现的次数多于其他数字），并且在2的幂次的情况下完全丢弃大部分位。 这种方法可以生成数字，直到某些东西在范围内，这会导致更加均匀的分布，但是对于小数字来说，它有点问题，并且当我已经拥有超过必要的开始位置时，生成更多位是很愚蠢的。

因此，我实现了一个系统，它需要最少的位数（查找最接近的2的幂，例如，如果我需要一个0-95的范围，我将取7位（2 ^ 7 = 128），并继续生成7直到我得到95以下的东西，应该总是有50％以上的概率，否则我可以少用一点）

无论如何，这个系统已经到位了，基本的统计测试表明它正在按预期工作，而且运行速度非常快。 但是，我一直无法在修改过的系统上运行TestU01（似乎没有支持动态比特尺寸），原始文件有点过于密集，无法通过。

基本上，我想知道如果通过Big Crush向前和向后传递，正如xorshift128 +所声称的那样，强烈表明每个单独的位都是满意的随机分开使用它们应该没问题，或者如果我可以让自己陷入困境。 另外，可选地，任何测试套件都可以让我凭经验验证发电机的统计质量。

---

这种方法可以生成数字，直到某个事物处于范围内，从而得到更均匀的分布，但是对于小数目，它有点问题[...]。

对于像以下C99例子那样的幼稚实现来说，情况确实如此：

uint64_t prng(void);

// Returns a random number between 0 and max-1.
uint64_t bounded_prng(uint64_t max) {
    uint64_t r;

    // Rejection sampling.
    do {
        r = prng();
    } while (r >= max);

    return r;
}

但还有另一种有效的算法。 您可以使用的最大倍数扩大的门槛max ，适合在一个uint64_t ，这是2^64 - (2^64 % max) 。 如果PRNG返回低于此阈值的值，则返回值模数max ，否则返回另一个随机值。

uint64_t bounded_prng(uint64_t max) {
    // Compute modulus: 2^64 % max = (2^64 - max) % max = -max % max.
    uint64_t mod = -max % max;

    // Compute threshold: 2^64 - mod = -mod
    uint64_t threshold = -mod;

    uint64_t r;

    do {
        r = prng();
    } while (r >= threshold);

    return r % max;
}

现在，随机值被拒绝的概率保证小于50％，从而产生一个非常有效的算法，就像您的位掩码方法一样。 对于小范围， prng被称为不止一次的概率非常小。 但如果你事先知道这个界限，你的位屏蔽解决方案可能仍然会赢。

您可以通过拒绝小于阈值的值来优化这一点：

uint64_t bounded_prng(uint64_t max) {
    // Compute threshold: 2^64 % max = (2^64 - max) % max = -max % max.
    uint64_t threshold = -max % max;

    uint64_t r;

    do {
        r = prng();
    } while (r < threshold);

    return r % max;
}

基本上，我想知道如果通过Big Crush向前和向后传递，正如xorshift128 +所声称的那样，强烈表明每个单独的位都是满意的随机分开使用它们应该没问题，或者如果我可以让自己陷入困境。

如果你想计算有界的随机值，你只能确保消除任何偏差。 那么有界随机值的质量应该与原始PRNG相匹配。 如果你的PRNG通过Big Crush，你一定会得到高质量的随机数。 你的方法和我展示的任何方法都很好。

---

你正在做的是生成一个均匀分布的int的最常见的方式，Big Crush是一个非常好的测试套件。 它肯定可以确保这些位是单独随机的，以及其他一些你从未想到的东西。

链接地址: http://www.djcxy.com/p/37275.html

上一篇: Quality of PRNG when not using all bits at once

下一篇: Is there a way to test the quality of a PRNG for multidimensional use?