一种更高效的生成随机整数的方法

Question

一种更高效的生成随机整数的方法

3

我有一个应用程序，需要测量算法消耗了多少位的随机性。我已经通过重写Random.next(int)方法来增加计数器并调用其父类方法的方式，对Random子类进行了仪表化。

实现nextInt(int)方法时遇到了一些问题，因为即使范围是2的幂，它也总是绘制32位。对于其他范围，问题更多：该方法不均匀——仅针对原始值大于小于Integer.MAX_VALUE最大倍数的范围，重试一次——并且它仍然使用比所需位数更多的随机位。

如何实现更好的nextInt(int)版本，仅使用确定范围内值所需的最少随机位数，同时完全均匀？它不需要保证终止（无论如何不可能），只需要具有1的概率终止。

编辑：

以下是我目前的进展：

int nextInt(int max){
    int n = Integer.numberOfTrailingZeros(max);
    return next(n) + nextOddInteger(max >> n) << n;
}

这可能不完全正确，但本质上它会从 num 中分解出所有的 n 个数字二，并生成一个具有 n 位的随机数，并将 nextOddInteger（num） 前缀添加到结果中。 nextOddInteger 将生成一个随机整数，该整数最大为其质因数分解不包含数字二。如何以非常高效的随机方式实现这一部分？

- AJMansfield

Java的Random类只是一个LCPRNG，例如最基本的类型。在*NIX上，您可以直接从/dev/random中提取位，但我不建议在跨平台的Java中这样做。 - Richard J. Ross III

@RichardJ.RossIII 目前底层 RNG 的质量并不是问题，只是假设它们是好的，选择整数以均匀随机方式所需的位数。我最终将替换底层 RNG，但我现在正在处理这部分内容。 - AJMansfield

1

这个回答解决了你的问题吗？如何从一串随机位中生成一个范围在[0，n]内的随机整数而不浪费位？ - Peter O.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- djechlin · Answer 1

听起来你应该把所有的位都画出来，放进一个持久队列中，并在需要时通过弹出位来消耗它们。只有在用完时才绘制新的随机位。

例如，如果 Random.next 绘制了 32 位，而你需要 8 位，则每四个调用需要 8 位时，你只需要绘制一次。