2

Given a function

int rand1();

which return 0 or 1, with equal probability, implement a function

int rand5();

which returns 0,1,2,3,4,5 with equal probability.

!!! Twist !!! Read before marking it as duplicate...

Number of times you can call rand1() is fixed. You may decide it to be 10 or 20 or 100 for that matter, but NOT any number of rand1() calls. i.e. there is a upper limit on on number of rand1() calls. Also you have to guarantee that rand5() should always return o to 5, with equal probability. It is not acceptable that the code is skewed towards, few extra 0 and 1.

If you think it is NOT POSSIBLE to write such function, then you can let us all know, as to why it is not possible.

EDIT : this is what i have, which I think is not sufficient

int rand5()
{
bitset<3> b;
b[0] = rand1();
b[1] = rand1();
b[2] = rand1();
int i = b;
if(b >= 6)
 return rand5();
return i;
}
20
  • 2
    What has this to do with C++ or C?
    – Kerrek SB
    Aug 19, 2011 at 21:38
  • well you have to write the code in C++ or SOME LANGUAGE . If I say you dont have to write code, then the question will be closed as NOT related to programming. There are many people waiting to do just that. But the fact is I have to implement this code (in C++), to do just the same. I have a sub-optimal solution with no fixed upper bound on calls of rand1(), and I am searching for implementation which doesnt have that limitation. Aug 19, 2011 at 21:40
  • codegolf.stackexchange.com ??
    – Joe
    Aug 19, 2011 at 21:41
  • 4
    Sounds like homework. Please add the word "homework" to the title, and show what you have so far. Explain what your problem is. Aug 19, 2011 at 21:41
  • 1
    @Tomalak : I didnt put homework tag. :( Jared Ng did that. But thanks Tomalak. :) Aug 19, 2011 at 22:05

2 Answers 2

6

Not possible. You can't divide 2^n into 6 evenly.

3
  • 3
    ...which is only required because of the fixed calls to rand1(). Otherwise you could generate 3 bits and simply discard any 6 and 7 results and re-roll. Aug 19, 2011 at 21:53
  • So far my conclusion too. But problem is I have no way of knowing that this is definitive. May be there are other ways to generate this distribution. Aug 19, 2011 at 21:58
  • 1
    Of course there are other ways to generate the distribution. They simply are not compatible with a fixed number of calls to rand1().
    – Thom Smith
    Aug 19, 2011 at 22:06
0

This is what people are doing (whether they know it or not) when they generate a random integer in the range [0, N) from a random floating-point number in the range [0, 1):

// assumed sizeof(unsigned int) == sizeof(float) == 32/CHAR_BIT
// assumed 'float' is IEEE single precision with the mantissa in the
// low bits
unsigned int randN(unsigned int high)
{
    union { unsigned int i; float f; } u;

    u.i = 0;
    for (int j = 0; j < 24; j++)
        u.i = u.i*2 + rand1();

    // u.f will be in the range [0, 0.5)
    // so multiply by twice the desired range
    return (unsigned int)floor(u.f * (high * 2));
}

I suspect this does not produce a perfectly uniform distribution, but it's good enough for most purposes.

2
  • 1
    This is roughly equivalent to just making a random n bit number modulo 6 and accepting the slight bias that occurs because 2^*n* is not divisible by 6. The larger n the smaller the error. The use of float just obfuscates this slightly. Aug 20, 2011 at 2:45
  • Yah. I used float because, as I said, it's pretty common to generate a random integer in [0, N) from a RNG primitive that produces a random float in [0, 1) by exactly this method, accepting any bias. I'm sort of curious what the bias winds up looking like, but not curious enough to actually do the math.
    – zwol
    Aug 20, 2011 at 4:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.