线性同余发生器种子选择及统计检验

Question

我需要做一个线性同余发生器，将成功通过选定的统计测试。在

我的问题是：如何正确选择发电机的数字和 我应该选择哪些统计测试？在

我想：

1. 均匀性卡方频率测试

   • 每个生成方法收集10000个数字

   • 将[0.1）等分为10等分

2. Kolmogorov-Smirnov均匀性试验

   • 由于K-S测试在较小的一组数字下工作得更好，您可以使用为卡方频率测试生成的10000个数字中的前100个

下面是代码示例：

def seedLCG(initVal):
    global rand
    rand = initVal

def lcg():
    a = 1664525
    c = 1013904223
    m = 2**32
    global rand
    rand = (a*rand + c) % m
    return rand

seedLCG(1)

for i in range(1000):
    print (lcg())

说到选择种子，我考虑的是纳秒，但我不知道如何实现它，它是否有意义？这个想法是为了证明所选的种子是随机选择的，而不是从瓶盖中挑选出来的

Answer 1

关于如何正确地为生成器选择数字，在Wiki页面中有一个Hull–Dobell定理的描述，它告诉您如何选择a和{}来获得全周期生成器。你从数字食谱中得到了你的数字，据我所知，你将得到完整的周期[0…2³²）生成器。或者你可以看看this paper中的优点，有（a，c）对，适合任何大小的周期。在

关于测试，请查看提供的paper@pjs。在

when it comes to choosing seeds, I was thinking about nanoseconds, but I have no idea how to implement it and will it make sense at all? The idea is to show that the selected seeds were chosen randomly and not so much from the cap。我认为这不是一个好主意，因为你不能保证你从time/ceil/…上摘下的种子。。。不会重叠。LCG基本上是双目标的[0…2³²）<；->；[0…2³²）映射，并且相对容易重叠随机数流，因此结果是相关的。在

相反，我建议使用LCG的另一个很好的特性-对数向前（和向后）跳过。因此，为了模拟N核心，你可以选择单个种子并运行在第一个代码上，相同的种子但是跳过（N/2³²）第二个核心，种子和跳过（N/2³²*2），依此类推。在

具有显式状态和跳过的LCG的代码如下，win10x64，python3.7anaconda

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)

print(rng.next())
print(rng.next())
print(rng.next())

rng.skip(-3) # back by 3
print(rng.next())
print(rng.next())
print(rng.next())

rng.skip(-3) # back by 3
rng.skip(2) # forward by 2
print(rng.next())

更新

生成10k号码

^{pr2}$