basic_tests.py 文件源码

def runs_test(generator, n_bits, sig_level=None, fips_style=False, misc=None):
    # The expected number of gaps (or blocks) of length i in a random sequence of length n is
    # e[i] = (n-i+3)=2^(i+2). Let k be equal to the largest integer i for which ei >= 5.
    def f_e(j):
        return (n_bits - j + 3) / 2 ** (j + 2)

    if fips_style:
        k = 6
    else:
        k = 1
        while f_e(k + 1) >= 5:
            k += 1

    # Let B[i], G[i] be the number of blocks and gaps, respectively, of length i in s for each i,
    # 1 <= i <= k.
    run_bit = None
    run_length = 0
    max_run_length = 0
    b = [0] * k  # zero-indexed
    g = [0] * k
    for i in range(n_bits + 1):
        bit = generator.random_bit() if i < n_bits else None

        # ongoing run
        if run_bit == bit:
            run_length += 1

        # run ended (or it's the beginning or end)
        if run_bit != bit:
            if run_length > max_run_length:
                max_run_length = run_length
            if fips_style and run_length > 6:
                run_length = 6
            if 1 <= run_length <= k:
                if run_bit == 0:
                    g[run_length - 1] += 1  # zero-indexed!
                elif run_bit == 1:
                    b[run_length - 1] += 1
            # reset counter
            run_bit = bit
            run_length = 1

    # Calculate the statistic:
    e = [f_e(i) for i in range(1, k + 1)]
    x4 = sum([(x - e[i]) ** 2 / e[i] for i, x in list(enumerate(b)) + list(enumerate(g))])

    if type(misc) is dict:
        misc.update(k=k, b=b, g=g, e=e, max_run=max_run_length)

    if sig_level is None:
        return x4
    else:
        limit = chi2.ppf(1 - sig_level, 2 * (k - 1))
        if type(misc) is dict:
            misc.update(x=x4, limit=limit)
        return x4 <= limit