RNG 技术的可移植性和可重复性

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

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

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

我已经尝试了几个版本的Linux，都是64位的，它们看起来是一致的，但我不容易访问Windows或32位版本。

请注意，它们不会产生彼此相同的范围，但这对我的目的来说是可以的。这些数字在人眼中必须是随机的。

方法 1
使用本机 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

最便携的版本，IMO，将是LCG，句点等于机器的自然字大小。它对模块使用寄存器溢出，使其更快。您必须使用 NumPy 数据类型来执行此操作，这里是简单的代码，常量 a、c 取自表 4 这里

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 的另一个功能是它能够在日志₂(N) 时间内向前跳转，其中 N 是跳过次数。我可以为您提供代码来执行此操作。使用跳转前瞻，您可以确保并行独立随机流的序列不重叠

更新

这是将我的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的摘要：

有了良好的常数(参见L'Ecuyer论文的参考)，它将覆盖整个[0...2⁶⁴)范围，而不会重复。基本完美的 [0...2⁶⁴) -> [0...2⁶⁴) 映射，您可以设置 0,1,2,3,...作为输入并获得整个范围输出
它是可逆的，您可以返回以前的种子，因此映射实际上是双射， [0...2 64) <-> [0...2⁶⁴).有关详细信息，请参阅可逆伪随机序列生成器
它具有向前和向后对数跳跃，因此查找没有问题适合并行计算的间隔 - 从单个种子开始，然后下一个线程将是skip(seed，2 64/N)，下一个线程skip(seed，2^64/N * 2)等等。保证不重叠
它简单快捷，虽然不是很高质量的RNG

LCG 很好。如果你想让 LCG 更容易理解，你可以递归地实现它，而不是迭代地实现它，以突出显示它所基于的递归公式。只有在您不太担心复杂性的情况下才这样做。

否则，我认为方法 2 对于 PRNG 来说已经足够清楚了。

算法(尤其是伪随机数生成器)可以通过多种方式在计算机之间产生不一致的结果。最值得注意的方法是，如果算法依赖于浮点数(几乎总是有限的精度)和浮点舍入。

某些编程语言比其他编程语言更容易出现可移植性问题。例如，与 Python 不同，C 或 C++ 中可能会出现不一致的结果，原因如下：

有符号整数溢出的未定义行为，或
某些数据类型(特别是int和long)的长度如何在编译器中以不同的方式定义。

我不知道方法 2 中的 Python 代码可以在计算机之间提供不一致的结果。另一方面，方法 1 是否可以这样做取决于random.sample是否以相同的方式在你关心的所有 Python 版本和所有计算机上实现。

相关内容

最新更新

热门标签：