Re: A83: Re: Random numbers


[Prev][Next][Index][Thread]

Re: A83: Re: Random numbers




And if you want something simpler, check out the zlib random routine for SOS. 
 It's pretty fast too.
Brandon Sterner

In a message dated 7/6/99 9:05:12 AM Eastern Daylight Time, 
cameron.m@iname.com writes:

<< >
 > I'm writing a game and I need a routine which returns random numbers.
 > I tried out some but they didn't work right - the numbers exceeded the
 > given maximum. Maybe someone could post a good random routine.
 >
 > Girts.
 >
 
 Hi Girts.
 
 A common method of finding random numbers in by using what's known as a
 congruential pseduorandom number generator.  Basically, this is a formula of
 the form:
 
   x(i) = [ax(i - 1) + c] mod m
 
 where x(i) is the random number you are generating, x(i -1) was the previous
 random number generated, and a, c & m are integer constants.
 
 You let m be the maximum random number you want generated minus 1.  So, if
 you wanted a random number from 0 - 99, you'd have
 
   x(i) = [ax(i - 1) + c] mod 100
 
 However, not just any values for a and c are going to work to make the
 formula generate every single positive integer below m.  The conditions
 required are:
 
   - gcd(c, m) = 1
   - each prime that divides m also divides a - 1 (this implies that gcd(a,
 m) = 1 also)
   - 4 divides a - 1 if 4 divides m.
 
 An example:
 
 ---
 Using the formula,
 
   x(i) = 4253261 x(i - 1) + 372837 mod 2^24
 
 we can generate each number from 0 to 16777215 in a seemingly random order.
 This'll work because the preconditions are satisfied:
 
   - gcd(372837, 2^24) = 1 (this is fairly obvious, since the only prime
 factor of 2^24 is 2, and here, c is odd)
   - only one prime divides 2^24, and that's 2.  This does divide 372866.
   - 4 divides 16777216, and also divides 372836.
 
 Apparently this particular formala was used in some versions of BASIC.
 ---
 
 When you are finding the first "random" number, you let the value of x(i -
 1) be any number below m.  This is the seed.  You'd probably be best getting
 this one by incrementing a register while in a 'keypress at the titlescreen'
 type of loop.
 
 Because of the use of mod, if you were to limit the random numbers to say,
 150, then the random number generator would be a bit slow, since you'd have
 to use some of the FP routines to do the mod.  However, if you use a value
 for m which is a power of 2, you can simple AND off the appropriate bits.
 In fact, if you were to use 65536 for m, you can use the fact that the
 numbers in 16-bit registers are going to be mod 65536 anyway.  However,
 you're still going to have to use the FP routine to do the multiplication,
 unless you can be bothered writing a proper 16-bit multiplication routine.
 
 Then again, if you only needed smaller numbers, you could have m = 256, in
 which case you could use _HTIMESL for the multiplication, which'd be a bit
 quicker than the FP equivalent.
 
 Anyway, I'm sure you can write your own routine from the information
 presented here.  If you can't, then I'll do one if I have to. :)
 
 Discrete maths rules,
 
 Cameron >>