How to generate a random BigInteger value in Java?

Question

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?

Answer 1

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.

Answer 2

The following method uses the BigInteger(int numBits, Random rnd) constructor and rejects the result if it's bigger than the specified 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.

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

Answer 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 ?

Answer 5

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

/**
 * 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;
}

Answer 6

For those who are still asking this question and are looking for a way to generate arbitrarily large random BigIntegers within a positive integer range, this is what I came up with. This random generator works without trying bunch of numbers until one fits the range. Instead it will generate a random number directly that will fit the given range.

private static BigInteger RandomBigInteger(BigInteger rangeStart, BigInteger rangeEnd){
    
    Random rand = new Random();
    int scale = rangeEnd.toString().length();
    String generated = "";
    for(int i = 0; i < rangeEnd.toString().length(); i++){
        generated += rand.nextInt(10);
    }
    BigDecimal inputRangeStart = new BigDecimal("0").setScale(scale, RoundingMode.FLOOR);
    BigDecimal inputRangeEnd = new BigDecimal(String.format("%0" + (rangeEnd.toString().length()) +  "d", 0).replace('0', '9')).setScale(scale, RoundingMode.FLOOR);
    BigDecimal outputRangeStart = new BigDecimal(rangeStart).setScale(scale, RoundingMode.FLOOR);
    BigDecimal outputRangeEnd = new BigDecimal(rangeEnd).add(new BigDecimal("1")).setScale(scale, RoundingMode.FLOOR); //Adds one to the output range to correct rounding
    
    //Calculates: (generated - inputRangeStart) / (inputRangeEnd - inputRangeStart) * (outputRangeEnd - outputRangeStart) + outputRangeStart 
    BigDecimal bd1 = new BigDecimal(new BigInteger(generated)).setScale(scale, RoundingMode.FLOOR).subtract(inputRangeStart);
    BigDecimal bd2 = inputRangeEnd.subtract(inputRangeStart);
    BigDecimal bd3 = bd1.divide(bd2, RoundingMode.FLOOR);
    BigDecimal bd4 = outputRangeEnd.subtract(outputRangeStart);  
    BigDecimal bd5 = bd3.multiply(bd4);      
    BigDecimal bd6 = bd5.add(outputRangeStart);
    
    BigInteger returnInteger = bd6.setScale(0, RoundingMode.FLOOR).toBigInteger();
    returnInteger = (returnInteger.compareTo(rangeEnd) > 0 ? rangeEnd : returnInteger); //Converts number to the end of output range if it's over it. This is to correct rounding.
    return returnInteger;
}   

How does it work?

First it generates a String with random numbers with the same length as the maximum range. For example: with given range of 10-1000 it will generate some number between 0000 and 9999 as a String.

Then it creates BigDecimals to represent the maximum possible value (9999 in previous example) and minimum value (0) and converts the range parameter BigIntegers to BigDecimals. Also in this step to the given range maximum value is added 1 in order to correct rounding errors in the next step.

Then using this formula the generated random number is mapped to the given range:

(generated - inputRangeStart) / (inputRangeEnd - inputRangeStart) * (outputRangeEnd - outputRangeStart) + outputRangeStart

After that it will do a last check whether or not the mapped number fits the given range and sets it to the given range maximum if it doesn't. This is done in order to correct rounding errors.

Answer 7

Just use modular reduction

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

Answer 8

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

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