线性同余发生器弱测试结果

Question

我想在我的线性同余生成器上做Dieharder Suite测试。你知道吗

我不确定测试是在我的生成器上进行的，还是结果太差。你知道吗

我用生成器生成了250万行，保存到文件中testrands.txt文件使用此标题：

#==================================================================
# generator lcg  seed = 1
#==================================================================
type: d
count: 100000
numbit: 32
1015568748
1586005467
2165703038
3027450565
217083232
1587069247
......

我遵循this指令（如示例所示）

然后我使用Dieharder suite以以下方式执行测试：

dieharder -g 202 -f testrands.txt -a

现在的结果出奇的弱（也许我生成的数字太少？）你知道吗

我照指南上的做了，但似乎还是有些不应该做的事情——LCG过了一个生日间隔（我认为不应该），剩下的结果出奇的弱

我的LCG：

import numpy as np

class LCG(object):

    UZERO: np.uint32 = np.uint32(0)
    UONE : np.uint32 = np.uint32(1)

    def __init__(self, seed: np.uint32, a: np.uint32, c: np.uint32) -> None:
        self._seed: np.uint32 = np.uint32(seed)
        self._a   : np.uint32 = np.uint32(a)
        self._c   : np.uint32 = np.uint32(c)

    def next(self) -> np.uint32:
        self._seed = self._a * self._seed + self._c
        return self._seed

    def seed(self) -> np.uint32:
        return self._seed

    def set_seed(self, seed: np.uint32) -> np.uint32:
        self._seed = seed

    def skip(self, ns: np.int32) -> None:
        """
        Signed argument - skip forward as well as backward

        The algorithm here to determine the parameters used to skip ahead is
        described in the paper F. Brown, "Random Number Generation with Arbitrary Stride,"
        Trans. Am. Nucl. Soc. (Nov. 1994). This algorithm is able to skip ahead in
        O(log2(N)) operations instead of O(N). It computes parameters
        A and C which can then be used to find x_N = A*x_0 + C mod 2^M.
        """

        nskip: np.uint32 = np.uint32(ns)

        a: np.uint32 = self._a
        c: np.uint32 = self._c

        a_next: np.uint32 = LCG.UONE
        c_next: np.uint32 = LCG.UZERO

        while nskip > LCG.UZERO:
            if (nskip & LCG.UONE) != LCG.UZERO:
                a_next = a_next * a
                c_next = c_next * a + c

            c = (a + LCG.UONE) * c
            a = a * a

            nskip = nskip >> LCG.UONE

        self._seed = a_next * self._seed + c_next


#%%
np.seterr(over='ignore')

a = np.uint32(1664525)
c = np.uint32(1013904223)
seed = np.uint32(1)

rng = LCG(seed, a, c)
q = [rng.next() for _ in range(0, 2500000)]

Answer 1

恭喜你，你已经证明了你的LCG实现与更现代的生成器没有竞争力。你知道吗

请注意，birthday spacings test和birthday test不是一回事。LCG有可能通过前者，但对于任何样本大小n≥3*2^{k/2的情况，任何报告其全k位状态的全周期k位发生器都将始终使后者在α≤0.01水平上失败。（对于32位实现，样本大小为3*216=196608。）如果是全周期生成器，则不会有任何重复值，"birthday paradox"告诉我们，如果值流是真正随机的，则至少应该有一个p≥0.99的值。你知道吗}