nist_sp_800_22_tests.py 文件源码

def random_excursions_variant(generator, n_bits, misc=None):
    """Random Excursions Variant Test.

    Test purpose as described in [NIST10, section 2.15]:
    "The focus of this test is the total number of times that a particular state is visited (i.e.,
    occurs) in a cumulative sum random walk. The purpose of this test is to detect deviations from
    the expected number of visits to various states in the random walk. This test is actually a
    series of eighteen tests (and conclusions), one test and conclusion for each of the states:
    -9, -8, ..., -1 and +1, +2, ..., +9."
    """

    if n_bits < 10 ** 6:
        print("Warning: Sequence should be at least 10^6 bits long", file=stderr)

    s = [0] * n_bits
    for i in range(n_bits):
        x = 1 if generator.random_bit() else - 1
        s[i] = s[i - 1] + x
    s.append(0)  # leading zero not needed for our implementation

    ksi = [0] * 18
    j = 0
    for x in s:
        if x == 0:
            j += 1
        elif -9 <= x <= 9:
            ksi[x + 9 - (x > 0)] += 1

    if j < 500:
        print("Warning: The number of cycles (zero crossings) should be at least 500 (is %d)" % j,
              file=stderr)

    p_value = list(map(lambda ksi_i, x: erfc(abs(ksi_i - j) / sqrt(2 * j * (4 * abs(x) - 2))),
                       ksi, list(range(-9, 0)) + list(range(1, 10))))

    if type(misc) == dict:
        misc.update(cumsum=s, j=j, ksi=ksi)

    return p_value