8

Ruby 将 PRNG 实现为“经过修改的 Mersenne Twister，周期为 2**19937-1”。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

4

1 回答 1

11

Mersenne Twister 序列很 2 ** ( 624 * 32 - 1 ) - 1长，种子值用于为 PRNG 设置与该序列中的位置直接相关的内部状态。

最容易找到的重复似乎是 every 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 扩展中访问此函数。

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

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

于 2013-11-19T21:36:28.667 回答