gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:41:58 27 4
gpt4 key购买 nike

我目前在我的项目中使用 xorshift128+,我知道它通过了 Big Crush,并且被认为可以根据其速度生成相当高质量的随机数。但是,它会生成 64 位数字,而我需要的绝大多数随机数都是小整数(介于 0 和 100 之间)。

现在,使用 % 将 64 位随机数减少到所需范围会导致分布不均匀(某些数字出现的次数比其他数字多),并且在 2 的幂的情况下会完全丢弃大部分位.生成数字直到某些东西在范围内的方法会导致更均匀的分布,但是对于小数字来说有点问题,而且当我已经有比开始时需要的更多的方式时,生成更多的位感觉很愚蠢。

因此,我实现了一个系统,该系统采用所需的最少位数(寻找最接近的 2 的幂,例如,如果我需要 0-95 的范围,我将采用 7 位 (2^7 = 128) 并且继续生成 7 位,直到我得到小于 95 的值,这应该总是有超过 50% 的概率,否则我只能少使用一位)

无论如何,系统已经到位,基本的统计测试表明它按预期工作,而且运行速度非常快。但是,我一直无法在修改后的系统上运行 TestU01(似乎没有内置对动态位大小的支持)并且原始论文对我来说有点太密集了。

基本上,我想知道是否像 xorshift128+ 声称的那样向前和向后传递 Big Crush,强烈建议每个单独的位都是令人满意的随机并且单独使用它们应该没问题,或者我是否可以设置自己麻烦。此外,可选的任何测试套件都可以让我凭经验验证我的生成器的统计质量。

最佳答案

The method where you generate numbers until something is in-range results in a more uniform distribution, but it's somewhat problematic with small numbers [...].

对于像下面的 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;
}

但是还有另一种有效的算法。您可以使用适合 uint64_tmax 的最大倍数来扩展阈值,即 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;
}

Basically, I'm wondering if passing Big Crush both forwards and backwards, as xorshift128+ is purported to do, strongly suggests that every individual bit is satisfactorily random and using them separately should be fine, or if I could be setting myself up for trouble.

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

关于algorithm - 不一次使用所有位时的 PRNG 质量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34610175/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com