Contents

# Count-the-1's Test (Stream of Bits)

## Test Purpose

The test evaluates the randomness of the overlapping random five-letter words sequence. The five-letter words have the specified distribution of the probabilities of obtaining the specified letter. The test forms the random letters from the integer output of a BRNG. The test treats the integer output as a sequence of bits.

## First Level Test

The first level test assumes that the integer output is a sequence of random bits. The test interprets this bit sequence as a sequence of bytes, that is, a sequence of 8-bit integer numbers. The number of 1’s in every random byte should have a binominal distribution with
m
= 8,
p
= 1/2 parameters. Therefore, the probability of getting
k
1’s in a byte is equal to 2
-8
C
8
k
. The first level test regards a random variable
c
that takes five possible values:
c
= 0, if the number of 1’s in a random byte is less than three,
c
= 1, if the number of 1’s in a random byte is three,
c
= 2, if the number of 1’s in a random byte is four,
c
= 3, if the number of 1’s in a random byte is five,
c
= 4, if the number of 1’s in a random byte is more than five.
The probability distribution of
c
is the following: The test interprets c as a selection of a random letter from the alphabet {
a, b, c, d, e
} with the probabilities
q
0
,
q
1
,
q
3
,
q
4
respectively. Thus, the sequence of random bytes
b
0
,
b
1
,
b
2
, ... corresponds with the defined sequence of random letters
l
0
,
l
1
,
l
2
, ... . The test forms overlapping words of length four:
v
1
=
l
1
l
2
l
3
l
4
,
v
2
=
l
2
l
3
l
4
l
5
, ... and length five:
w
1
=
l
1
l
2
l
3
l
4
l
5
,
w
2
=
l
2
l
3
l
4
l
5
l
6
, ... from this sequence. The test computes the frequencies of getting each of 625 of possible four-letter words and of 3,125 of possible five-letter words for 2,560,000 of the obtained words. According to these frequencies, the test makes the chi-square statistics V1 and V2 for the four- and five-letter words respectively. The test takes into account the covariance of the frequencies of the fallouts of four-letter and five-letter words and performs the chi-square test for the V2 - V1 statistic. The V2 -V1 statistic is asymptotically normal with a mean
a
= 2500 and standard deviation
s
= 70.71. The result of the first level test is the p-value.
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 only NB of lower bits from each WS-bit integer to form a bit sequence.

## Second Level Test

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

## Final Result Interpretation

The second level test performs ten times. The test computes the FAIL percentage of the failed second level tests. 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 WH and SFMT19937 generators use all the four elements to form a bit sequence.

#### Product and Performance Information

1

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