CODEWITHSUNDEEP
javarandom
user973931
user973931

Reputation: 515

Random Number generation Issues

This question was asked in my interview. random(0,1) is a function that generates integers 0 and 1 randomly. Using this function how would you design a function that takes two integers a,b as input and generates random integers including a and b.

I have No idea how to solve this.

Upvotes: 3

Views: 413

Answers (4)

Raks
Raks

Reputation: 870

function randomBetween(int a, int b){
int x = b-a;//assuming a is smaller than b
float rand = random();
return a+Math.ceil(rand*x);
}

Upvotes: 0

Chris Hopman
Chris Hopman

Reputation: 2102

So we have randomBit() returning 0 or 1 independently, uniformly at random and we want a function random(a, b) that returns a value in the range [a,b] uniformly at random. Let's actually make that the range [a, b) because half-open ranges are easier to work with and equivalent. In fact, it is easy to see that we can just consider the case where a == 0 (and b > 0), i.e. we just want to generate a random integer in the range [0, b).

Let's start with the simple answer suggested elsewhere. (Forgive me for using c++ syntax, the concept is the same in Java)

int random2n(int n) {
   int ret = n ? randomBit() + (random2n(n - 1) << 1) : 0;
}
int random(int b) {
    int n = ceil(log2(b)), v;
    while ((v = random2n(n)) >= b);
    return v;
}

That is-- it is easy to generate a value in the range [0, 2^n) given randomBit(). So to get a value in [0, b), we repeatedly generate something in the range [0, 2^ceil(log2(b))] until we get something in the correct range. It is rather trivial to show that this selects from the range [0, b) uniformly at random.

As stated before, the worst case expected number of calls to randomBit() for this is (1 + 1/2 + 1/4 + ...) ceil(log2(b)) = 2 ceil(log2(b)). Most of those calls are a waste, we really only need log2(n) bits of entropy and so we should try to get as close to that as possible. Even a clever implementation of this that calculates the high bits early and bails out as soon as it exits the wanted range has the same expected number of calls to randomBit() in the worst case.

We can devise a more efficient (in terms of calls to randomBit()) method quite easily. Let's say we want to generate a number in the range [0, b). With a single call to randomBit(), we should be able to approximately cut our target range in half. In fact, if b is even, we can do that. If b is odd, we will have a (very) small chance that we have to "re-roll". Consider the function:

int random(int b) {
    if (b < 2) return 0;
    int mid = (b + 1) / 2, ret = b;
    while (ret == b) {
         ret = (randomBit() ? mid : 0) + random(mid);
    }
    return ret;
}

This function essentially uses each random bit to select between two halves of the wanted range and then recursively generates a value in that half. While the function is fairly simple, the analysis of it is a bit more complex. By induction one can prove that this generates a value in the range [0, b) uniformly at random. Also, it can be shown that, in the worst case, this is expected to require ceil(log2(b)) + 2 calls to randomBit(). When randomBit() is slow, as may be the case for a true random generator, this is expected to waste only a constant number of calls rather than a linear amount as in the first solution.

Upvotes: 0

UmNyobe
UmNyobe

Reputation: 22890

I hate this kind of interview Question because there are some answer fulfilling it but the interviewer will be pretty mad if you use them. For example, 

Call random, 
if you obtain 0, output a
if you obtain 1, output b

A more sophisticate answer, and probably what the interviewer wants is

init(a,b){
  c = Max(a,b)
  d = log2(c) //so we know how much bits we need to cover both a and b
}

Random(){
 int r = 0;
 for(int i = 0; i< d; i++)
    r = (r<<1)| Random01();
 return r;
 }

You can generate random strings of 0 and 1 by successively calling the sub function.

Upvotes: 0

CommonMan
CommonMan

Reputation: 3928

We can do this easily by bit logic (E,g, a=4 b=10)

  1. Calculate difference b-a (for given e.g. 6)
  2. Now calculate ceil(log(b-a+1)(Base 2)) i.e. no of bits required to represent all numbers b/w a and b
  3. now call random(0,1) for each bit. (for given example range will be b/w 000 - 111)
  4. do step 3 till the number(say num) is b/w 000 to 110(inclusive) i.e. we need only 7 levels since b-a+1 is 7.So there are 7 possible states a,a+1,a+2,... a+6 which is b.
  5. return num + a.

Upvotes: 4

Related Questions