如何在Java中生成随机BigInteger值？ [英] How to generate a random BigInteger value in Java?

问题描述

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

I need to generate arbitrarily large random integers in the range 0 (inclusive) to n (exclusive). My initial thought was to call nextDouble and multiply by n, but once n gets to be larger than 2⁵³, the results would no longer be uniformly distributed.

BigInteger 提供以下构造函数：

BigInteger has the following constructor available:

public BigInteger(int numBits, Random rnd)

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

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

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

How can this be used to get a random value in the range 0 - n, where n is not a power of 2?

推荐答案

使用循环：

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

平均来说，这将需要不到两次迭代，选择将是统一的。

on average, this will require less than two iterations, and the selection will be uniform.

编辑：如果您的RNG价格昂贵，您可以通过以下方式限制迭代次数：

If your RNG is expensive, you can limit the number of iterations the following way:

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'

对于这个版本，它是非常不可能的循环不止一次（在 2 ^ 100 中少于一次机会，即远小于主机在下一秒内自发着火的概率）。另一方面， mod（）操作的计算成本很高，因此该版本可能比之前的版本慢，除非 rnd 实例，如果异常缓慢。

With this version, it is highly improbable that the loop is taken more than once (less than one chance in 2^100, i.e. much less than the probability that the host machine spontaneously catches fire in the next following second). On the other hand, the mod() operation is computationally expensive, so this version is probably slower than the previous, unless the rnd instance if exceptionally slow.

这篇关于如何在Java中生成随机BigInteger值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！