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

问题描述

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

BigInteger 有以下可用的构造函数:

public BigInteger(int numBits, Random rnd)

<块引用>

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

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

解决方案

使用循环:

BigInteger randomNumber;做 {randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);} while (randomNumber.compareTo(upperLimit) >= 0);

平均而言，这将需要少于两次迭代，并且选择将是统一的.

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

int nlen = upperLimit.bitLength();BigInteger nm1 = upperLimit.subtract(BigInteger.ONE);BigInteger 随机数，温度；做 {temp = new BigInteger(nlen + 100, randomSource);randomNumber = temp.mod(upperLimit);} while (s.subtract(randomNumber).add(nm1).bitLength() >= nlen + 100);//结果在 'randomNumber'

在这个版本中，循环被多次执行的可能性很小(2^100 中不到一次，即远小于主机自发着火的概率下一秒).另一方面，mod() 操作的计算量很大，所以这个版本可能比前一个版本慢，除非 randomSource 实例特别慢.

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 has the following constructor available:

public BigInteger(int numBits, Random rnd)

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

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

解决方案

Use a loop:

BigInteger randomNumber;
do {
    randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);

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

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

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'

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 randomSource instance is exceptionally slow.

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