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

random java biginteger

2022-08-31 14:24:00

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

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

public BigInteger(int numBits, Random rnd)

构造一个随机生成的 BigInteger，均匀分布在 0 到（2^numBits - 1）的范围内（包括 0 到 2 个数字位 - 1）。

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

答案 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

答案 2

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

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次。