Scaling Random Bytes to Selected Integer Range

Question

I have a file of true random bytes. I want a function that returns a random integer in the range given by taking a byte from the file and scaling it. (is this the right word?)

public int getInt(int l, int h) throws IOException {
    int m = (h - l) + 1;            // number of ranges needed
    int r = 256 / m;                // size of byte range
    int x = (r * m) - 1;            // maximum allowable byte value
    int b;
    do {
        try {                       // get random byte from file
            b = ram.readUnsignedByte();
        } catch (EOFException e) {  // catch EOF, reset pointer
            b = 255; ram.seek(0);   // and set b to maximum value
        }                           // so test will fail.
    } while(b > x);                 // if byte is greater than
                                    // allowable value, loop.
    return (b / r) + l;             // return random integer
}                                   // within requested range

So here is my function. I am worried about destroying the true randomness of the bytes in the file by scaling it. I read that I need to throw out any number that would be above an allowed max value (so for a number 0-9, the max value is 249 because I only have 7 values left to distribute to 10 different groups). Does my implementation look correct?

Also, I am wondering, just by invalidating certain bytes that are too large, am I skewing the distribution in any way?

Answer 1

Yes, to avoid bias, you can't use modulo, you have to throw out results which are not in range.

Key to success in programming is splitting your task up in suitable sub-tasks. Quick spec:

1. add a function to calculate how many bits are needed to store a given number
2. add a class which reads and buffers bytes from the randomness file, and has method to give you an integer with some number of bits taken from the file (rest of bits 0).
3. add the actual method to get your random number:
   • calculate the range of result, and from it calculate the number of bits needed
   • loop getting the bits, adding lower bound, retrying if result more than upper bound

Note about step 2: first implementation can be pretty crude, you can just get 4 bytes as integer and throw out extra bits, for example. Later you can optimize this class to keep unused bits and use them next time, to avoid wasting random bits. Since getting genuinely good random bits is usually somewhat expensive, this optimization is probably worth doing for serious use.

For bit operations, see for example this SO question: Java "Bit Shifting" Tutorial?