Chapter 4 | Chapter 6 | |||||

## index | ||||||

## Back to Deley's Homepage |

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.

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).

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).

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.)

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. |

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. |

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 |

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. |

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. |

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 |