Tuesday, September 21, 2010

Random generation

Given a random generator function rand04() that generates random numbers between 0 and 4 (i.e., 0,1,2,3,4) with equal probability. Write a random genartor rand07() that generates numbers between 0 to 7 (0,1,2,3,4,5,6,7) with equal probability.


  1. Use rand04() to generate binary stream. Produce 0 if rand04() returns 0 or 1, produce 1 if random04() returns 2 or 3, skip if rand04() returns 4.

    Split stream to 3-bit units, these are binary encoded random values in range 0..7

  2. Take two samples A and B and form C=5*A+B which is a random number from 0 to 24 inclusive.
    If C<24, return C/3 as the answer. Else repeat the generation and test until it does succeed.