Generate integer random number using available binaryrandom (which return 0 or 1) function

Question

In a recent interview, I came through the below question

Given a function BinaryRandom() which returns 0 or 1 randomly, create a function int MyRandom(int) which creates a random number less or equal to the given input using BinaryRandom().

As I am a daily stack overflow and GeeksForGeeks user and I recall a similar kind of problem on GeeksForGeeks, see below link

https://www.geeksforgeeks.org/implement-random-0-6-generator-using-the-given-random-0-1-generator/

The only difference is on the GeeksForGeeks range was 0-6 and in my case range is <=N (N is input integer number).

and the above solution is derived from SO using the following link

Creating a random number generator from a coin toss.

As I beginner in Algorithm, I find it hard to understand above. Can anyone please suggest a simple solution to the above question? or give a simple understanding of it?

Answer 1

Given a function BinaryRandom() which returns 0 or 1
create a function int MyRandom(int) which creates a random number less or equal to the given input

int MyRandom(int max);

1. Find bit-width of max --> bitwidth. Maybe count right shifts until 0. E.g. with max == 42, we need 6 bits.

2. Form random number by calling BinaryRandom(). E.g. with 6 bits, that will form a number [0...63].

   int r = 0;
   // Double the value each iteration and add new bit.
   for (i = 0; i<bitwidth; i++) r = 2*r + BinaryRandom();  
   

3. Insure not out of range: If r > max, repeat step 2.

4. Return r.

There are ways (not shown) to reduce the chance of having to redo step 2, yet we want to avoid biasing the results by doing something like r_from_more_than_6_iterations%42.

Answer 2

Building on chux' answer here is a simple implementation:

int MyRandom(int max) {
    for (;;) {
        int r = 0;
        for (m = max; m > 0; m >>= 1) {
            r += r + BinaryRandom();
        }
        if (r <= max || max < 0)
            return r;
    }
}