A83: Re: Random numbers

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

A83: Re: Random numbers


>
> 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
References: