From: CSBVAX::CSBVAX::MRGATE::"SMTP::CRVAX.SRI.COM::RELAY-INFO-VAX" 6-FEB-1989 17:00 To: MRGATE::"ARISIA::EVERHART" Subj: RE: Help on the rancom number generator Received: From KL.SRI.COM by CRVAX.SRI.COM with TCP; Mon, 6 FEB 89 13:00:32 PDT Received: from gold.bacs.indiana.edu by KL.SRI.COM with TCP; Mon, 6 Feb 89 12:51:29 PST Date: 6 Feb 89 15:39:00 EST From: "IVAX::IJAH400" Subject: RE: Help on the rancom number generator To: "info-vax" cc: <@relay.cs.net:cstajs%uk.ac.stafpol.cr83@nss.cs.ucl.uk> [] Andrew J. Sherwood writes: > Can anybody help me ? A research student has asked me whether the random > number generator on the VAX has been tested, who by, and whether there have > been any papers written on it. I assume it must have been tested but has > anybody got any information on it or could suggest a direction to look for it. I am only aware of two different pseudo-random number generators implemented on the VAX (by Digital). These are the MTH$RANDOM RTL routine, which is used by FORTRAN's RAN function, and the "rand" function in the VAXC runtime library. Rand is supposedly equivalent to the standard UNIX* rand function. Both of these generators are mixed linear congruential generators of the form: f(z) = (a*z + c) mod m where z is the integer "seed" and f(z) is the next seed in the sequence. For MTH$RANDOM, a = 69069, c = 1, and m = 2**32. For rand, a = 1103515245, c = 12345, and m = 2**31. The floating point number returned by MTH$RANDOM (in the range 0..1) is the same as the result you would get by taking the most significant 24 bits of f(z) and dividing it by 2**24. Rand returns an integer, so to get a uniform variate on 0..1 you have to divide the result by m. Unfortunately, about the best thing that can be said for either of these generators is that they are full period generators (period length = m). There is a definite non-random behavior associated with *all* full period mixed linear congruential generators with m = 2**b: the kth bit of z (where the least significant bit is bit 0) cycles with period 2**(k+1)! This alone is quite enough to render them unsuitable for some applications. I do not know whether either of them has been subjected to much testing otherwise. In a recent article in CACM (Park, Stephen K. and Miller, Keith W., "Random Number Generators: Good Ones are Hard to Find", Commun. ACM vol. 31, no. 10 (Oct. 1988)), the UNIX* "rand" is exhibited in a section titled "A Sampling of Inadequate Generators". Presumably MTH$RANDOM would fall into the same category as it suffers from the same problem rand does. The article describes a "minimal standard" generator and points to lots of references that will be of use for applications where even the minimal standard might be inadequate. As for the generators in the "inadequate" category (which presumably would include MTH$RANDOM as well as rand), the authors have this to say: "There is really no argument in support of *any* of the example generators cited in this section. Most of them are naive implementations of a deceptively simple idea. All should be discarded. Even the best of them, those which have a full period and are correctly implemented, are inferior to the minimal standard." The "minimal standard" described in the article uses a multiplier a = 16807 (7**5) and a prime modulus m = 2**31-1. The use of a prime modulus avoids the bit-cycling problem, and the multiplier has at least been subjected to some documented testing (see CACM article). A further requirement made by the authors on the multiplier was that an portable implementation could be done using 32-bit two's complement arithmetic avoiding overflow (i.e., a portable implementation in a high level language). This generator is a straight multiplicative generator (c = 0) with z in the range 1 to 2**31-2. The period is 2**31-2 if the initial seed is in the range 1 to 2**31-2 (note that zero is not an acceptable seed for a straight multiplicative generator since it generates zero again). The authors speculate that a = 48271 or a = 69621 may be better multipliers, but are sticking with a = 16807 pending further testing and user experience. So, in my humble opinion, I would listen to the mathematicians and use an implementation of the "minimal standard", if the statistical "goodness" of the numbers generated is at all important. The article gives a Pascal implementation that is portable over all 32-bit machines that use 32-bit two's complement arithmetic. An assembly language implementation for the VAX would be trivial to write. For users with (rare) requirements for which *any* linear congruential generator is inadequate, there are references to articles describing simple combined generators given in the CACM article. - James A. Harvey, IUPUI Computing Services (Indiana University) Internet: ijah400%ivax.decnet@gold.bacs.indiana.edu BITNET: ijah400@indyvax * UNIX is a registered trademark of Bell Laboratories. Disclaimer: The opinions offered here are my own and not those of my employer. I do not claim to be an expert on pseudo-random number generators, nor do I want to be, although I have an adequate background in math to understand the advice of those knowledgable on the subject. I have had better experience in the past following such advice rather than blinding using whatever happened to be available on the machine I was using, which usually wasn't that good, and too often, to quote Knuth, "really horrible".