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?

You need to state a lower limit. For example, if N is 3, there are infinitely many integers less than N: 2, 1, 0, −1, −2, −3,… Likely your lower limit is 0 or 1 (inclusive), but we cannot know which until you state it. — Eric Postpischil, Sep 06 '20 at 16:53
"I find it hard to understand" is not a very precise statement. Can you try to find a more precise statement? Is there some place in the answer to the SO where you read a sentence and couldn't quite grasp it? Can you turn that into a concrete question which you can ask? — rici, Sep 06 '20 at 20:04

chux - Reinstate Monica · Accepted Answer · 2020-09-06T17:01:02.570

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);

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

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();

Insure not out of range: If r > max, repeat step 2.
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.

score 2 · Answer 2 · answered Sep 06 '20 at 18:02

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;
    }
}

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

2 Answers2