Developer Reference

Contents

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.
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
b
0
,
b
1
,
b
2
, ... from the integer output of the BRNG and then forms 20-bit overlapping words
w
0
=
b
0
b
1
...
b
19
,
w
1
=
b
1
b
2
...
b
20
, ... 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
p
j
,
j
= 1, 2, ..., 20. The test applies the Kolmogorov-Smirnov goodness-of-fit test with Anderson-Darling statistics to the obtained set of
p
j
,
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
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.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.