8

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

2 つの異なるシードとの衝突を回避しながら、できるだけ多くの異なるシードを使用したいという意味で、MT の最大シード範囲を利用したい場合、これを実現するシード範囲は何ですか?

Ruby のランダムな実装の内部で何が起こっているのかを理解しようとしましたが、あまり理解できませんでした。https://github.com/ruby/ruby/blob/c5e08b764eb342538884b383f0e6428b6faf214b/random.c#L370

4

1 に答える 1

11

Mersenne Twister シーケンスは 2 ** ( 624 * 32 - 1 ) - 1長く、シード値は、そのシーケンス内の位置に直接関連する PRNG の内部状態を設定するために使用されます。

最も見つけやすい繰り返しは every2 ** ( 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]

リピート値は、メルセンヌ ツイスターがどのように機能するかに関連しています。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。これは非常に複雑に見える関数です。パックされたシード値は文字通り状態に書き込まれるのではなく、状態が項目ごとに生成され、提供された配列値を追加し、さまざまな xor、追加、および相互参照を使用して、以前の値 (ここの Ruby ソースは、パック配列のインデックス位置にも追加され、「非線形」とコメントされています。これは、標準 MT への参照された変更の 1 つだと思います)

MT シーケンスのサイズは以下よりも小さいことに注意してください。ここに2 ** ( 624 * 32 )示す値は、repeat_every一度に 2 つのシーケンスをスキップしていますが、内部状態を正確に設定する方法を簡単に確認できるため、繰り返しのシード値を見つけるのが最も簡単です。同じです (シードの配列表現の最初の 624 項目は同一であり、それが後で使用されるすべてであるため)。他のシード値も同じ内部状態を生成しますが、その関係は、19938 ビット空間の各整数を別の整数とペアにする複雑なマッピングであり、MT に同じ状態を作成します。

于 2013-11-19T21:36:28.667 に答える