python - RNG 技术的便携性和可重复性

Question

我可以使用两种方法中的一种来创建具有两个重要特征的伪随机数序列 - (1) 它可以在不同的机器上重现，并且 (2) 该序列从不重复范围内的数字，直到所有数字都被发出.

我的问题是 - 这些方法中的任何一种在可移植性(操作系统、Python 版本等)方面是否存在潜在问题？例如，有谁知道当 XXX 为真时我是否会在一个系统上获得一组结果而在另一个系统上获得不同的结果？

我并不是真的征求关于使用哪种方法本身的建议，只是当 Z 为真时我应该注意 Y 系统上的 X。

我试过几个 Linux 版本，都是 64 位的，它们看起来一致，但我无法轻松访问 Windows 或 32 位版本。

请注意，它们不会产生彼此相同的范围，但这对我来说没问题。这些数字只需要在人眼看来是随机的。

方法 1
使用 native Python 库函数从一个范围内生成一个随机样本。如果我使用大范围(10m 或更大)，它会很慢，但对于相对较小的范围来说还可以，并且对于没有数学学位的人来说更容易理解:

import random
random.seed(5)
x = random.sample(range(10000,99999),89999)
for i in range(10):
   print(x[i])

方法 2
使用的算法不是来自 Python 库:
( https://en.wikipedia.org/wiki/Linear_congruential_generator )
即使对于大范围，它也非常快，但更难理解，因此发现潜在问题:

def lcg(modulus, a, c, seed):
  while True:
    seed = (a * seed + c) % modulus
    yield seed


m = 10000019
c = int(m/2)
a = 5653
s = a

g = lcg(m,a,c,s)
for _ in range(10):
  print(next(g))

请注意，我对其他选择持开放态度；最初的问题是在这里提出的:https://math.stackexchange.com/questions/3289084/generate-a-pseudo-random-predictable-non-repeating-integer-sequence-purely-math

Answer 1

大多数便携版本，IMO，将是周期等于机器自然字大小的 LCG。它为模块使用寄存器溢出，使其更快。你必须使用 NumPy 数据类型来做到这一点，这里是简单的代码，常量 a、c 取自表 4 here

import numpy as np

def LCG(seed: np.uint64, a: np.uint64, c: np.uint64) -> np.uint64:
    with np.errstate(over='ignore'):
        while True:
            seed = (a * seed + c)
            yield seed

a = np.uint64(2862933555777941757)
c = np.uint64(1)

rng64 = LCG(np.uint64(17), a, c)

print(next(rng64))
print(next(rng64))
print(next(rng64))

Linux x64 和 Windows x64 以及 OS X VM 的工作方式完全相同。

关于可重复性，唯一的好处是存储前几个数字并在应用程序初始化阶段将它们与 LCG 输出进行比较 - 如果它们没问题，您可以继续进行。

我喜欢 LCG 的另一个特点是它能够在 log₂(N) 时间内向前跳跃，其中 N 是跳跃次数。我可以为您提供代码来做到这一点。使用 jump ahead 可以确保并行独立随机流的非重叠序列

更新

这里是我的 C 代码到 Python/NumPy 的翻译，似乎有效。它可以在对数时间向前和向后跳跃。

import numpy as np

class LCG(object):

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

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

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

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

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

    def skip(self, ns: np.int64) -> 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.uint64 = np.uint64(ns)

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

        a_next: np.uint64 = LCG.UONE
        c_next: np.uint64 = 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.uint64(2862933555777941757)
c = np.uint64(1)
seed = np.uint64(1)

rng64 = LCG(seed, a, c) # initialization

print(rng64.next())
print(rng64.next())
print(rng64.next())

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

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

无论如何，LCG RNG 的总结:

1. 有了良好的常量(参见 L'Ecuyer 论文的引用资料)，它将覆盖整个 [0...2⁶⁴) 范围而不会重复自身。基本完美 [0...2⁶⁴) -> [0...2⁶⁴) 映射，你可以设置0,1,2,3,...作为输入并得到全范围输出
2. 它是可逆的，你可以取回之前的种子，所以映射实际上是双射，[0...2⁶⁴) <-> [0...2⁶⁴)。有关详细信息，请参见 Reversible pseudo-random sequence generator
3. 它有对数向前和向后跳跃，所以找起来没有问题并行计算的合适间隔 - 从单个种子开始，然后下一个线程将被跳过(种子，2⁶⁴/N)，下一个线程将被跳过(种子，2⁶⁴/N * 2) 等等等等。保证不重叠
4. 它简单快速，虽然不是一个非常高质量的 RNG