Randomizing a BigInteger

Question

I'm looking to randomize a BigInteger. The intent is to pick a number from 1 to 8180385048. Though, from what I noticed, the BigInteger(BitLen, Random) does it from n to X²-1, I'd want some unpredictable number. I tried to make a method that would do it, but I keep running into bugs and have finally given in to asking on here. :P Does anyone have any suggestions on how to do this?

Answer 1

Make a loop and get random BigIntegers of the minimum bit length that covers your range until you obtain one number in range. That should preserve the distribution of random numbers.

Answer 2

Judging from the docs of Random.nextInt(int n) which obviously needs to solve the same problem, they seem to have concluded that you can't do better than "resampling if out of range", but that the penalty is expected to be negligible.

From the docs:

The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2³¹ is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2³⁰+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.

I'd suggest you simply use the randomizing constructor you mentioned and iterate until you reach a value that is in range, for instance like this:

public static BigInteger rndBigInt(BigInteger max) {
    Random rnd = new Random();
    do {
        BigInteger i = new BigInteger(max.bitLength(), rnd);
        if (i.compareTo(max) <= 0)
            return i;
    } while (true);
}

public static void main(String... args) {
    System.out.println(rndBigInt(new BigInteger("8180385048")));
}

For your particular case (with max = 8180385048), the probability of having to reiterate, even once, is about 4.8 %, so no worries :-)

Answer 3

Reiterating if out of range, as suggested in other answers, is a solution to this problem. However if you want to avoid this, another option is to use the modulus operator:

BigInteger i = new BigInteger(max.bitLength(), rnd);
i = i.mod(max);                 // Now 0 <= i <= max - 1
i = i.add(BigInteger.ONE);      // Now 1 <= i <= max