George Marsaglia's post to Sci.Stat.Math on 1/12/99. ********************************* This posting ends with 17 lines of C code that provide eight different in-line random number generators, six for random 32-bit integers and two for uniform reals in (0,1) and (-1,1). Comments are interspersed with that code. Various combinations of the six in-line integer generators may put in C expressions to provide a wide variety of very fast, long period, well-tested RNG's. I invite comments, feedback, verifications and timings. First, there is narrative giving background for this posting; you may want to skip it. Narrative: Having had experience in producing and testing for randomness in computers, I am frequently asked to suggest good random number generators (RNG's), test RNG's, or comment on existing RNG's. Many recent queries have been in two areas: (1) requests for implementations in C and (2) comments on generators with immense periods, particularly the Mersenne Twister. This posting is mainly for category (1), for which I suggest a set of C implementations of RNG's I have developed. C implementations of my DIEHARD battery of tests will be discussed elsewhere, and Narasimhan's GUI version is expected to be released soon. For (2), I merely repeat what I have said in response to various queries: the Mersenne Twister looks good, but it seems to be essentially a lagged Fibonacci RNG using the exclusive-or (xor) operation, and experience has shown that lagged Fibonacci generators using xor provide unsatisfactory 'randomness' unless the lags are very long, and even for those with very long lags, (and even for those using + or - rather than xor), many people (I among them) are inclined to be cautious about sequences based on such a simple operation as: each new integer is the xor, (or sum, or difference), of two earlier ones. To be sure, the resulting integers can be "twisted", but not, I think, as simply or as safely as combining, say by addition, with members of a sequence from a (shorter period) generator that has itself passed extensive tests of randomness. I also reply that it does not take an immense program (as, for example, in posted listings of Twister) to produce a more satisfactory RNG with an immense period, and give this example, on which I will expand below: Inclusion of #define SWB ( t[c+237]=(x=t[c+15])-(y=t[++c]+(x>16))<<16) #define wnew ((w=18000*(w&65535)+(w>>16))&65535) #define MWC (znew+wnew) #define SHR3 (jsr=(jsr=(jsr=jsr^(jsr<<17))^(jsr>>13))^(jsr<<5)) #define CONG (jcong=69069*jcong+1234567) #define KISS ((MWC^CONG)+SHR3) #define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[++c+178]) #define SWB (t[c+237]=(x=t[c+15])-(y=t[++c]+(x>24); will provide a random byte, while v=4.+3.*UNI; will provide a uniform v in the interval 4. to 7. For the super cautious, (KISS+SWB) in an expression would provide a random 32-bit integer from a sequence with period > 27700, and would only add some 300 nanoseconds to the computing time for that expression. */ /* The KISS generator, (Keep It Simple Stupid), is designed to combine the two multiply-with-carry generators in MWC with the 3-shift register SHR3 and the congruential generator CONG, using addition and exclusive-or. Period about 2123. It is one of my favorite generators. */ /* The MWC generator concatenates two 16-bit multiply-with-carry generators, x(n)=36969x(n-1)+carry, y(n)=18000y(n-1)+carry mod 216, has period about 260 and seems to pass all tests of randomness. A favorite stand-alone generator---faster than KISS, which contains it.*/ /* SHR3 is a 3-shift-register generator with period 232-1. It uses y(n)=y(n-1)(I+L17)(I+R13)(I+L5), with the y's viewed as binary vectors, L the 32x32 binary matrix that shifts a vector left 1, and R its transpose. SHR3 seems to pass all except the binary rank test, since 32 successive values, as binary vectors, must be linearly independent, while 32 successive truly random 32-bit integers, viewed as binary vectors, will be linearly independent only about 29% of the time. */ /* CONG is a congruential generator with the widely used 69069 as multiplier: x(n)=69069x(n-1)+1234567. It has period 232. The leading half of its 32 bits seem to pass all tests, but bits in the last half are too regular. */ /* LFIB4 is an extension of the class that I have previously defined as lagged Fibonacci generators: x(n)=x(n-r) op x(n-s), with the x's in a finite set over which there is a binary operation op, such as +,- on integers mod 232, * on odd such integers, exclusive-or (xor) on binary vectors. Except for those using multiplication, lagged Fibonacci generators fail various tests of randomness, unless the lags are very long. To see if more than two lags would serve to overcome the problems of 2- lag generators using +,- or xor, I have developed the 4-lag generator LFIB4: x(n)=x(n-256)+x(n-179)+x(n-119)+x(n-55) mod 232. Its period is 231*(2256-1), about 2287, and it seems to pass all tests---in particular, those of the kind for which 2-lag generators using +,-,xor seem to fail. For even more confidence in its suitability, LFIB4 can be combined with KISS, with a resulting period of about 2410: just use (KISS+LFIB4) in any C expression. */ /* SWB is a subtract-with-borrow generator that I developed to give a simple method for producing extremely long periods: x(n)=x(n-222)-x(n-237)-borrow mod 232. The 'borrow' is 0 unless set to 1 if computing x(n-1) caused overflow in 32-bit integer arithmetic. This generator has a very long period, 27098(2480-1), about 27578. It seems to pass all tests of randomness, but, suspicious of a generator so simple and fast (62 nanosecs at 300MHz), I would suggest combining SWB with KISS, MWC, SHR3, or CONG. */ /* Finally, because many simulations call for uniform random variables in 0