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.
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
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
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
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

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804