3

I have an application where I need to measure how many bits of randomness an algorithm consumes. I have instrumented a subclass of Random to do this by overriding Random.next(int) to increment a counter before calling its parent's method.

I have run into some issues with the implementation of the nextInt(int) method, because it will always draw 32 bits even when the range is a power of two. For other ranges there are even more problems: the method is not uniform---it only retries once for the case where the original value drawn is greater than the greatest multiple of the range lower than Integer.MAX_VALUE--- and it still uses more bits of randomness than are needed.

How can I implement a better version of nextInt(int) that uses only the bare minimum number of random bits needed to determine a value within the range, while being perfectly uniform? It does not need guaranteed termination (not possible anyway), just termination with probability 1.

Edit:

Here is what I have so far:

int nextInt(int max){
    int n = Integer.numberOfTrailingZeros(max);
    return next(n) + nextOddInteger(max >> n) << n;
}

This might not exactly be correct, but essentially this factors out all n twos from num, generates a random number with n bits, and prepends nextOddInteger(num) to the resulting bits. nextOddInteger would generate a random integer up to a number whose prime factorization contains no twos. How can I implement this part in a very randomness-efficient way?

AJMansfield
  • 4,039
  • 3
  • 29
  • 50
  • Java's `Random` class is just a LCPRNG, e.g. the most basic type available. On *NIX, you could draw bits directly from `/dev/random`, but I wouldn't recommend it for cross-platform java. – Richard J. Ross III Aug 04 '14 at 02:40
  • @RichardJ.RossIII The quality of the underlying RNG is not currently an issue at this point, just the number of bits it would take (assuming they were good) to select the integer in a uniformly random fashion. I will be replacing the underlying RNG eventually, but I am working on this part first. – AJMansfield Aug 04 '14 at 02:49
  • 1
    Does this answer your question? [How to generate a random integer in the range \[0,n\] from a stream of random bits without wasting bits?](https://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits) – Peter O. Feb 14 '23 at 23:16

1 Answers1

0

Sounds like you should draw all the bits, slap them in a persistent queue, and consume them by popping the bits as needed. Only draw new random bits when you run out.

e.g. if Random.next draws 32 bits and you need 8, then you will only need to draw once for every four calls that need 8 bits each.

djechlin
  • 59,258
  • 35
  • 162
  • 290
  • The issue here is not the the number of bits that `next(int)` throws away before outputting, but the number of bits `nextInt(int)` is consuming. – AJMansfield Aug 04 '14 at 02:43
  • @AJMansfield but the next time you call nextInt it wouldn't need to draw at all since there's enough left over. – djechlin Aug 04 '14 at 02:47
  • If you read the docs, `next(int)` already provides for that. You specify the desired number of bits as the function's parameter. – AJMansfield Aug 04 '14 at 02:52
  • @AJMansfield then I don't understand your question, at least the first problem of 2-even ranges overconsuming. – djechlin Aug 04 '14 at 05:51
  • I have added more info to my question that may explain what the issue is. – AJMansfield Aug 04 '14 at 08:53