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
– Eric Postpischil, Commented Sep 6, 2020 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
– rici, Commented Sep 6, 2020 at 20:04

chux · Accepted Answer · 2020-09-06 17:01:02Z

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.

chqrlie · Accepted Answer · 2020-09-06 18:02:26Z

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

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related