如何在 Java 中生成一个随机的 BigInteger 值？

Question

我需要生成 0（含）到 n（不含）范围内任意大的随机整数。我最初的想法是调用 nextDouble 并乘以 n，但是一旦 n 大于 2 53 ，结果将不再均匀分布。

BigInteger 具有以下可用的构造函数：

 public BigInteger(int numBits, Random rnd)

构造一个随机生成的 BigInteger，均匀分布在 0 到 (2 numBits - 1) 范围内，包括边界值。

这如何用于获得 0 - n 范围内的随机值，其中 n 不是 2 的幂？

原文由 Bill the Lizard 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

使用循环：

 BigInteger randomNumber;
do {
    randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);

平均而言，这将需要少于两次迭代，并且选择将是统一的。

编辑： 如果您的 RNG 很昂贵，您可以通过以下方式限制迭代次数：

 int nlen = upperLimit.bitLength();
BigInteger nm1 = upperLimit.subtract(BigInteger.ONE);
BigInteger randomNumber, temp;
do {
    temp = new BigInteger(nlen + 100, randomSource);
    randomNumber = temp.mod(upperLimit);
} while (s.subtract(randomNumber).add(nm1).bitLength() >= nlen + 100);
// result is in 'randomNumber'

使用此版本，循环被执行多次的可能性很小（小于 2^100 中的一次机会，即远低于主机在下一秒自发着火的概率）。另一方面， mod() 操作在计算上是昂贵的，所以这个版本可能比以前慢，除非 randomSource 实例特别慢。

原文由 Thomas Pornin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

以下方法使用 BigInteger(int numBits, Random rnd) 构造函数，如果结果大于指定的 n，则拒绝该结果。

 public BigInteger nextRandomBigInteger(BigInteger n) {
    Random rand = new Random();
    BigInteger result = new BigInteger(n.bitLength(), rand);
    while( result.compareTo(n) >= 0 ) {
        result = new BigInteger(n.bitLength(), rand);
    }
    return result;
}

这样做的缺点是构造函数被调用的次数不确定，但在最坏的情况下（n 只是略大于 2 的幂），构造函数的预期调用次数应该只有大约 2 次。

原文由 Bill the Lizard 发布，翻译遵循 CC BY-SA 2.5 许可协议