Diehard tests
Encyclopedia
The diehard tests are a battery of statistical tests for measuring the quality of a random number generator. They were developed by George Marsaglia
over several years and first published in 1995 on a CD-ROM
of random numbers.
These are the tests:
George Marsaglia
George Marsaglia was an American mathematician and computer scientist. He established the lattice structure of congruential random number generators in the paper "Random numbers fall mainly in the planes". This phenomenon is sometimes called the Marsaglia effect...
over several years and first published in 1995 on a CD-ROM
CD-ROM
A CD-ROM is a pre-pressed compact disc that contains data accessible to, but not writable by, a computer for data storage and music playback. The 1985 “Yellow Book” standard developed by Sony and Philips adapted the format to hold any form of binary data....
of random numbers.
These are the tests:
- Birthday spacings: Choose random points on a large interval. The spacings between the points should be asymptotically exponentially distributedExponential distributionIn probability theory and statistics, the exponential distribution is a family of continuous probability distributions. It describes the time between events in a Poisson process, i.e...
. The name is based on the birthday paradoxBirthday paradoxIn probability theory, the birthday problem or birthday paradox pertains to the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 366. However, 99%...
.
- Overlapping permutations: Analyze sequences of five consecutive random numbers. The 120 possible orderings should occur with statistically equal probability.
- Ranks of matrices: Select some number of bits from some number of random numbers to form a matrix over {0,1}, then determine the rankRank (linear algebra)The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
of the matrix. Count the ranks.
- Monkey testMonkey testIn computer science, a Monkey test is a unit test that runs with no specific test in mind. The monkey in this case is the producer of any input. For example, a monkey test can enter random strings into text boxes to ensure handling of all possible user input or provide garbage files to check for...
s: Treat sequences of some number of bits as "words". Count the overlapping words in a stream. The number of "words" that don't appear should follow a known distribution. The name is based on the infinite monkey theoremInfinite monkey theoremThe infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare....
.
- Count the 1s: Count the 1 bits in each of either successive or chosen bytes. Convert the counts to "letters", and count the occurrences of five-letter "words".
- Parking lot test: Randomly place unit circles in a 100 x 100 square. If the circle overlaps an existing one, try again. After 12,000 tries, the number of successfully "parked" circles should follow a certain normal distribution.
- Minimum distance test: Randomly place 8,000 points in a 10,000 x 10,000 square, then find the minimum distance between the pairs. The square of this distance should be exponentially distributedExponential distributionIn probability theory and statistics, the exponential distribution is a family of continuous probability distributions. It describes the time between events in a Poisson process, i.e...
with a certain mean.
- Random spheres test: Randomly choose 4,000 points in a cube of edge 1,000. Center a sphere on each point, whose radius is the minimum distance to another point. The smallest sphere's volume should be exponentially distributed with a certain mean.
- The squeeze test: Multiply 231 by random floats on
[0,1) until you reach 1. Repeat this 100,000 times. The number of floats needed to reach 1 should follow a certain distribution.
- Overlapping sums test: Generate a long sequence of random floats on
[0,1) . Add sequences of 100 consecutive floats. The sums should be normally distributed with characteristic mean and sigma.
- Runs test: Generate a long sequence of random floats on
[0,1) . Count ascending and descending runs. The counts should follow a certain distribution. - The craps test: Play 200,000 games of crapsCrapsCraps is a dice game in which players place wagers on the outcome of the roll, or a series of rolls, of a pair of dice. Players may wager money against each other or a bank...
, counting the wins and the number of throws per game. Each count should follow a certain distribution.