Ruby的rand函数有效种子范围是多少？

Question

Ruby将PRNG实现为“具有2 ** 19937-1周期的修改的Mersenne Twister。”1

我的理解是MT在2 ^ 32个不同的种子上运行。使我困惑的是，Random.new(seed)接受任意大的数字，例如Random.new(2 ** 100)。

但是，我无法找到（逻辑）冲突：

Random.new(1).rand(10**5) == Random.new(2**32-1).rand(10**5) => false
Random.new(1).rand(10**5) == Random.new(2**32).rand(10**5) => false
Random.new(1).rand(10**5) == Random.new(2**32+1).rand(10**5) => false

鉴于我们希望在利用 MT 的最大种子范围时尽可能使用尽可能多的不同种子，同时仍然避免两个不同种子之间的碰撞，那么哪种种子范围能实现这一点？

我尝试了解 Ruby 的随机生成器实现，但没有进展。https://github.com/ruby/ruby/blob/c5e08b764eb342538884b383f0e6428b6faf214b/random.c#L370

- randomguy

---

它在内部使用一个624个32位整数的向量（我认为 - 至少这是MT的默认实现所使用的）。您链接的代码将大整数分割成32位整数数组，以提供初始状态向量。 - Neil Slater

注意：624 * 32 = 19968。...“种子”也是 MT 的“状态”。 - Neil Slater

@NeilSlater：等等。这是否意味着Random.new(1)在某个时候会开始生成与Random.new(1000)相同的序列？ - randomguy

是的，有一个重复的单一序列，种子只是在不同的位置开始。然而，状态通常不像小的种子那样靠得很近。在实践中，你很难看到碰撞 - 如果你只是从srand(1)和srand(1000)开始生成器，并且每秒得到十亿个结果，那么在序列之间出现重叠之前我们早已经死了。可用的空间非常巨大。这与知道“我在序列中的位置”不同，后者是关于看到足够多的变化来识别状态的问题。 - Neil Slater

Neil Slater: 啊，这很有道理。为了概括一下：通过 Ruby 的实现，我们可以选择种子范围长达 19968 位数字，但代价是唯一序列长度的减少？ - randomguy

Answer 1

梅森旋转算法（Mersenne Twister）的序列长度为2 ** ( 624 * 32 - 1 ) - 1，种子值用于设置 PRNG（伪随机数生成器）的内部状态，与该序列中的位置直接相关。

最容易找到的重复似乎是每2 ** ( 624 * 32 )次，可以证明它的工作原理如下：

 repeat_every =  2 ** ( 624 * 32 )

 start_value = 5024214421  # Try any value

 r1 = Random.new( start_value )

 r2 = Random.new( start_value + repeat_every )

 r17 = Random.new( start_value + 17 * repeat_every )

 r23 = Random.new( start_value + 23 * repeat_every )

 r1.rand == r2.rand  
 # true

 r17.rand == r23.rand  
 # true

或者尝试这个：

 repeat_every =  2 ** ( 624 * 32 )

 start_value = 5024214421  # Try any value

 r1 = Random.new( start_value )

 r2 = Random.new( start_value + repeat_every )

 Array.new(10) { r1.rand(100) }
 # => [84, 86, 8, 58, 5, 21, 79, 10, 17, 50]

 Array.new(10) { r2.rand(100) }
 # => [84, 86, 8, 58, 5, 21, 79, 10, 17, 50]

重复值与Mersenne Twister的工作方式有关。MT的内部状态是一个由624个32位无符号整数组成的数组。您提供的Ruby源代码将Ruby Fixnum打包到一个数组中-这个神奇的命令是

  rb_integer_pack( seed, buf, len, sizeof(uint32_t), 0,
        INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER );

然而，这并不是易于操作的东西，它在internal.h中被定义，所以只有在Ruby解释器本身上工作时才能真正访问它。你不能从普通的C扩展中访问此功能。

然后，函数init_by_array将打包的整数加载到MT的内部状态中。这是一个看起来相当复杂的函数 - 打包的种子值没有直接写入状态，而是逐个生成状态，添加提供的数组值，使用各种异或、加法和交叉引用前一个值(这里的Ruby源代码还添加了打包数组的索引位置，注释为“非线性”，我认为这是标准MT的其中一项修改)。

请注意，MT序列的大小小于2 ** (624 * 32) - 我在这里显示的repeat_every值跳过两个序列，但它是最容易找到重复种子值的方法，因为可以轻松地看到它如何完全设置内部状态(因为种子的数组表示中的前624个项目是相同的，以后都只使用这些项目)。其他种子值也会产生相同的内部状态，但关系是一种复杂的映射，将19938位空间中的每个整数与另一个整数配对，为MT创建相同的状态。

- Neil Slater