Necessary and Sufficient

A colleague asked me about question (15) in my Uber Geek Challenge post so I thought I'd provide a simplistic explanation as I don't think Wikipedia gives such.

Basically, there are two popular ways of storing negative numbers in a binary number system: one's complement and two's complement. The easiest to understand is, arguably, one's complement. To get the negative of a given binary value when using one's complement you simply flip all the bits. However with zero represented by all zeros in binary, flipping all bits results in all ones and this is interpreted as "-0". Having two values for zero (one positive and one negative) isn't desirable so the alternate approach, two's complement, flips all the bits then adds 1. That ensures you don't get a positive and negative zero, and the only price you pay is a slight asymmetry in the numeric range - one less positive number if you don't count zero as positive.

The image on the right shows the binary representation of 8-bit negative numbers and their positive counterparts.

Question: Given an unbiased PRNG which returns values in the range 0-5, how could you use this function to produce unbiased random numbers in the range 0-7.

Answer: Most people immediately think that they could run the Rand5() twice and return the sum mod 8 however this doesn't produce unbiased results. To get unbiased results every possible result needs to have the same probability.

Consider what the numbers 0-5 look like in binary:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
 

Notice that we have 6 values in total. This is nice and even and will help us no doubt. Now look at the least-significant bits (LSB) of these 6 values. Three have a one and three have a zero. i.e. 0s and 1s have an equal likelihood of appearing in the LSB of the returned random number.  The same cannot be said of the other 2 columns.

Now let us add 6 and 7 to our binary table:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

This table shows the binary representation of all possible values that could be returned from the function we need to produce - Rand7(). Examining the distribution of zeros and ones in each column we can see that every column have an even distribution of 0s and 1s.  So we can produce Rand7() as follows:

        static uint Rand7()
        {
            return (uint)(((Rand5() & 1) << 2) + ((Rand5() & 1) << 1) + (Rand5() & 1));
        }

What this is doing is calling the Rand5() function 3 times, masking off the LSB which we know will be evenly distributed between 0s and 1s, and shifting them into each of the 3 bit positions, then converting the resulting binary representation to an unsigned integer. The result is an unbiased pseudo-random drawing from the range 0-7 inclusive.