On Jun 28, 9:30 am, Debajyoti Sarma <[email protected]> wrote: > How to implement random function ? > int random(int n); //this function is availabe in stdlib.h in C , only > dos supportability. > this should return numbers from 0 to n-1 with equal probability.
First implement a good linear congruential generator as described at http://en.wikipedia.org/wiki/Linear_congruential_generator . Say this is rand(). Now assume RAND_MAX is the largest int this generator can produce. Then you want int random(int n) { int r, lim = (RAND_MAX + 1) / n * n; do { r = rand(); // call the linear congruential generator } while r >= lim; return r % n; } The loop ensures that the highest (n-1) or fewer values produced by rand() don't skew the results. For example if RAND_MAX is 5 (i.e. 6 random values are available) and n is 4, then the loop throws away 4 and 5 because they would cause 0 and 1 to be returned with twice the probability of 2 and 3. -- 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?hl=en.
