线性同余生成器 - 弱测试结果

Question

我正在尝试对我的线性同余生成器进行 Dieharder Suite 测试。

我不确定是在我的发电机上进行了测试，还是只是结果太弱了。

我用生成器生成 2,5 行 mio 行，将它们保存到文件 testrands.txt 中 header:

#==================================================================
# 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 通过了 birthday-spacing（我认为它不应该）并且其余结果出奇地薄弱

我的 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 is not the same thing as the birthday test. It is possible for an LCG to pass the former, but any full-cycle k-bit generator which reports its full k-bit state will always fail the latter at an α ≤ 0.01 level for any sample size n ≥ 3*2^k/2. (For your 32-bit implementation, that's a sample size of 3*2¹⁶ = 196608.) There won't be any duplicate values if it's a full-cycle generator, and the "birthday paradox" 告诉我们如果值流是真正随机的，则至少应该有一个 p ≥ 0.99。

线性同余生成器 - 弱测试结果

Linear congruential generator - weak tests results

python

random

numpy

lcg