3

You are given a function let’s say bin() which will generate 0 or 1 with equal probability. Now you are given a range of contiguous integers say [a,b] (a and b inclusive).

Write a function say rand() using bin() to generate numbers within range [a,b] with equal probability

geeky
  • 135
  • 2
  • 10

4 Answers4

5

The insight you need is that your bin() function returns a single binary digit, or "bit". Invoking it once gives you 0 or 1. If you invoke it twice you get two bits b0 and b1 which can be combined as b1 * 2 + b0, giving you one of 0, 1, 2 or 3 with equal probability. If you invoke it thrice you get three bits b0, b1 and b2. Put them together and you get b2 * 2^2 + b1 * 2 + b0, giving you a member of {0, 1, 2, 3, 4, 5, 6, 7} with equal probability. And so on, as many as you want.

Your range [a, b] has m = b-a+1 values. You just need enough bits to generate a number between 0 and 2^n-1, where n is the smallest value that makes 2^n-1 greater than or equal to m. Then just scale that set to start at a and you're good.

So let's say you are given the range [20, 30]. There are 11 numbers there from 20 to 30 inclusive. 11 is greater than 8 (2^3), but less than 16 (2^4), so you'll need 4 bits. Use bin() to generate four bits b0, b1, b2, and b3. Put them together as x = b3 * 2^3 + b2 * 2^2 + b1 * 2 + b0. You'll get a result, x, between 0 and 15. If x > 11 then generate another four bits. When x <= 11, your answer is x + 20.

Erick G. Hagstrom
  • 4,873
  • 1
  • 24
  • 38
2

Help, but no code:

  • You can shift the range [0,2 ** n] easily to [a,a+2 ** n]
  • You can easily produce an equal probability from [0,2**n-1]
  • If you need a number that isn't a power of 2, just generate a number up to 2 ** n and re-roll if it exceeds the number you need
Carlos
  • 5,991
  • 6
  • 43
  • 82
  • Carlos :I could not understand your logic http://stackoverflow.com/questions/21119930/how-to-generate-a-random-number-with-equal-probability-in-a-given-interval – geeky Feb 23 '16 at 10:09
  • Can you please explain your logic – geeky Feb 23 '16 at 10:10
  • @geeky what do you not understand? Say you want a number from 0 to 5. Generate a number from 0 to 7. If it's 6 or 7, do it until again. For a number from 25 to 30, just add 25 to the result. – Carlos Feb 23 '16 at 10:15
1

Subtract the numbers to work out your range:

Decimal: 20 - 10 = 10
Binary : 10100 - 01010 = 1010

Work out how many bits you need to represent this: 4.

For each of these, generate a random 1 or 0:

num_bits = 4
rand[num_bits]
for (x = 0; x < num_bits; ++x)
  rand[x] = bin()

Let's say rand[] = [0,1,0,0] after this. Add this number back to the start of your range.

Binary: 1010 + 0100 = 1110
Decimal: 10 + 4 = 14
Michael
  • 41,989
  • 11
  • 82
  • 128
0

You can always change the range [a,b] to [0,b-a], denote X = b - a. Then you can define a function rand(X) as follows:

function int rand(X){
   int i = 1;
   // determine how many bits you need (see above answer for why)
   while (X < 2^i) {
      i++;
   }
   // generate the random numbers
   Boolean cont = true;
   int num = 0;
   while (cont == true) {
      for (j = 1 to i) {
         // this generates num in range [0,2^i -1] with equal prob
         // but we need to discard if num is larger than X
         num = num + bin() * 2^j;
      }
      if (num <= X) { cont = false}
   }
   return num;
}
Jimmy
  • 187
  • 7