@Nitish: I'm assuming that Random(0,1) returns 0 and 1 randomly, with equal probability. Let n = ceiling(log_2(b-a+1)). Use the rejection method (http://en.wikipedia.org/wiki/ Rejection_sampling) as follows:
Generate an integer, k, 0 <= k < 2^n, one bit at a time, using Random(0,1) n times. k will be uniformly distributed between 0 and 2^n - 1. If k > b-a, reject k and generate a new one. Otherwise, return k+a. The "algorithm" terminates with probability 1 with an expected number of calls to Random(0,1) of n * 2^n / (b - a + 1). Dave On Jul 6, 12:50 pm, Nitish Garg <nitishgarg1...@gmail.com> wrote: > Describe an implementation of Random(a, b) that only make calls to Random(0, > 1)? > Well I am thinking this way: > > - Divide the range (a,b) in to 2 parts like (a, mid) and (mid, b) where > mid = (a+b)/2 > - Select one of the range using a call to Random(0, 1). > - Then continue dividing the new range and selecting a new based on a > call to Random(0, 1) until we have two elements left. > - From the two elements one can easily be selected by a call to Random(a, > b). > > Is this approach correct? Or something else can be done? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
