Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!apple!vsi1!zorch!xanthian From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) Newsgroups: comp.sys.amiga.tech Subject: Re: rand() within a range. Message-ID: <1990Dec6.033145.22855@zorch.SF-Bay.ORG> Date: 6 Dec 90 03:31:45 GMT References: <666@sheoak.bcae.oz> <540@ssp9.idca.tds.philips.nl> Organization: SF-Bay Public-Access Unix Lines: 88 dolf@idca.tds.philips.nl (Dolf Grunbauer) writes: > 737104@sheoak.bcae.oz (David Thiele) writes: >> Is there a way to generate random numbers within a certain range in >> Lattice C??. Ive done it with the following code but it's not very >> elegant (or fast!), > By the way: why do you want to set seed explicitly before each rand > call ? Probably what will do also is: > Random(range) > int range; > { > if range = 0 > return(0); > else return (rand() % range); > } > and call 'srand' only in some initialisation function or main. Nope. You don't want to do that; it gives you a biased sample. To see the worst case, suppose, where MAXINT is the largest possible output of rand(), that range is approximately 2*MAXINT/3. Then you're going to get about twice as many samples in the interval from zero to range/2 -1, as in range/2 to range -1. In psuedocode, you want: #define MAXINT /* as whatever 2^31-1 is, assuming 32 bit integers */ Random(int range) { int limit, work1, work2, work3; /* Goal: Use as much of the possible returned range 0 to MAXINT as possible (to minimize the number of wasted, expensive calls to rand()), without biasing the sample. Method: Find the biggest number of copies of 0 to range - 1 that will fit in 0 to MAXINT; this will cover some, perhaps equal, interval 0 to limit. If the call to rand() falls in 0 to limit, take the modulus with range as the returned value. If not, throw away the result and try again. Discussion: It is desired that the value returned fall in the interval 0 to range - 1. What you want to know is how many copies of range will fit in the interval 0 to MAXINT, or, more important, 1 to MAXINT + 1, so we can divide to get the answer. This gets messy because you can't represent MAXINT + 1 directly, and range might be an exact divisor of MAXINT + 1. */ work1 = MAXINT/range; /* integer number of ranges that fit in MAXINT */ /* in case what was left, + 1, will hold one more copy of range */ work2 = (MAXINT - (work1 * range) + 1) / range ; /* the "-1" has to go here to avoid overflow in the next calculation */ /* in case range is an exact divisor of MAXINT + 1 */ limit = range * work1 - 1; /* add in zero or one more range interval */ limit = limit + range * work2; /* limit is now the biggest usable return value from rand() */ while ((work3 = rand()) > limit) /* iterate*/ ; return (work3 % range); } If only one value of range is being used, or if the programmer is willing to do the work in the calling routine for each different value, the calculation of limit should be moved out to the calling routine and the calculated value passed in for efficiency. You still have to do the seed call to srand() once somewhere, preferably near the top of your main routine. If that constitutes code (doubtful) then it is public domain. The idea is yours in any case, it sure isn't original with me. Forgive bugs, I haven't been well enough to light off a compiler since June. Modulo possible bugs, that is the "standard" way to do the job right. Kent, the man from xanth.