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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (22)

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

BigInteger 有以下构造函数可用:

public BigInteger(int numBits, Random rnd)

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

这怎么能用来得到一个在0 - n范围内的随机值,其中n不是2的幂?

提问于
用户回答回答于

使用循环:

BigInteger r;
do {
    r = new BigInteger(n.bitLength(), rnd);
} while (r.compareTo(n) >= 0);

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

如果你的RNG很昂贵,你可以通过以下方式限制迭代次数:

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

用户回答回答于

下面的方法使用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倍。

扫码关注云+社区