Каков эффективный начальный диапазон ранда Руби?

Ruby реализует PRNG как «модифицированный вихрь Мерсенна с периодом 2**19937-1». 1

Насколько я понимаю МП, он работает с 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/c5e08b764eb342538884b383f0e603c/random#Lrandom#L314b /а>


ruby random random-seed mersenne-twister
person randomguy    schedule 19.11.2013    source источник
comment
Внутри он использует вектор из 624 32-битных целых чисел (я думаю - по крайней мере, это то, что будут использовать реализации MT по умолчанию). Код, который вы связали, разбивает большое целое число на массив 32-битных целых чисел, которые передают начальный вектор состояния.   -  person Neil Slater    schedule 19.11.2013
comment
Примечание: 624 * 32 = 19968. . . сид также является состоянием для MT   -  person Neil Slater    schedule 19.11.2013
comment
@NeilSlater: Так что подожди. Означает ли это, что Random.new(1) в какой-то момент начнет генерировать ту же последовательность, что и Random.new(1000)?   -  person randomguy    schedule 19.11.2013
comment
Интересно, выполняет ли rb_to_int(vseed); некоторую нормализацию?   -  person randomguy    schedule 19.11.2013
comment
Да, есть одна последовательность, которая повторяется, семена просто поднимаются в другом месте. Однако состояния обычно не так близки друг к другу, как маленькие семена. Очень маловероятно, что вы увидите коллизию на практике — если вы просто запустите генератор, работающий от srand(1) против srand(1000), и получите миллиард результатов в секунду, мы все будем давно мертвы к тому времени, когда между последовательностями произойдет перекрытие. Доступное пространство огромно. Это другая проблема, чем знание того, где я нахожусь в последовательности, которая заключается в том, чтобы увидеть достаточно вариаций, чтобы идентифицировать состояние.   -  person Neil Slater    schedule 19.11.2013
comment
Нил Слейтер: А, это имеет смысл. Просто для понимания: с реализацией Ruby мы можем выбрать начальный диапазон до 19968 бит за счет уникальной длины последовательности?   -  person randomguy    schedule 19.11.2013
comment
Я думаю, это близко. Сам смотрю, но пока не могу генерировать повторяющиеся последовательности, которые продемонстрировали бы это с ответом на ваш вопрос.   -  person Neil Slater    schedule 19.11.2013
comment
Кажется, слишком много магии. Я мог бы просто использовать простую реализацию MT c/c++ и интерфейс с ней из Ruby, просто на всякий случай.   -  person randomguy    schedule 19.11.2013

Ответы (1)


arrow_upward
11
arrow_downward

Последовательность 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. Это довольно сложная функция — упакованное начальное значение не записывается в состояние буквально, а вместо этого состояние генерируется поэлементно, добавляя в предоставленные значения массива, используя различные операции xor, добавления и перекрестные ссылки на состояние. предыдущее значение (источник Ruby здесь также добавляет позицию индекса упакованного массива с комментарием «нелинейный», я думаю, что это одна из упомянутых модификаций стандартного MT)

Обратите внимание, что размер последовательности MT меньше, чем 2 ** ( 624 * 32 ) — значение repeat_every, которое я показываю здесь, пропускает 2 последовательности за раз, но легче всего найти повторяющееся начальное значение, потому что это легко чтобы увидеть, как он устанавливает точно такое же внутреннее состояние (поскольку первые 624 элемента в представлении массива начального числа идентичны, и это все, что используется позже). Другие начальные значения также будут создавать такое же внутреннее состояние, но связь представляет собой сложное сопоставление, которое связывает каждое целое число в 19938-битном пространстве с другим целым числом, которое создает такое же состояние для MT.

person Neil Slater    schedule 19.11.2013