[A83] Re: Random numbers

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

[A83] Re: Random numbers


> What is the best random number generator routine , in terms of
> effectiveness and speed ?

I used the following routine in Zelda 86:

; a fast, yet decent random number generator
; returns: a = psuedo random number
; destroyed: flags
RandomNumber:
 push bc
 ld a,r
 ld b,a
 ld a,($1234)
_@RandomNumberSeed =$-2
 ld c,a
 ld a,(bc)
 ld (_@RandomNumberSeed),a
 xor b
 sub b
 add a,c
 pop bc
 ret

It takes 83 t-states, 93 with ret.  Not going to get this much faster and
still be "random".  Note that I wrote this routine about two years ago, and
I wasn't going for anything truely random (which is of course impossible),
or even statistically correct, but merely something small/efficient to use
in a game.  It seems to work well enough.  I remember running some tests and
watching what numbers it printed out.  Essentially what it does is keeps a
seed number, does some "random operations that seem to work well" on the
seed, the memory refresh counter and a "random" byte from the ROM determined
by the tom foolery, and returns the value.

Something that I didn't think about then is that although it seems to
provide a good range of numbers that seem fairly random, the entropy is not
very good, and it might not be good for generating small numbers.
Generating a value that is 7-8 bits is very different from a value with 2
bits.  Just masking off the high bits won't necessarily do it for you.

Donald Knuth's The Art of Computer Programming describes the method most
used for seed based random number generators, such as srand() / rand() in
the Standard C library.  The method is the linear congruential method, and
uses the following formula:

Xi+1 = (A*Xi + C) mod M

A is the multiplier, C is the increment, and M is the modulus.  Three rules
are stated for these values:

A-1 must be a multiple of every prime factor of M

A-1 and M must have the same divisibility by 4

C and M must be relatively prime

The book does have proofs of these rules, but as much of the stuff in his
books, and with most math things, you really don't need to know, just know
that it works, and that fortunately you don't have to prove it yourself.  At
least, that's my standpoint on these sorts of things.

In the formula, X is the seed.  So each time a random number is generated,
that random number also becomes the next seed:

random = (A*seed + C) % M
seed = random

It is very important to choose good values for A, C and M.
References: