[Openmcl-devel] improvements to CL:RANDOM

[R. Matthew Emerson]

I've just committed changes to the trunk that replace the old random number generator with a new one of much higher quality.  (We'll just have to wait and see about the quality of my implementation of this new generator.)  Raw performance of the new generator appears to be comparable to that of the old, despite the fact that the new generator does a lot more work.

When you rebuild the lisp, you'll see some warnings;  these may be ignored.

Please report any bugs (performance, correctness, what-have-you) you find.

Clozure CL's old random number generator is a classic linear congruential generator.  LCGs obey the recurrence x_i = (ax_{i-1} + c) mod m.  If we use LCG(m, a, c) to denote a LCGs, then Clozure CL's was LCG(2^32 - 1, 48271, 0).  The nice thing about this generator is that it is can be implemented very efficiently.  The bad things are that it has a very short period, and it does very poorly on empirical tests [1].  (So, other than that, how did you like the play, Mrs. Lincoln?)

There are many high-quality random number generators to choose from.  Reference [1] contains a fairly large list.  I selected the mrg31k3p generator described in [2].  This generator has a period of about 2^185, and does well on all the TestU01 tests.

Another candidate was L'Ecuyer's widely-used mrg32k3a generator.  This is used in SRFI 27 [3].  I actually implemented it, but I decided to use mrg31k3p instead.  The mrg32k3a generator is implemented with double precision floating point arithmetic, and it ended up being simpler to stick to integer arithmetic.

The Mersenne twister generator is, of course, very famous and widely used.  I didn't pick it mainly because it keeps some 600-odd words of state, which I find cumbersome, and also because I find the implementation of the multiple recursive generators to be a little more straightforward.

At some point sooner or later, it will make sense to implement a generator designed for 64-bit processors.  The mrg31k3p generator produces values in the interval [0, 2^31 - 1), so we have to call the generator multiple times to get longer sequences of random bits.

[1] P. L'Ecuyer and R. Simard, "TestU01: A C Library for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.  http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf

[2] P. L'Ecuyer and R. Touzin, ``Fast Combined Multiple Recursive Generators with Multipliers of the form a = +/- 2^d +/- 2^e'', Proceedings of the 2000 Winter Simulation Conference, Dec. 2000, 683--689.  http://www.informs-sim.org/wsc00papers/090.PDF

[3] http://srfi.schemers.org/srfi-27/