How Computers Generate Random Numbers - Chapter 7

Chapter 6                     Chapter 8
index
Back to Deley's Homepage



7.0    SHUFFLING

 A simple way to greatly improve any random number generator is to shuffle the output. Start with an array of dimension around 100. (The exact size of array is not important.) This is the array that will be used to shuffle the output from the random number generator. Initialize the array by filling it with random numbers from your random number generator. Then when the program wants a random number, randomly choose one from the array and output it to the program. Then replace the number chosen in the array with a new random number from the random number generator.

Note that this shuffling method uses two numbers from the random number generator for each random number output to the calling program. The first random number is used to pick an element from the array of random numbers, and the second random number is used to replace the number chosen.

The improvement in randomness is quite dramatic. We tried this shuffling technique with the ANSI C random number generator. The results are given below first without shuffling and then with shuffling using an array size of 128 (a convenient power of 2):

ANSI C rand()

WITHOUT SHUFFLING:    WITH SHUFFLING:
1-D Fails above 500,000 bpdFails above 400,000 bpd
2-D Fails above 600 bpdFails above 3100 bpd
3-D Fails above 80 bpdFails above 210 bpd
4-D Fails above 21 bpdFails above 55 bpd
5-D Fails above 15 bpdFails above 24 bpd
6-D Fails above 8 bpdFails above 14 bpd
7-D Fails above 7 bpdFails above 9 bpd
8-D Fails above 5 bpdFails above 7 bpd

Notice the dramatic improvement in performance when shuffling is used. This shuffling technique works so well it may even fix up the defective RANDU generator to the point where it is acceptable. (Only a lack of time prevented this test from being performed.) This shuffling technique is highly recommended for anyone who is even remotely concerned about the quality of their random number generator.

Shuffling also takes care of the problem of points lying "mainly in the planes" as was discussed earlier. Points plotted on a unit square appear random rather than lying on parallel lines, and points plotted on a unit cube appear random rather than lying on parallel planes. In general points plotted on a unit n-dimensional hypercube no longer all lie on parallel (n-1) dimensional hypercubes.

This shuffling technique is highly recommended.




Chapter 6                     Chapter 8
index
Back to Deley's Homepage