System.Random 和无限猴子定理

会员 4201813

4.80/5 (9投票s)

2018年4月13日

CPOL

16分钟阅读

19034

258

使用对数复杂度沿着 System.Random 输出序列进行跳转

下载源代码 - 17.3 KB

引言

随机数生成器 (RNG) 用于各种软件应用，但它们通常被当作一种“黑匣子”，仅仅返回一系列随机数。然而，有时我们需要深入了解并获得更高级的功能，例如保存当前生成器状态以便以后恢复，或者在给定一些前导数字的情况下预测后续的随机数等。解决这些问题需要对 RNG 算法有更深入的了解。本文介绍了一种适用于广泛 RNG 的有用技术，该技术不仅可以带来有趣的、也可以应用于实际项目的结果。

本文的灵感来源于 PCG 网站上的一则笑话：该生成器除了其他有趣的特性外，还可以强制输出某些预定义的文本。广为人知的无限猴子定理指出，通过随机过程产生这种结果是可能的，但极其罕见。我们能否使用不那么高级的算法，例如 .NET Framework 中的 System.Random，来实现类似的功能呢？幸运的是，答案是“可以”。Hiroshi Haramoto、Makoto Matsumoto、Takuji Nishimura、François Panneton 和 Pierre L'Ecuyer 的研究论文《Efficient Jump Ahead for $\mathbb{F}_2$-Linear Random Number Generators》描述了一种用于导航基于线性递推的生成器随机数序列的技术。虽然他们论文的主要目标是介绍涉及二阶伽罗瓦域上多项式算术的先进算法，但其中也提到了一个更简单但效率较低的基于矩阵乘法的简单方法。在我们的探索过程中，我们将了解 System.Random 的工作原理，为什么它的结构使其具有线性，以及最终如何使用矩阵乘法来产生预定义输出。

背景

假设读者对 RNG 有基本的经验，例如创建它们、正确初始化它们以生成可重现的随机数序列、获取这些数字等。中等水平的 C# 经验足以理解代码。在解释代码之外的数学内容时，需要对代数（矩阵乘法）有所了解。

本文的代码可以使用 .NET Framework 4 和 Visual Studio 2017 Community Edition 来构建。单元测试需要 NUnit，但如果您不希望安装该框架，可以将其从项目中删除。

猴子打字机

让我们从展示最终结果开始：一个简单的程序，强制标准的 System.Random 生成英文文本。本文附带的存档包含一个解决方案中一组相关项目的源代码，名为 MonkeyTypewriter。请在您喜欢的 .NET 开发环境中打开该解决方案，并探索 MonkeyTypewriter.cs。此文件包含一个简单的控制台应用程序的代码。首先，我们可以看到两个辅助函数：GetSeries() 和 DumpSeries()。这些函数的实现细节对我们的目标并不重要，我们仅简要描述它们的作用。

IEnumerable<byte> GetSeries(Random rng, uint size)

GetSeries() 是一个适配器函数，它将 System.Random 实例生成的 32 位整数序列转换为指定大小的字节序列。

void DumpSeries(IEnumerator<byte> seriesIter, uint pos, uint size)

DumpSeries() 接收一个字节流的迭代器，并以十六进制和 ASCII 格式将其内容输出到控制台，用点号替换不可打印的 ASCII 码。

现在，这是 Main() 方法，它值得更详细的描述。首先，我们创建一个标准的 .NET 随机生成器实例，并使用一组魔术数字 initialState 来设置其内部状态。我们可以看到 SetState() 方法的使用，它不是 System.Random 的一部分。此方法被实现为 System.Random 的扩展，可以在 RandomExt 类中找到。稍后将对其进行解释。

Random rng = new Random();
			
int [] initialState = {...};

rng.SetState(initialState);

