Re: random function

[Robert A. Cassels <cassels@cambridge.apple.com>]

>I am doing some large monte-carlo simulations, and need to
>know what I am getting from the Random function. Does
>MCL 2.0 follow the algorithm described in Steele CLtL2?
>Where can I see the source code for this function?
>Thanks!

The source code is in LAP (68000 assembler) so you may or may not want to
see it.  I'm not sure which part of the algorithm you're concerned about
(the part that generates random 16-bit integers or the part that gives you
something of the appropriate type and range) or for which type (integer or
float).

I'll attempt to summarize the algorithms, although I'm probably off in a
few details since I seldom read LAP.  Also, my summary will be in more
mathematical terms than the assembly language.  You may rest assured that
the actual algorithms are much more efficient than the description might
suggest.

The random state is a 32-bit integer, represented as 2 16-bit parts.

The part that generates random 16-bit integers appears (if I read the LAP
correctly) to be equivalent to:
  (setq state (mod (* state 16807) (- (expt 2 31) 1)))

The low-order 16 bits of the new state are used as the 16-bit random
integer.

For integers, some number (if you really need to know, I'll interpret some
more LAP) of 16-bit chunks are concatenated to make a larger integer.  The
result is the large integer modulo the integer argument to RANDOM.

For floats, it appears that 4 16-bit chunks are concatenated to make a
64-bit integer.  The result is the float argument times the random integer
divided by 2**64.


If I were doing serious simulations, I might want a larger random state and
a better algorithm for generating the 16-bit parts.  I'd probably use one
from Knuth.  The conversion to approriate type and range seems fine to me,
though.