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

Question

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

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

public BigInteger(int numBits, Random rnd)
构造一个随机生成的BigInteger，该整数均匀地分布在0到（2 numBits -1）（包括0和2 ）之间。

如何使用它来获取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实例异常慢。