之后，我们将生成一个随机字节序列并打印出来。为了使输出更简洁，我们打印序列的开头，然后跳过一些字节，最后输出我们期望看到一些有趣内容的数据片段。这个过程由一组计数器管理：标题块的长度应为 startingChunkSize 字节，后跟 skippedChunkSize 个跳过的字节，最后，我们在 payloadOffset 之前 payloadPaddingSize 字节处恢复输出，在那里我们将检查 payloadSize 字节。

const uint startingChunkSize  = 100;
const uint payloadOffset      = 1000;
const uint payloadSize        = 250;
const uint payloadPaddingSize = 50;
const uint skippedChunkSize   = payloadOffset - payloadPaddingSize - startingChunkSize;
			
var series = GetSeries(rng, payloadOffset + payloadSize);
			
var seriesIter = series.GetEnumerator();
			
DumpSeries(seriesIter, 0, startingChunkSize);
			
Console.WriteLine("\nSkipping {0} bytes...\n", skippedChunkSize);

for(int i = 0; i < skippedChunkSize; i++)
    seriesIter.MoveNext();
			
DumpSeries(seriesIter, startingChunkSize + skippedChunkSize, payloadPaddingSize + payloadSize);

该程序的输出应如下所示

00000000 79 37 CE 3E 48 DE A6 02 C4 84 40 06 DC 78 58 36 y7.>H.....@..xX6
00000010 26 F8 DC 68 5F 05 1C 74 EA CB 5D 53 11 90 62 6B &..h_..t..]S..bk
00000020 D6 11 9B 5E 27 29 30 54 43 62 D5 6B 1A 1C E2 1C ...^')0TCb.k....
00000030 16 7C D1 7B D3 9A 1E 50 66 E0 F2 7B 9D 5E 0C 1B .|.{...Pf..{.^..
00000040 CE 96 7A 2F 40 E4 E5 43 6E EB 3C 74 60 7C 53 79 ..z/@..Cn.<t`|Sy
00000050 89 74 24 6F 17 19 D5 31 90 A2 E7 41 54 0B 43 22 .t$o...1...AT.C"
00000060 16 F2 4B 4F                                     ..KO            

Skipping 850 bytes...

000003B6                   81 66 DF 9E 85 1F CA D2 DF 4E       .f.......N
000003C0 E3 85 CF 4E DB 8B A3 33 6F E1 A7 52 6E 4D D4 46 ...N...3o..RnM.F
000003D0 1B EA FA 66 C1 55 39 51 E1 99 19 16 DA 05 73 7E ...f.U9Q......s~
000003E0 7C 72 6E 44 C7 35 C0 7B 4D 6F 6E 6B 65 79 20 68 |rnD.5.{Monkey h
000003F0 69 74 74 69 6E 67 20 6B 65 79 73 20 61 74 20 72 itting keys at r
00000400 61 6E 64 6F 6D 20 6F 6E 20 61 20 74 79 70 65 77 andom on a typew
00000410 72 69 74 65 72 20 6B 65 79 62 6F 61 72 64 20 66 riter keyboard f
00000420 6F 72 20 61 6E 20 69 6E 66 69 6E 69 74 65 20 61 or an infinite a
00000430 6D 6F 75 6E 74 20 6F 66 20 74 69 6D 65 20 77 69 mount of time wi
00000440 6C 6C 20 61 6C 6D 6F 73 74 20 73 75 72 65 6C 79 ll almost surely
00000450 20 74 79 70 65 20 61 20 67 69 76 65 6E 20 74 65  type a given te
00000460 78 74 2C 20 73 75 63 68 20 61 73 20 74 68 65 20 xt, such as the 
00000470 63 6F 6D 70 6C 65 74 65 20 77 6F 72 6B 73 20 6F complete works o
00000480 66 20 57 69 6C 6C 69 61 6D 20 53 68 61 6B 65 73 f William Shakes
00000490 70 65 61 72 65 2E 20 28 57 69 6B 69 70 65 64 69 peare. (Wikipedi
000004A0 61 29 34 52 FC 7C 87 6C FE DA B3 65 AC C9 91 78 a)4R.|.l...e...x
000004B0 5A EC CA 67 6C 34 F9 34 6D 96 FD 0F 07 52 FF 5D Z..gl4.4m....R.]
000004C0 A7 C1 56 0E E8 4E F7 01 F9 0C 00 07 FC 06 05 76 ..V..N.........v
000004D0 F9 46 AD 75 F2 13 07 27 41 00 A7 01 FC 4D 03 4F .F.u...'A....M.O
000004E0 06 B7                                           ..

不可思议！从偏移量 0x3E8（即 1000）开始，我们看到了一个来自关于无限猴子定理的维基百科文章的摘录，该摘录是由标准库实现的著名 RNG 算法生成的。秘密武器无疑是将在下一节中详细介绍的那个棘手的初始化序列。

探索 RNG 内部

首先，让我们弄清楚 System.Random 使用的是哪种算法。我们从哪里可以获得它的描述？GitHub 上有 .NET Framework 的开源实现。System.Random 的代码可以在 Random.cs 中找到。准确地说，我们将在实验中使用此修订版。

查看 InternalSample() 方法，我们可以识别该算法：它被称为减法滞后斐波那契生成器。该生成器使用以下公式生成下一个随机数

$\label{eq:lf} x_i = x_{i-55} - x_{i-34} \pmod{2^{31}-1}. \tag{1} $

请注意，滞后值 55 和 34 是此实现特有的，但本文讨论的一般思想适用于整个滞后斐波那契 RNG 系列。将该公式放入代码中，我们需要保存最后 55 个生成的随机数，并在每次生成下一个时更新它们。对于这项任务，循环缓冲区是完美的匹配。正如我们在代码中看到的，分配了一个大小为 56 的缓冲区作为 _seedArray，最后一个使用的项由 _inext 指向，它在每次向缓冲区添加新项时都会递增。辅助索引 _inextp 表示第二个滞后的位置，并跟随 _inext，保持一定距离。

我们对库代码的第一项改进是用于保存和恢复生成器内部状态的方法。以明显的方式进行，我们应该保留所有 private 数据不变，即一个数组和两个索引。但是，还有另一种更方便的方法：按线性顺序（从其起始元素到最后一个）保存队列的状态，以便在不环绕边界的情况下填充目标缓冲区。

为了方便起见，我们处理 RNG 状态的代码将在 RandomExt 类中作为扩展方法实现。由于 RNG 数据字段是 private 的，我们将不得不使用反射来访问它们。对于每个数据字段，我们应该获取 FieldInfo。这些辅助函数可以设为 static，因此我们可以在 RandomExt 的 static 构造函数中初始化它们。

private static readonly System.Reflection.FieldInfo seedArrayField;
private static readonly System.Reflection.FieldInfo inextField;
private static readonly System.Reflection.FieldInfo inextpField;

static RandomExt()
{
    Type rngType = typeof(Random);

    seedArrayField = rngType.GetField("SeedArray", System.Reflection.BindingFlags.NonPublic | 
                     System.Reflection.BindingFlags.Instance);
    inextField     = rngType.GetField("inext", System.Reflection.BindingFlags.NonPublic | 
                     System.Reflection.BindingFlags.Instance);
    inextpField    = rngType.GetField("inextp", System.Reflection.BindingFlags.NonPublic | 
                     System.Reflection.BindingFlags.Instance);
}

请注意，上面代码中的字段名称与我们用于参考的 GitHub 代码中的名称不同。结果是，从 Windows SDK 安装的 .NET Framework 4 与开源实现不同，并且使用没有下划线的字段名称。幸运的是，这是发现的唯一区别，因此基于开源框架实现的代码与官方实现一起工作良好。检索给定 System.Random 实例状态的方法 GetState() 的实现如下

public static int[] GetState(this Random rng)
{
    int   inext      = (int)inextField.GetValue(rng);
    int[] seedArray  = (int[])seedArrayField.GetValue(rng);
			
    int[] state = new int[seedArray.Length - 1];
			
    int upperChunkSize = seedArray.Length - (inext + 1);

    Array.Copy(seedArray, inext + 1, state, 0, upperChunkSize);
    Array.Copy(seedArray, 1, state, upperChunkSize, inext);
			
    return state;
}

我们将状态保存为原始整数数组，以简化后续操作。对于生产代码，将状态保存在某个不透明对象中会更好。从保存的数据恢复 RNG 状态甚至更简单。

public static void SetState(this Random rng, int[] state)
{
    int[] seedArray = (int[])seedArrayField.GetValue(rng);
			
    state.CopyTo(seedArray, 1);
			
    inextField.SetValue(rng, 0);
    inextpField.SetValue(rng, 21);
}

让我们回到我们的实验，看看在生成随机数时 RNG 的内部状态是如何改变的。演示程序 Explore.cs 使用扩展方法 GetState() 来生成 4 个随机数，并在获取每个随机数之前保存 RNG 状态。

之后，这些状态将与 CompareStates() 对齐打印。为了简洁起见，本文未显示部分输出。

 0, 12501C5F, 0261CFD7, 0EE1DDBA, 305F5F61, 6B945933
 1, 0261CFD7, 0EE1DDBA, 305F5F61, 6B945933, 5EFEC028
 2, 0EE1DDBA, 305F5F61, 6B945933, 5EFEC028, 0882DB09
 3, 305F5F61, 6B945933, 5EFEC028, 0882DB09, 58BFEC38
 4, 6B945933, 5EFEC028, 0882DB09, 58BFEC38, 7186A68A
 5, 5EFEC028, 0882DB09, 58BFEC38, 7186A68A, 119335E0
 6, 0882DB09, 58BFEC38, 7186A68A, 119335E0, 5AB9802F
 7, 58BFEC38, 7186A68A, 119335E0, 5AB9802F, 085EDD91
 8, 7186A68A, 119335E0, 5AB9802F, 085EDD91, 464A53F4
 9, 119335E0, 5AB9802F, 085EDD91, 464A53F4, 25F50014
10, 5AB9802F, 085EDD91, 464A53F4, 25F50014, 0D71DBE2
...
20, 25C17A83, 3CCB9920, 70588FBF, 7ED0E1FF, 6D756ECA
21, 3CCB9920, 70588FBF, 7ED0E1FF, 6D756ECA, 56051885
22, 70588FBF, 7ED0E1FF, 6D756ECA, 56051885, 3D621D24
23, 7ED0E1FF, 6D756ECA, 56051885, 3D621D24, 2BC9713B
24, 6D756ECA, 56051885, 3D621D24, 2BC9713B, 171877FD
25, 56051885, 3D621D24, 2BC9713B, 171877FD, 5B4C72F1
...
45, 04FCC85C, 10E756FA, 37BB801B, 50C25426, 042EA0A6
46, 10E756FA, 37BB801B, 50C25426, 042EA0A6, 674DAB56
47, 37BB801B, 50C25426, 042EA0A6, 674DAB56, 577BC5A8
48, 50C25426, 042EA0A6, 674DAB56, 577BC5A8, 7A98A95A
49, 042EA0A6, 674DAB56, 577BC5A8, 7A98A95A, 4F93B56B
50, 674DAB56, 577BC5A8, 7A98A95A, 4F93B56B, 0042832E
51, 577BC5A8, 7A98A95A, 4F93B56B, 0042832E, 5584833E
52, 7A98A95A, 4F93B56B, 0042832E, 5584833E, 12094017
53, 4F93B56B, 0042832E, 5584833E, 12094017, 1010FBBA
54, 0042832E, 5584833E, 12094017, 1010FBBA, 42E9F096

第一个随机数 0x5584833E 是通过从缓冲区中取第 0 个元素 0x12501C5F 并减去第 21 个元素 0x3CCB9920（模 $2^{31}-1$）来计算的

$ \mathrm{12501C5F}_{16} - \mathrm{3CCB9920}_{16} = \mathrm{D584833F}_{16} \equiv \mathrm{5584833E}_{16} \pmod{2^{31}-1} $

如果我们比较生成此数字之前的 RNG 状态（第 1 列）和之后的（第 2 列），我们可以看到初始状态中的第 0 个元素已被丢弃，所有后续数字都向上移动了一个位置，并且队列中的最后一个元素被最近生成的随机数填充。重复几次，可以看到相同的模式。现在，我们可以利用这些信息来制作该 RNG 的另一种数学模型，该模型将具有一些重要的优势。

向量表示和线性 RNG

我们最初的滞后斐波那契生成器公式 $(\ref{eq:lf})$ 通过一个整数序列 $\{x_i\}$ 定义，我们需要保留一些历史来计算下一个 $x_i$。巧妙地使用循环缓冲区进行操作仅仅是实现细节。有人可能会设想一个递归算法，每次需要下一个随机数时都将序列从头开始重新计算两次。虽然效率极低，但这种方式也是合法的。

进一步，我们可以将循环缓冲区作为一个整体随时间变化的对象来处理。也就是说，让我们将其视为一个长度为 55 的数字向量（这里我们将使用零基项索引，这对于数学家来说有点不寻常，但更符合代码）

$ X = \langle X_0, X_1, \ldots X_{54}\rangle, \quad 0 \le X_i< 2^{31}-1. $

在这种情况下，我们可以定义一个转换函数 $s$，从前一个状态生成下一个状态

$ X^{(i)} = s(X^{({i-1})}). $

我们还可以定义一个函数 $r$，将随机状态 $X^{(i)}$ 映射到第 $i$ 个随机数 $x_i$

$ x_i = r(X^{(i)}). $

对于滞后斐波那契，后者很简单，只是获取第 $i$ 个状态的第 55 个分量

$ x_i = X^{(i)}_{54}. $

现在我们应该定义 $X' = s(X)$

$ X'_i = \begin{cases} X_{i+1}, & 0 \le i < 53, \\ X_0 - X_{21} \pmod{2^{31}-1}, & i = 54. \end{cases} $

这个定义可以改写如下：让我们将每个状态分量视为过去所有状态分量乘以某些常数的总和。这样，我们可以使用简单的算术而不带任何条件来统一表示上述两种情况。确实，在两种情况下，我们都可以通过乘以零来屏蔽不需要的分量，而需要的分量则自然地从上面的定义中获取其系数

$ \begin{align*} X'_0 &= 0\cdot X_0 + 1\cdot X_1 + 0\cdot X_2 + 0\cdot X_3 + \cdots + 0\cdot X_{20} + 0\cdot X_{21} + 0\cdot X_{22} + \cdots + 0\cdot X_{54}\pmod{2^{31}-1},\\ X'_1 &= 0\cdot X_0 + 0\cdot X_1 + 1\cdot X_2 + 0\cdot X_3 + \cdots + 0\cdot X_{20} + 0\cdot X_{21} + 0\cdot X_{22} + \cdots + 0\cdot X_{54}\pmod{2^{31}-1},\\ &\vdots \\ X'_{53} &= 0\cdot X_0 + 0\cdot X_1 + 0\cdot X_2 + 0\cdot X_3 + \cdots + 0\cdot X_{20} + 0\cdot X_{21} + 0\cdot X_{22} + \cdots + 1\cdot X_{54}\pmod{2^{31}-1},\\ X'_{54} &= 1\cdot X_0 + 0\cdot X_1 + 0\cdot X_2 + 0\cdot X_3 + \cdots + 0\cdot X_{20} - 1\cdot X_{21} + 0\cdot X_{22} + \cdots + 0\cdot X_{54}\pmod{2^{31}-1},\\ \end{align*} $

这反过来是一个矩阵乘积，其中 $X$ 与常数矩阵 $A$ 相乘

$ \label{eq:linrng} X' = AX, \tag{2} $

其中，特定于我们的滞后斐波那契 RNG 的 $A$ 为

$ \label{eq:stepforward} a_{ij} = \begin{cases} 1, & 0 \le i \le 53, j = i + 1,\\ 1, & i = 54, j = 0,\\ -1, & i = 54, j = 21,\\ 0, & \mbox{otherwise}. \end{cases} \tag{3} $

不同的 $A$ 代表不同的 RNG 算法，这些算法可能好也可能坏。例如

$ \label{eq:stepbackward} a_{ij} = \begin{cases} 1, & i = 0, j = 54,\\ 1, & i = 0, j = 20,\\ 1, & 1 \le i \le 54, j = i - 1,\\ 0, & \mbox{otherwise} \end{cases} \tag{4} $

生成的随机数序列与 System.Random 相同，但方向相反。类似地，$A=I$（单位矩阵）表示退化情况，此时 RNG 生成常数序列。

其算法可以表示为 $(\ref{eq:linrng})$ 的 RNG 系列被称为“线性随机数生成器”。除了滞后斐波那契，这个系列还包括流行的算法，如梅森旋转算法或 xorshift。

现在是时候问一个自然的问题了：这些矩阵乘法难道不是在浪费计算资源吗？是的，事实上，使用循环缓冲区实现的滞后斐波那契 RNG 可以通过一次减法/加法缓冲区项以及一些移动一对缓冲区指针的工作来向前（或向后）推进。而矩阵乘法在一般情况下，对于大小为 $k$ 的矩阵，需要至少 $O(k^2)$ 次操作。考虑到矩阵 $A$ 是稀疏的，如果消除不必要的操作，我们可以获得更好的性能，但这最终会导致我们回到原始算法。

然而，矩阵表示具有文章开头介绍的研究论文中提到的优点。让我们从某个初始状态 $X^{(0)}$ 开始，进行 $n$ 步

$ \begin{align*} X^{(1)} &= AX^{(0)},\\ X^{(2)} &= AX^{(1)} &= AAX^{(0)} &= A^2X^{(0)},\\ &\vdots\\ X^{(n)} &= AX^{(n-1)} &= A\ldots AX^{(0)} &= A^n X^{(0)}.\\ \end{align*} $

这意味着，如果我们知道相应的 $A^n$，我们可以直接从初始状态获得第 $n$ 个随机数。并且有一个著名的算法，可以在 $O(\log n)$ 步内计算出该幂。也就是说，我们可以以对数复杂度沿着我们的随机序列向前或向后跳转 $n$ 步。同时，直接进行 $n$ 步操作的复杂度是线性的。给定 $n$ 很大，即使有矩阵乘法带来的较大的常数因子，对数方法也会优于线性方法。

RandomExt 包含一些基于上述理论的辅助函数。例如，ForwardStep() 和 BackwardStep() 分别生成矩阵 $(\ref{eq:stepforward})$ 和 $(\ref{eq:stepbackward})$。还有其他函数实现了矩阵乘法和求幂。它们可以组合起来生成所需的转换矩阵，然后将其应用于 GetState() 保存的随机状态，再用 SetState() 加载回 RNG。这种方法看起来有些粗糙，但似乎足以作为概念验证。

从学术界到生产

让我们利用线性 RNG 的理论背景来开发一些有用的代码。首先，让我们详细解释第 Monkey Typewriter 节中的技巧是如何实现的。我们记得 System.Random 的状态由 55 个 32 位整数组成，因此我们可以放入 220 字节的数据。但是，并非所有字节组合都是允许的：每个整数都应位于 $[0, 2^{31}-1)$ 范围内。另外，状态向量不能为零，因为它会破坏生成器（公式 $(\ref{eq:lf})$ 在这种情况下开始生成全零）。如果我们只使用 0 到 127 的字节值，第一个限制将得到满足，并且这个范围足以表示用经典的 7 位 ASCII 编码的消息。至于第二个限制，我们只需要记住它。

在用所需载荷填充状态向量后，我们可以使用上面描述的矩阵乘法向后移动 55 步，得到一个新的状态。如果我们设置了这个新状态到随机生成器并开始从该 RNG 中检索随机数，在 55 步之后，我们将得到初始状态，同时它的所有分量都将作为生成器的随机数输出。这就是我们强制 RNG 生成某些预定义序列所需的一切！为了让这个技巧更令人印象深刻，我们还可以向后移动更多步，以便我们的预定义内容出现在一些随机数据之后。

Prepare.cs 中的代码完全实现了这个“modus operandi”。这个控制台应用程序将所需的短语及其在未来随机流中的偏移量作为命令行参数。为了简单起见，假设偏移量是 4 的倍数，因此载荷从状态项的边界开始。然后使用 RandomExt 中的辅助方法来计算所需步数的转换矩阵，最后计算应该设置到 RNG 以生成指定短语的初始状态向量。然后将此向量打印到标准输出，并可以手动插入到我们首先探索的 MonkeyTypewriter 的源代码中。

我们还可以利用这种理论来实现多个随机数“流”。也就是说，从一个种子值生成多个随机序列。这该如何实现？假设我们有一个周期为 $N$ 的 RNG，并选择我们要使用的流的数量 $s$（$s \ll N$）。我们可以将原始序列分成 $s$ 组连续的数字，每组有 $\lfloor \frac{N}{s} \rfloor$ 个项，每组用于生成一个流。

只要您能够移动到随机序列中的给定位置，实现这个想法就很简单，而我们刚刚学会了如何做到这一点。

使用流在需要协调多个协同工作的 RNG 时非常方便，例如在分布式蒙特卡洛模拟等场景中。我们的目标是确保多个 RNG 不会生成相同的数字。

一种可能的方法是使用不同的随机种子来初始化这些 RNG。我们将不得不实现一些种子管理方案，例如，指定一个“主工作节点”，负责为其他节点播种。

我们也可以在每个工作节点上使用本地 RNG 来生成分布式引擎的随机种子。在这种情况下可能会发生种子冲突，但概率相当低。更重要的是，这种方法缺乏可重现性：更改工作节点数量，甚至再次运行计算，都会得到一组不同的随机数。

任何基于种子的场景还有一个额外的问题：我们不能确定从不同种子生成的随机数序列不会过早重叠。然而，这种重叠的概率相当低。

无论如何，这种初始化代码会增加整体复杂性。另一方面，使用独立流看起来要简单得多。我们将只使用一个对所有工作节点通用的随机种子。每个工作节点仍然负责获取正确的流索引，但与随机种子不同，流索引可以通过更确定的算法（例如使用 MPI rank）由工作节点计算得出。此外，有了流，我们可以确切地知道它们何时开始重叠，因此我们可以决定这是否对我们是安全的。

这两种方法可以结合起来，为我们提供更多的“自由度”。

结语

在我们旅程的最后，让我们总结一下我们学到的知识。我们看到了开源如何帮助我们理解工具，如何利用 C# 和 .NET 的特性（如扩展方法和反射）来定制闭源库。我们还接触了像循环缓冲区这样的有用数据结构，以及像平方求幂这样优雅的算法。我一直对 Strassen 算法以来的矩阵乘法进展感到非常惊讶。此外，我们现在对 System.Random 背后的算法有了更详细的了解，这可以防止我们误用它。我们看到了该算法与其他一些算法（线性）共有的共同属性，以及如何利用这些属性沿随机序列向两个方向导航。最后，我们应用了这一理论来制作产生有趣输出的 RNG，并勾勒出了更实用的独立随机流及其在分布式计算中的应用。

另请参阅

有关沿线性随机流跳转的更多信息，包括基于多项式算术的更有效算法，请参见

历史

2018 年 4 月 13 日：初始版本
2020 年 5 月 4 日：添加了“另请参阅”部分