How Computers Generate Random Numbers - Chapter 5

Chapter 4                   Chapter 6
index
Back to Deley's Homepage



5.0    RATINGS FOR VARIOUS GENERATORS

 Here are the results of testing the 5 random number generators introduced in section 4.1


5.1    REVIEW OF TESTS PERFORMED

 We'll review once more the tests which were performed on each generator.


5.1.1    THE 1-D TEST

 Note that all the random number generators examined here [except the C and C++ rand() function] generate "random" values between [0,1). See addendum [3] at the end of this paper on how to convert the C and C++ rand() function so it generates random values between [0,1)

The 1-D test is the frequency test. Imagine a number line stretching from 0 to 1. We will use our random number generator to plot random points on this line. First we divide the line into a number of segments or "bins". Below is an example of dividing the unit line into 4 segments or bins:


Technically bin 1 covers all values between [0, 0.25) not including 0.25 Bin 2 covers all values between [0.25, 0.50) not including 0.50 Bin 3 covers all values between [0.50, 0.75) not including 0.75 And bin 4 covers all values between [0.75, 1.0) not including 1.0

We then see how randomly the random number generator fills our bins. If the bins are filled too unevenly, the Chi-Square test will give a value that's too high indicating the points do not appear random. For example, if all the points landed in bin 1 and no points landed in any of the other bins, we would conclude that the generator did not appear to be random. On the other hand, if the bins are filled too evenly, the Chi-Square test will give a value that's too low, also indicating the points do not appear random. For example, if after plotting 1000 points each of the four bins had exactly the same number of points in them, we would conclude that the generator was not random enough. The values given for the 1-D test is the approximate number of bins above which the random number generator fails the Chi-Square test in one dimension.


5.1.2    THE 2-D TEST

 The 2-D test is the serial test. We can imagine a unit square stretching from (0,0) at one tip to (1,1) at the other tip. We will use the random number generator to plot points on this unit square. To plot a point we generate two random numbers and use them as the coordinates. But first we divide the unit square into a number of smaller squares or "bins", in a gridlike pattern. Below is an example of dividing up the unit square into a total of 16 bins with 4 bins on a side:


We then see how randomly the random number generator fills our bins, the same as in the 1-D test. The value given for the 2-D test is the approximate number of bins per side or bins per dimension (bpd) above which the random number generator fails the Chi-Square test in two dimensions.

If we were to look at the unit square after we had plotted a large number of points, we would notice that rather than appearing random, the points all lined up on parallel lines. All linear congruential random number generators have this flaw. We will have more to say about this in section 7 (The Spectral Test).


5.1.3    THE 3-D TEST

 The 3-D test is the logical extension of the 2-D test and the 1-D test. Imagine a unit cube stretching from (0,0,0) at one tip to (1,1,1) at the other tip. We will use our random number generator to plot points on this unit cube. To plot a point we generate three random numbers and use them as the coordinates. We divide the unit cube into a number of smaller cubes or "bins", and then see how randomly the random number generator fills our bins, the same as we do for the 2-D test and 1-D test. The value given for the 3-D test is the approximate number of bins per side above which the random number generator fails the Chi-Square test in three dimensions.

If we were to look at the unit cube after we had plotted a large number of points, we would notice that rather than appearing random, the points all lined up on parallel planes. All linear congruential random number generators have this flaw. The infamous RANDU generator has only 16 parallel planes covering the unit cube, hence it performs extremely poorly on the 3-D test. We will have more to say about this in section 7 (The Spectral Test).


5.1.4    THE 4-D TEST


The 4-D test and higher dimensional tests are again the logical extension of the 3-D test, 2-D test, and 1-D test. For an n-D or n-dimensional test, we imagine an n-dimensional hypercube, divided in a gridlike manner into smaller hypercubes or "bins". We plot points in this n-dimensional hypercube by generating n random numbers and using them as the coordinates of a point. We then perform a chi-square test to see how evenly or unevenly our bins get filled with points. The value given for any n-D test is the approximate number of bins per dimension (bpd) above which the random number generator failed the chi-square test. (The total number of bins in an N-dimensional hypercube would be the number of bins per dimension raised to the Nth power.)




