Bitstream Test

Test Purpose

The test uses simulation to check if it is possible to interpret the integer output of a BRNG as a sequence of random bits.

Note

The bit precision of a BRNG defines the sequence of random bits formation. For example, only 59 lower bits take part in the bit stream formation for the MCG59 generator, and only 31 lower bits for the MCG31 generator.

First Level Test

The first level test initially forms the sequence of bits b0, b1, b2, ... from the integer output of the BRNG and then forms 20-bit overlapping words w0= b0b1... b19 , w1 = b1b2... b20, ... from the sequence. From the total number of 2021 formed words the test computes the quantity K of the missed 20-bit words. For the truly random sequence the K statistic distribution should be very close to normal with mean a = 141,909 and standard deviation s = 428. The test denotes the cumulative function of the normal distribution with these parameters as F(x). The result is that the distribution of the p-value p = F(K) should be uniform within the interval of (0, 1). 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-31. 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 selects:

  1. NB of lower bits from each WS-bit integer to form a bit sequence

  2. NB of lower bits from each of four WS-bit elements for WH generator

Second Level Test

The second level test performs the first level test 20 times. The result of each first level test is the p-value pj, j = 1, 2, ..., 20. The test applies the Kolmogorov-Smirnov goodness-of-fit test with Anderson-Darling statistics to the obtained set of pj, j = 1, 2, ..., 20. If the resulting p-value is p < 0.05 or p > 0.95, the test fails.

Final Result Interpretation

The final result of the test is the FAIL percentage of the failed second level tests. The second level test performs ten times. The acceptable result is the value of FAIL < 50%.

Tested Generators

Function Name

Application

vsRngUniform

not applicable

vdRngUniform

not applicable

viRngUniform

not applicable

viRngUniformBits

applicable

Function Name

Application

vsRngUniform

not applicable

vdRngUniform

not applicable

viRngUniform

not applicable

viRngUniformBits

applicable

The lower bits are not random for multiplicative congruential generators where the module is the power of two (for example, MCG59), thus, the Bitstream Test fails for such generators.

For more complete information about compiler optimizations, see our Optimization Notice.
Select sticky button color: 
Orange (only for download buttons)