java - 如何在 Java 中生成随机 BigInteger 值？

Question

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

BigInteger有以下可用的构造函数:

public BigInteger(int numBits, Random rnd)

Constructs a randomly generated BigInteger, uniformly distributed over the range 0 to (2^numBits - 1), inclusive.

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

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 实例特别慢。