Can we do it like this?
Random_bit()
{
......int x= rand_5()%3;
......if(x== 2)
.............return Random_bit();
......else
............return x;
}
This will generate 0 and 1 each with probability 2/5.
Rand_7()
{
........int b1,b2,b3;
........b1 = Random_bit();
........ b2 = Random_bit();
........ b3 = Random_bit();
........If(b1 & b2 & b3 all are zero)
..............return Rand_7();
........else
............return b3*4 + b2*2 + b1*1;
}
Returns a number between 1 and 7 (inclusive) with probability 8/125.
On Tue, Sep 8, 2009 at 11:42 AM, Dufus <[email protected]> wrote:
>
> Hardest part of this problem is to prove that the generated number
> INDEED follow uniform distribution :D
>
> _dufus
>
>
> On Sep 8, 6:57 am, Dave <[email protected]> wrote:
> > Use the rejection technique, something like this:
> >
> > do
> > {
> > do
> > U1 = random_1_to_5();
> > while( U1 == 5 );
> > // At this point, U1 is a uniform integer in the range 1 to 4.
> > U2 = random_1_to_5();
> > if( U1 > 2 )
> > U2 += 5;}
> >
> > while( U2 > 7 );
> > // At this point, U2 is a uniform random integer in the range 1 to 7.
> >
> > It takes on average 45/14 1_to_5 random numbers to make a 1_to_7
> > random number.
> >
> > Dave
> >
> > On Sep 7, 10:56 am, ankur aggarwal <[email protected]> wrote:
> >
> > > Given a random number generator that generates numbers in the range 1
> to
> > > 5, how can u create a random number generator to generate numbers in
> the
> > > range 1 to 7. (remember that the generated random numbers should follow
> a
> > > uniform distribution in the corresponding range)
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
