martens@python.cis.ohio-state.edu (Jeff Martens) (12/03/90)
In article <37886@nigel.ee.udel.edu> AAW151%URIACC.BITNET@brownvm.brown.edu (Andy Patrizio) writes: >In going through ANSI C, one of umpteen books on C programming, reference is >made to a command called rand() that will generate random numbers. >First off, is this possible under Lattice C? And second, how exactly is it >done? The book doesn't elaborate. Lattice C, except for the possibility of running out of memory, is turing complete. So you can certainly do it in Lattice C. Most programming languages come with random number generators as part of the language or in a library, but many are garbage (e.g. unix rand() or the random # function that TDI distributed with their Modula 2). If you need a good random number generator, you might want to read this article: @article{ParMil:88, author = {Stephen K. Park and Keith W. Miller}, title = {Random Number Generators: Good Ones are Hard to Find}, journal = {CACM}, year = {1988}, month = {October}, volume = {31}, number = {10}, pages = {1192 -- 1201} } Of course, if you're just writing a game it doesn't probably matter. Please note that I've redirected followups to c.s.a.tech. -- -- Jeff (martens@cis.ohio-state.edu) "Until you stalk and overrun, you can't devour anyone" -- Hobbes.
737104@sheoak.bcae.oz (David Thiele) (12/04/90)
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!),
Random(range,seed)
int range,seed;
{
srand(seed);
if range = 0
return(0);
else{
do
seed = rand() / 10000000;
while (seed >= range);
return(seed);
}
}
urrgghh! help
Davedolf@idca.tds.PHILIPS.nl (Dolf Grunbauer) (12/05/90)
In article <666@sheoak.bcae.oz> 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!), > >Random(range,seed) >int range,seed; >{ > srand(seed); > if range = 0 > return(0); > else{ > do > seed = rand() / 10000000; > while (seed >= range); > return(seed); > } >} > How about: Random(range,seed) int range,seed; { srand(seed); if range = 0 return(0); else return (((seed = rand()) / 10000000) % range); } By the way: why do you want to set seed explicitly before each rand call ? Propably 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. -- _ _ / U | Dolf Grunbauer Tel: +31 55 433233 Internet dolf@idca.tds.philips.nl /__'< Philips Information Systems UUCP ...!mcsun!philapd!dolf 88 |_\ If you are granted one wish do you know what to wish for right now ?
hclausen@adspdk.UUCP (Henrik Clausen) (12/06/90)
In article <666@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!). You said it :-) Try something like: int Random(int Range) { return((int)(Range * drand48())); } Add offsets at your desire. Seed from the timer with srand48(). drand48() returns a double, and is supposed to be quite good. BTW, this stuff is in your manual. -Henrik | Henrik Clausen, Graffiti Data | If the Doors of Perception where cleansed, | | ...{pyramid|rutgers}!cbmvax! | Man would see Reality as it is - Infinite. | \______cbmehq!adspdk!hclausen___|_________________________________W. Blake___/
aaronf@hpfcbig.SDE.HP.COM (Aaron Friesen) (12/06/90)
sheoak.bcae.oz (David Thiele) / 4:20 pm Dec 3, 1990 / > 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!), [ Code Deleted... ] Simply taking rand() % range or something similar should give you what you want. This will be fast and about as "random" as the code you are currently using.
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (12/06/90)
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>
nj@magnolia.Berkeley.EDU (Narciso Jaramillo) (12/07/90)
In article <1990Dec6.033145.22855@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: 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!), > return (rand() % range); 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. If you're willing to do some floating-point arithmetic, you can also do return ((int)floor((double)(rand())/MAXINT * high)); or return ((int)floor(drand48() * high)); Since rand() returns values that are (presumably evenly) distributed over the range [0, MAXINT), (double)(rand())/MAXINT should return floating point values that are evenly distributed over the range [0.0, 1.0). Since drand48() also returns values in [0.0, 1.0), both of these should return unbiased values in the range [0, high). Slightly expensive because of the floating-point operations, but you don't have to go through the (admittedly fast, though not necessarily faster) contortions of Kent's algorithm. nj
barrett@jhunix.HCF.JHU.EDU (Dan Barrett) (12/08/90)
I tried e-mail but it bounced. In article <666@sheoak.bcae.oz> 737104@sheoak.bcae.oz (David Thiele) writes: >Is there a way to generate random numbers within a certain range in >Lattice C?? It can be done in ANY language -- there is a mathematical formula for it. All you need is a function Rand() that returns a random real number between 0 and 1 (not including 1). This is commonly supplied by your compiler company. To generate a random integer between integers A and B, with A < B: (1) Figure out the distance between A and B: distance = B - A + 1; (2) Multiply a random number by the distance, and truncate the remainder. This gives you a random integer between 0 and (distance - 1): first = floor(distance * Rand()); (3) Now increase this number by A, to give you an integer between A and (A + distance - 1). But remember: A + distance - 1 = A + (B - A + 1) - 1 = B So you have a random integer between A and B: answer = first + A; Here is the final formula: answer = floor((B - A + 1) * Rand()) + A; Dan //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ | Dan Barrett - Systems Administrator, Computer Science Department | | The Johns Hopkins University, 34th and Charles Sts., Baltimore, MD 21218 | | INTERNET: barrett@cs.jhu.edu | | | COMPUSERVE: >internet:barrett@cs.jhu.edu | UUCP: barrett@jhunix.UUCP | \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/////////////////////////////////////
andrew@teslab.lab.OZ (Andrew Phillips) (12/11/90)
In article <540@ssp9.idca.tds.philips.nl> dolf@idca.tds.philips.nl (Dolf Grunbauer) writes: >In article <666@sheoak.bcae.oz> 737104@sheoak.bcae.oz (David Thiele) writes: >>Is there a way to generate random numbers within a certain range in >>Lattice C??. ... > >... >Random(range) >int range; >{ > if range = 0 > return(0); > else return (rand() % range); >} This is not the best solution for two reasons. First, unless range is a divisor of the maximum value returned by rand() plus one then the numbers will not be distributed evenly over the range. Second, even the best PRNG's are not very random in their least significant bits, so you want values which use the most significant bits. A simple portable solution would be to use drand48(): #define RANDOM(RANGE) ((int)(drand48()*(RANGE))) If you don't want to use floating point numbers or need more speed and know that longs are bigger than ints you could use (assuming rand() returns a value between zero and MAXINT): #define RANDOM(RANGE) ((int)(((long)rand()*(RANGE))/(MAXINT+1))) Or else if you know range is never going to be bigger than say 256 use something like: #define RANDOM(RANGE) (((rand()/256)*(RANGE))/((MAXINT+1)/256)) Andrew. -- Andrew Phillips (andrew@teslab.lab.oz.au) Phone +61 (Aust) 2 (Sydney) 289 8712
lshaw@ccwf.cc.utexas.edu (logan shaw) (12/13/90)
In article <666@sheoak.bcae.oz> 737104@sheoak.bcae.oz (David Thiele) writes: >Is there a way to generate random numbers within a certain range in >Lattice C??. ... Well, assuming you are already writing an amiga specific application and this won't hurt portability, you could use the amiga.lib function rangerand(). You pass it a longword (with a value from 1 to 65535) and it returns a random number between 0 and that number. If you are being portable, use a macro. Hope that helps... -- =----------------Logan-Shaw---(lshaw@ccwf.cc.utexas.edu)----------------= "Trust in the Lord with all thine heart, and lean not on thine own understanding. In all thy ways acknowledge Him and he shall direct thy paths" - Proverbs 3:5-6
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (12/13/90)
andrew@teslab.lab.oz.au (Andrew Phillips) writes: >If you don't want to use floating point numbers or need more speed >and know that longs are bigger than ints you could use (assuming >rand() returns a value between zero and MAXINT): >#define RANDOM(RANGE) ((int)(((long)rand()*(RANGE))/(MAXINT+1))) ^^^^^^^^probably not >Or else if you know range is never going to be bigger than say 256 use >something like: >#define RANDOM(RANGE) (((rand()/256)*(RANGE))/((MAXINT+1)/256)) ^^^^^^^^nope Your first example will overflow to MAXNEGINT if the compiler chooses to do the promotion to long as late as possible, and your second one is guaranteed to overflow. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>