5.2    TEST RESULTS

 Each generator was tested for dimensions 1 through 8. Here now are the results:




5.2.1    MTH$RANDOM

DEFINITION:

        SEED = (69069*SEED + 1) mod 2**32
X = SEED/2**32
Returns real in range [0,1)     {including 0, excluding 1}

Fails 1-D above 350,000 bpd   (bins per dimension)
Fails 2-D above 600 bpd
Fails 3-D above 100 bpd
Fails 4-D above 27 bpd
Fails 5-D above 15 bpd
Fails 6-D above 9 bpd
Fails 7-D above 7 bpd
Fails 8-D above 4 bpd

Comments:
This generator is also used by the VAX/VMS FORTRAN intrinsic function RAN, and by the VAX/VMS BASIC function RND.




5.2.2    RANDU

DEFINITION:

        SEED = (65539*SEED) mod 2**31
X = SEED/2**31
Returns real in range [0,1)     {including 0, excluding 1}

RATING:
Fails 1-D above 200,000 bpd   (bins per dimension)
Fails 2-D above 400 bpd
Fails 3-D above 3 b bpd
Fails 4-D above 6 bbpd
Fails 5-D above 6 bbpd
Fails 6-D above 4 bpd
Fails 7-D above 3 bpd
Fails 8-D above 3 bpd

Comments:
Note the extremely poor performance for dimensions 3 and above. This generator is obsolete.




5.2.3    VAX C ( rand() )

DEFINITION:

        SEED = (1103515245*SEED + 12345) mod 2**31
X = SEED
Returns real in range [0, 2**31)     {including 0, excluding 2**31}

RATING:
Fails 1-D above 500,000 bpd   (bins per dimension)
Fails 2-D above 600 bpd
Fails 3-D above 80 bpd
Fails 4-D above 21 bpd
Fails 5-D above 15 bpd
Fails 6-D above 8 bpd
Fails 7-D above 7 bpd
Fails 8-D above 5 bpd




5.2.4    Microsoft C v4.0 rand()

DEFINITION:

        SEED = (214013*SEED + 2531011) mod 2**31
X = int( SEED/2**16 )
Returns real in range [0, 2**15)     {including 0, excluding 2**15}

RATING:
Fails 1-D above 3000 bpd   (bins per dimension)
Fails 2-D above 700 bpd
Fails 3-D above 84 bpd
Fails 4-D above 16 bpd
Fails 5-D above 15 bpd
Fails 6-D above 7 bpd
Fails 7-D above 6 bpd
Fails 8-D above 4 bpd

Comments:
The poor performance for 1-d is partly due to truncating the lower 16 bits of SEED before returning X. X is returned as a 15 bit positive signed integer.




5.2.5    Turbo Pascal v6.0 (random)

DEFINITION:

        SEED = (134775813*SEED + 1) mod 2**32
X = int(SEED/2**16)
Returns real in range [0, 2**16)     {including 0, excluding 2**16}

RATING:
Fails 1-D above 6000 bpd   (bins per dimension)
Fails 2-D above 700 bpd
Fails 3-D above 87 bpd
Fails 4-D above 27 bpd
Fails 5-D above 13 bpd
Fails 6-D above 9 bpd
Fails 7-D above 7 bpd
Fails 8-D above 4 bpd

Comments:
The poor performance for 1-d is partly due to truncating the lower 16 bits of SEED before returning X. X is returned as a 16 bit unsigned integer.




5.3    WHY DID THEY ALL FAIL AT ~1-10 MILLION ITERATIONS?
Why did all the random number generators tested here fail at about 1-10 million balls, regardless of how many "bins per dimension" were being tested?

I think it is due to reaching the limit of the 32 bit computer these tests were done on. Random number generators typically produce a single precision floating point number between 0 and 1. A typical single precision floating point datum on a 32 bit computer uses a normalized 24-bit fraction. The precision is approximately 2**23 = 8,388,608 . So I think no random number generator on a 32 bit machine can do better than about 5 million iterations unless we avoid the conversion into and back out of a single precision floating point variable. It would be interesting to see if 64-bit random number generators on a 64-bit machine have improved performance as it seems they should.



Chapter 4                   Chapter 6
index
Back to Deley's Homepage