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

Random number generator

    Date: Mon, 14 Jan 1991 08:22 EST
    From: lawton@RA.radc.af.mil (James Lawton)

    Has anyone done any testing of the random number generator included in
    Genera?  By tests I refer to such statistics as chi-square and the

    James Lawton
    Rome Laboratory
    Griffiss AFB, NY   13441-5700

The Symbolics random number generator is identical to the
"rotating table" described by Knuth in v. 2. of "The Art of Computer
Programming", with a table size of 71, a write-read separation of 35,
and a write-read advance of 1, with arithmetic performed modulo 2^32.
The algorithm has been subjected to intense analysis on a variety of
platforms, although (to my knowledge) Symbolics has not duplicated the
tests.  It is, therefore, remotely possible that the algorithm is
implemented incorrectly.  However, I have just read the code and it
seems quite straightforward.  The algorithm is simple and it would
require real creativity to get it wrong.

When the write-read separation and advance are relatively prime to the
table size, the algorithm passes all the tests I have ever heard of.
Ours has 2272 bits of state (really 13972.2+ bits if you include the
positions of the pointers as part of the state) and presumably will not
cycle within the lifetime of the universe at one sample per picosecond.