Question

Suppose you have access to a random number generator Rng() that generates uniform random numbers in {0, 1, . . . , n − 1}. Design a function uses Rng() generate a uniform random number in {0, 1, . . . , m − 1}, where m ≤ n

Answer 1

Notice that the function rng() can return numbers from anywhere between 0 to (n-1).

If we want to produce a random value between 0 to (m-1), m<=n, and easy step is to limit the range of values by taking the remainder of the number with m.

Consider this example:

Take a random number generator that can generate any number between 0 to 999 (n = 1000). If we then take the remainder of the output of this function with the value 8 (m = 8), the results we get are in the range (0%8) to (999%8). Then, the only values we can get are 0, 1, 2, 3, 4, 5, 6, and 7, regardless of what the value of "n" in the random generator is. Hence, taking the remainder of the random number generator rng() by the value m gives us the desired value.

When m == n, when we take the remainder with n, we just get the original value back.

Hence, we can define the function rng_m():

function rng_m(m): 
    return rng() % m 

(If you liked this answer, feel free to give it a thumbs up. Thank you!)