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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
