1 minute read

Generate Uniform Random Numbers - Elements of Programming Interviews (EPI)

Problem:

Implement a function that returns a random integer between \(a\) and \(b\) inclusive with equal probability. You are given a function that generates a 1 or a 0 randomly.

Solution:

We can use the random number generator provided to us to generate bits randomly. We can keep generating a random bit and then shifting it and storing it in a result variable until we have the desired number of bits which will be the same as the number of bits necessary to represent our range.

Example: \(a = 3 \\ b = 24 \\ result = 0 \\ i = 0\) The number of bits needed to represent this range 24-3 = 21 is 5. So we run a loop with 5 iterations and in each iteration we generate a random bit for our result.

  1. Generate random number. result = result | (random_number << i). i = i + 1.
  2. Generate random number. result = result | (random_number << i). i = i + 1. Keep Repeating until we have a result. Check if that result is in the range i.e result <= 21 if yes then shift the result into our range by adding the lower bound \(a\) to our result: result = result + a and that is our answer. Otherwise if result is not in the range then we just run the whole loop again.

In code. Note that zero_one_random() is a provided function that generates a random number from 0, 1:

def uniform_random(lower_bound: int, upper_bound: int) -> int:
    """Generate random int in given range"""
    r = upper_bound - lower_bound
    while True:
        result = 0
        current_bit = 0
        while True:
            result = result | (zero_one_random() << current_bit)
            r >>= 1
            if not r:
                break
            current_bit += 1
        r = upper_bound - lower_bound
        if result <= r:
            return result + lower_bound