Birthday Spacing Test
Test Purpose
The test uses simulation to evaluate the randomness of groups of 24 sequential bits of the integer output of a BRNG. The test analyzes all possible groups of the kind, that is, for example, from 0 to 23 bit, from 1 to 24 bit, and so on.
First Level Test
The first level test selects at random
m
= 210 ”birthdays” from a ”year” of n
= 224 days. Then the test computes the spacing between the birthdays for each pair of sequential birthdays. The test then uses the spacings to determine the K
value, that is, the number of pairs of sequential birthdays with the spacing of more than one day. In this case K
should have the distribution close to the Poisson distribution with the l
= 16 parameter. The first level test determines 200 values of K
j
(j
= 1, 2, ..., 200). To obtain the p-value p
, the test applies the chi-square goodness-of-fit test to the determined values.The integer output lists different interpretations for each BRNG. In the table below, NB stands for the number of bits required to represent a random number in integer arithmetic, WS stands for the machine word size, in bits, used in integer random number generation.
BRNG | Integer Output Interpretation |
---|---|
MCG31m1 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-30. NB=31, WS=32. |
R250 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
MRG32k3a | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
MCG59 | Array of 64-bit integers. Each 64-bit integer uses the following bits: 0-58. NB=59, WS=64. |
WH | Array of quadruples of 32-bit integers. Each 32-bit integer uses the following bits: 0-23. NB=24, WS=32. |
MT19937 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
MT2203 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
SFMT19937 | Array of quadruples of 32-bit integers. Each 32-bit integer uses the following bits: 0-32. NB=32, WS=32. |
PHILOX4X32X10 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
ARS5 | Array of 32-bit integers. Each 32-bit integer uses the following bits: 0-31. NB=32, WS=32. |
The test generates the dates of the birthdays in the following way:
- Selects thebs,bs+1, ...,bs+23bits from the next WS-bit integer of the integer output ofviRngUniformBits.
- Treats the selected bits as a 24-bit integer, that is, the number of the date on which the next birthday takes place and thus generates a birthday.
- The test performs the steps 1 and 2mtimes to generatembirthdays taken that the year consists ofndays. The legitimate valuessare different for each base generator (see the table above): 0 £s£ NB - 24.
Second Level Test
The second level test performs the first level test ten times for the fixed
s
. The test applies the Kolmogorov-Smirnov goodness-of-fit test with Anderson-Darling statistics to the obtained set of pj
(j
= 1, 2 , ..., 10). If the resulting p-value is p
< 0.05 or p
> 0.95, the test fails for the given s
.Final Result Interpretation
The second level test performs ten times for each 0 £
s
£ NB - 24. The test computes the FAILs percentage for the failed second level tests. The final result is the minimal percentage of the failed tests FAIL = min(FAIL0
, FAIL1
, ..., FAILNB-24
) for 0 £ s
£ NB - 24. The applicable result is the value of FAIL < 50%. Thus, the test determines if it is possible to select 24 random bits from every element of the integer output of the generator.- The integer output for the WH generator is the quadruples of the 32-bits values (xi,yi,zi,wi). In each 32-bit value only the lower 24 bits are significant.
- The second level test performs ten times for thexielement. Then the test computes the FAILxpercentage the failed second level tests.
- The second level test performs ten times for theyi. Then the test computes the FAILypercentage for the failed second level tests.
- The test performs the same procedure to compute the FAILzand FAILwvalues.
The final result is the minimal percentage of the failed tests FAIL = min(FAIL
x
, FAILy
, FAILz
, FAILw
). The acceptable result is the value of FAIL < 50%.The test determines if it is possible to select 24 random bits from the fixed element
x, y, z
or w
for each element of the integer output of the generator.Tested Generators
Function Name | Application |
---|---|
vsRngUniform | not applicable |
vdRngUniform | not applicable |
viRngUniform | not applicable |
viRngUniformBits | applicable |