Dave,
You are correct about the first approach. It is biased towards '1' and of
course 000 goes waste.
With the second approach, I couldn't find a uniform distribution, because there
is no power of 5 which is a multiple of 7, as they are relatively prime. For
the errornous approach where 1 transition goes waste, code should be very
simple. Here is a prototype,
int rand_1_7() {
int f = 15624/7;
// since transitions are already random, lets divide 15624 uniformly for
each of 1,2,..,7
// lets imagine a number with base 5, so 15625 is 1000000, and 15624 will
be 444444.
// suppose each call to rand_1_5() gives one bit for the number
int b1 = rand_1_5()-1; // 1 is substracted to bring the numbers to the range
[0,4]
int b2 = rand_1_5()-1;
int b3 = rand_1_5()-1;
int b4 = rand_1_5()-1;
int b5 = rand_1_5()-1;
int b6 = rand_1_5()-1;
int num = (5^5)*b6 + (5^4)*b5 + (5^3)*b4 + (5*2)*b3 + (5^1)*b2 + (5^0)*b1;
if(num <= f) return 1;
if(num <= 2*f) return 2;
if(num <= 3*f) return 3;
if(num <= 4*f) return 4;
if(num <= 5*f) return 5;
if(num <= 6*f) return 6;
return 7;
}
________________________________
From: Dave <[email protected]>
To: Algorithm Geeks <[email protected]>
Sent: Wednesday, 9 September, 2009 2:42:26 AM
Subject: [algogeeks] Re: random number...
Manish, your first approach doesn't work. You will notice that b1, b2,
and b3 each are 0 2/5 of the time and 1 3/5 of the time, so the return
value is not uniformly distributed.
For approach 2, what do you have to do if you want an exactly uniform
distribution as a result? Or what would the code look like for one of
your non-exact methods?
Dave
On Sep 8, 1:32 pm, manish bhatia <[email protected]> wrote:
> I can think of 2 appraches.
>
> [1] Similar to something already suggested. Just adding my 2 cents.
>
> 1 to 7 digits can be represented by 3 bits. So going by that,
>
> int rand_1_7() {
> b1 = rand_1_5()*(7/5) > (7/2) ? 1 : 0;
> b2 = rand_1_5()*(7/5) > (7/2) ? 1 : 0;
> b3 = rand_1_5()*(7/5) > (7/2) > 1 : 0;
> return (b1*4 + b2*2 + b3*1);
>
> }
>
> [2] What we are trying to do is map numbers 1 to 5 to numbers 1 to 7. Of
> course mapping 5 items to 7 items is not straight forward. So lets not map
> items, but map transitions. Suppose an imaginary initial state x. Now when we
> call rand_1_5(), we have one of the following transition,
> 1) x -> 1
> 2) x -> 2
> 3) x -> 3
> 4) x -> 4
> 5) x -> 5
> Now, lets call rand_1_5() again, and remember the last transition, viz.
> 1) x -> 1 -> 1
> 2) x -> 1 -> 2
> ....
> 24) x -> 5 -> 4
> 25) x -> 5 -> 5
>
> So we have 25 transitions. Divide it by 7, we get 4 as remainder and 3 as
> quotient i.e. if we each number 1 to 7, three of these 25 transitions each,
> we get 4 unused transitions. Lets take it to next level. We get 25*5 = 125
> transitions. Divide by 7, we get 6 unused transitions. Still another level,
> get us 125*5 = 625 transition, divide by 7, we get 2 as remainder. So nearest
> we get is, 625*5*5 = 15624. Dividing by 7, we get 1 as remainder. So in 15625
> transitions, (by calling rand_1_5() 6-times), we can assign 2232
> unique-transitions to each on of 1,2,..,7. With just 1 un-assigned
> transition, we get 1/15625 part-error, or 0.0064% error.
>
> Comments?
>
> 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)
>
> Love Cricket? Check out live scores, photos, video highlights and more.
> Click herehttp://cricket.yahoo.com
Looking for local information? Find it on Yahoo! Local
http://in.local.yahoo.com/
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
