🚀 go-pugleaf

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.
<xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>