梅森旋转算法(Mersenne Twister)的序列长度为2 ** ( 624 * 32 - 1 ) - 1
,种子值用于设置 PRNG(伪随机数生成器)的内部状态,与该序列中的位置直接相关。
最容易找到的重复似乎是每2 ** ( 624 * 32 )
次,可以证明它的工作原理如下:
repeat_every = 2 ** ( 624 * 32 )
start_value = 5024214421
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
r17.rand == r23.rand
或者尝试这个:
repeat_every = 2 ** ( 624 * 32 )
start_value = 5024214421
r1 = Random.new( start_value )
r2 = Random.new( start_value + repeat_every )
Array.new(10) { r1.rand(100) }
Array.new(10) { r2.rand(100) }
重复值与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创建相同的状态。
srand(1)
和srand(1000)
开始生成器,并且每秒得到十亿个结果,那么在序列之间出现重叠之前我们早已经死了。可用的空间非常巨大。这与知道“我在序列中的位置”不同,后者是关于看到足够多的变化来识别状态的问题。 - Neil Slater