Write a C++ program to generate random distribution between 0 to 5 given rand1() which returns 0 or 1 at random

Question

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

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. — Ajeet Ganga, Aug 19 '11 at 21:40
Sounds like homework. Please add the word "homework" to the title, and show what you have so far. Explain what your problem is. — Cheers and hth. - Alf, Aug 19 '11 at 21:41
Possible duplicate of [How to generate a random number from specified discrete distribution?](http://stackoverflow.com/questions/4207238/how-to-generate-a-random-number-from-specified-discrete-distribution) — Greg Hewgill, Aug 19 '11 at 21:42
@Ajeet Rather than just post the problem, show us what you have so far or where you're specifically stuck. Also, retagging as 'homework'. — Jared Ng, Aug 19 '11 at 21:43
This may be more suitable for statistics.stackexchange.com... — Matteo Italia, Aug 19 '11 at 21:45
@Ajeet: That you will be writing it in C++ is not particularly relevant; you are not ready to implement this algorithm yet. You are still trying to _design_ it (mathematically), which has nothing at all to do with C++. — Lightness Races in Orbit, Aug 19 '11 at 21:45
@Alf P : This is a homework ? Why dont you try solving it ? I doubt this tough question would become homework . IMHO This is something that will separate a veteran programmer from learnt-ten-program-answers-yesterday. — Ajeet Ganga, Aug 19 '11 at 21:46
@Ajeet: If it's not homework, remove the `homework` tag. And don't mind Alf; he thinks _everything_'s homework :P — Lightness Races in Orbit, Aug 19 '11 at 21:47
@Alf : So you solved it ? Please please give the answer. May be I am not smart enough to understand the difference between trivial and tough. — Ajeet Ganga, Aug 19 '11 at 21:54
@Ajeet: fishing for answers won't help you. i suggest you just think about it. e.g. think about how an ordinary random generator works. — Cheers and hth. - Alf, Aug 19 '11 at 22:05
@Tomalak : I didnt put homework tag. :( Jared Ng did that. But thanks Tomalak. :) — Ajeet Ganga, Aug 19 '11 at 22:05
@Alf : dude, I dont get it. Are we all not on stack-exchange for "answers" ? Pardon me but I agree my thinking phase was really short and I couldnt come up with answer for that. — Ajeet Ganga, Aug 19 '11 at 22:08
@Ajeet I'm sorry, your question did look very much like homework. In the future, please try to include some explanation of what you've attempted, or where exactly you're stuck. Posting a question that reads "Implement this" doesn't show the effort you've made on your part. — Jared Ng, Aug 20 '11 at 00:10
While impossible to get a finite solution in the worst case, it is quite possible on average. Here is one which takes on average 11/3 iterations. I am sure that it is possible to to do better though: `int rand5() { int b = 0; while(rand1() == b) { b ^= 1; } return 3*rand1() + (b ? 2 : rand1()); }` — Mikola, Aug 20 '11 at 00:27
@Jared : Point taken. Next time I will post the existing solution which I want to improve upon. — Ajeet Ganga, Aug 20 '11 at 01:06
@Ajeet: check for solution: http://stackoverflow.com/questions/7128608 — Nicolae Dascalu, Aug 20 '11 at 01:24
@joe: While a good puzzle for [CodeGolf.SE](http://codegolf.stackexchange.com) could be constructed from this question, in it's current form it is nor even remotely suitable. //doffs CodeGolf.SE moderator hat — dmckee --- ex-moderator kitten, Aug 20 '11 at 21:20

score 6 · Accepted Answer · answered Aug 19 '11 at 21:45

6

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

answered Aug 19 '11 at 21:45

Thom Smith

13,916
6
45
91

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. – Ben Jackson Aug 19 '11 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. – Ajeet Ganga Aug 19 '11 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 '11 at 22:06

score 0 · Answer 2 · answered Aug 19 '11 at 22:51

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.

answered Aug 19 '11 at 22:51

zwol

135,547
38
252
361

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. – Ben Jackson Aug 20 '11 at 02: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 '11 at 04:26

Write a C++ program to generate random distribution between 0 to 5 given rand1() which returns 0 or 1 at random

2 Answers2