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

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.

我需要生成范围为0(包括)到n(排他性)的任意大的随机整数。我最初的想法是调用nextDouble并乘以n，但是一旦n大于253，结果就不再是均匀分布了。

BigInteger has the following constructor available:

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

public BigInteger(int numBits, Random rnd)

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

构造一个随机生成的BigInteger，均匀分布在0到(2numBits - 1)之间，包括。

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

如何用它得到0 - n范围内的随机值，n不是2的幂?

7 个解决方案

#1

Use a loop:

使用一个循环:

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.

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

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

编辑:如果你的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'

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.

这个版本,它是高度不可思议,循环不止一次(2 ^ 100不到一个机会,即主机的概率远远小于自发着火在下一秒)之后。另一方面，mod()操作的计算开销很大，因此这个版本可能比以前的版本慢，除非rnd实例特别慢。

#2

The following method uses the BigInteger(int numBits, Random rnd) constructor and rejects the result if it's bigger than the specified n.

下面的方法使用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;
}

The drawback to this is that the constructor is called an unspecified number of times, but in the worst case (n is just slightly greater than a power of 2) the expected number of calls to the constructor should be only about 2 times.

这其中的缺点是构造函数被调用的次数是不确定的，但是在最坏的情况下(n只是略大于2的幂)，构造函数调用的预期数量应该只有2倍。

#3

The simplest approach (by quite a long way) would be to use the specified constructor to generate a random number with the right number of bits (floor(log2 n) + 1), and then throw it away if it's greater than n. In the worst possible case (e.g. a number in the range [0, 2ⁿ + 1) you'll throw away just under half the values you create, on average.

最简单的方法(通过很长一段路)是使用指定的构造函数来生成一个随机数与正确的比特数(地板(log2 n)+ 1),然后扔掉它如果它大于n。在最糟糕的情况下(例如,数量的范围(0,2 n + 1)你会扔掉一半您创建的值,平均。

#4

Why not constructing a random BigInteger, then building a BigDecimal from it ? There is a constructor in BigDecimal : public BigDecimal(BigInteger unscaledVal, int scale) that seems relevant here, no ? Give it a random BigInteger and a random scale int, and you'll have a random BigDecimal. No ?

为什么不构造一个随机的BigInteger，然后从中构建一个BigDecimal呢?在BigDecimal中有一个构造函数:public BigDecimal(BigInteger unscaledVal, int scale)在这里看起来是相关的，不是吗?给它一个随机的BigInteger和一个随机的scale int，你就会得到一个随机的BigDecimal。没有?

#5

Here is how I do it in a class called Generic_BigInteger available via: Andy Turner's Generic Source Code Web Page

以下是我如何在一个名为Generic_BigInteger的类中完成的:Andy Turner的通用源代码Web页面

/**
 * There are methods to get large random numbers. Indeed, there is a
 * constructor for BigDecimal that allows for this, but only for uniform
 * distributions over a binary power range.
 * @param a_Random
 * @param upperLimit
 * @return a random integer as a BigInteger between 0 and upperLimit
 * inclusive
 */
public static BigInteger getRandom(
        Generic_Number a_Generic_Number,
        BigInteger upperLimit) {
    // Special cases
    if (upperLimit.compareTo(BigInteger.ZERO) == 0) {
        return BigInteger.ZERO;
    }
    String upperLimit_String = upperLimit.toString();
    int upperLimitStringLength = upperLimit_String.length();
    Random[] random = a_Generic_Number.get_RandomArrayMinLength(
        upperLimitStringLength);
    if (upperLimit.compareTo(BigInteger.ONE) == 0) {
        if (random[0].nextBoolean()) {
            return BigInteger.ONE;
        } else {
            return BigInteger.ZERO;
        }
    }
    int startIndex = 0;
    int endIndex = 1;
    String result_String = "";
    int digit;
    int upperLimitDigit;
    int i;
    // Take care not to assign any digit that will result in a number larger
    // upperLimit
    for (i = 0; i < upperLimitStringLength; i ++){
        upperLimitDigit = new Integer(
                upperLimit_String.substring(startIndex,endIndex));
        startIndex ++;
        endIndex ++;
        digit = random[i].nextInt(upperLimitDigit + 1);
        if (digit != upperLimitDigit){
            break;
        }
        result_String += digit;
    }
    // Once something smaller than upperLimit guaranteed, assign any digit
    // between zero and nine inclusive
    for (i = i + 1; i < upperLimitStringLength; i ++) {
        digit = random[i].nextInt(10);
        result_String += digit;
    }
    // Tidy values starting with zero(s)
    while (result_String.startsWith("0")) {
        if (result_String.length() > 1) {
            result_String = result_String.substring(1);
        } else {
            break;
        }
    }
    BigInteger result = new BigInteger(result_String);
    return result;
}

#6

Just use modular reduction

只使用模块化的减少

new BigInteger(n.bitLength(), new SecureRandom()).mod(n)

#7

-2

Compile this F# code into a DLL and you can also reference it in your C# / VB.NET programs

将f#代码编译到一个DLL中，您也可以在c# / VB中引用它。网项目

type BigIntegerRandom() =
    static let internalRandom = new Random()

    /// Returns a BigInteger random number of the specified number of bytes.
    static member RandomBigInteger(numBytes:int, rand:Random) =
        let r = if rand=null then internalRandom else rand
        let bytes : byte[] = Array.zeroCreate (numBytes+1)
        r.NextBytes(bytes)
        bytes.[numBytes] <- 0uy
        bigint bytes

    /// Returns a BigInteger random number from 0 (inclusive) to max (exclusive).
    static member RandomBigInteger(max:bigint, rand:Random) =
        let rec getNumBytesInRange num bytes = if max < num then bytes else getNumBytesInRange (num * 256I) bytes+1
        let bytesNeeded = getNumBytesInRange 256I 1
        BigIntegerRandom.RandomBigInteger(bytesNeeded, rand) % max

    /// Returns a BigInteger random number from min (inclusive) to max (exclusive).
    static member RandomBigInteger(min:bigint, max:bigint, rand:Random) =
        BigIntegerRandom.RandomBigInteger(max - min, rand) + min

#1