🚀 go-pugleaf

In article <1993Jan20.203516.18565@prime.mdata.fi> paetau@mits.mdata.fi (Rasmus Paetau) writes:
>Does anybody know how to generate random numbers on a computer? I know
>of the GEMDOS/BIOS/XBIOS call that does that, but I wonder if it could
>be done faster?

The XBIOS call uses the "linear congruential" method of generating pseudo-
random numbers, which works as follows:

R(n+1) := [R(n) * a] mod b

(Where R(n) is the n'th random number, R(n+1) the n+1'th number, etc)

The idea is to choose values of a and b such that long sequences of
non-repeating pseudo-random numbers are obtained. From a computational
viewpoint, it makes sense to make b a power of 2 since the modulo function
then reduces to a simple AND instruction. There are also rules for choosing
good values for a.

The XBIOS call is pretty quick -- it's an assembler implementation of the
above, and you're not going to write one that's much quicker! The thing that
takes the time (on a 68000 at least) is the multiplication. There are other
methods that use shift-then-XOR (see the book references below).

I remember (it's a long time since I disassembled the code) that when the
XBIOS routine is first called, the generator is seeded with a new number --
but I forget where that number comes from.

>I'm supposed to do a program that has to do with
>probability and such things, and I'd like a fast and flexible random
>routine in assembler.. so if anybody has ideas, they're welcome!

If you want *truly* random numbers (as opposed to pseudo-random numbers),
then you're going to have to build some hardware. Commercial random number
hardware works by amplifying the quantum noise in a resistor and
thresholding it to generate a stream of random bits.

There is quite a lot of literature about random number generation. You might
look at the "Numerical Recipes" book by Press, Flannery et al. (but it has
some mistakes in the section on random numbers). Any good numerical
algorithms book should cover random numbers -- Sedgewick's "Algorithms" has
a small section on it (and it covers the shift-XOR method).

>| Rasmus Paetau (paetau@mits.mdata.fi) | I still believe in Falcon030 |

Mat

| Mathew Lodge                      | "What think you, my lord, of... Love?" |
| mjl-b@minster.york.ac.uk          | "You mean rumpy-pumpy?"                |
| Langwith College, Uni of York, UK |  -- Blackadder II                      |