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

Question

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

BigInteger 有以下构造函数可用:

public BigInteger(int numBits, Random rnd)

构造一个随机生成的BigInteger,均匀分布在0到(2 ^numBits - 1)的范围内,包括0和(2 ^numBits - 1).

如何使用它来获得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实例特别慢.

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

Answer 3

最简单的方法(通过相当长的路径)将使用指定的构造函数生成具有正确位数(floor(log2 n) + 1)的随机数,然后如果它大于n则抛弃它.在最糟糕的情况下(例如,[0,2 ⁿ + 1] 范围内的数字,平均而言,您将丢弃的数值略低于您创建的值的一半.