Как найти период генератора псевдослучайных чисел?

[mihaild]

B@R5uk в сообщении #1570975 писал(а):

Не очень надёжная схема. Если период кратен 2, то оба генератора будут синфазны, и совпадение просто не будет обнаружено.

Это стандартный алгоритм поиска цикла в связном списке. Совпадение гарантированно будет, потому что после входа в цикл на каждой итерации длина пути от быстрого до медленного итератора уменьшается на $1$.

[B@R5uk]

mihaild в сообщении #1570979 писал(а):

уменьшается на 1

О, точно, на разность же надо смотреть. Спасибо.

[Евгений Машеров]

TheRuinedMap в сообщении #1570734 писал(а):

Не обязательно. Генератор может разбивать диапазон на несколько циклов, каждый без апериодической части.

Возможно и так. Но в любом случае апериодическая часть, если есть, это выход на периодическую.

[Евгений Машеров]

B@R5uk в сообщении #1570975 писал(а):

Не очень надёжная схема. Если период кратен 2, то оба генератора будут синфазны, и совпадение просто не будет обнаружено.

Совершенно надёжная. Пример: "генератор" с периодом 4 вида $x_{i+1}=(x_i+1) \mod 4$
Запускаем с начальным значением 0
(номер испытания: выход первого генератора; выходы двух подряд запусков второго генератора)
1: 1; 1,2
2: 2; 3,0
3: 3; 1,2
4: 0; 3,0 - первое совпадение, запоминаем N=4
5: 1; 1,2
6: 2; 3,0
7: 3; 1,2
8: 0; 3,0 - второе совпадение, период равен 8-4=4

Синфазности тут в принципе быть не может, она сбивается на каждом шаге, поскольку второй запускается по два раза, и разность позиций в цикле всякий раз растёт на единицу. Апериодика пропускается, поскольку в апериодической последовательности не может быть тех значений, которые входят в цикл (естественно, это для генераторов вида $x_{i+1}=f(x_i)$ - линейных конгруэнтных, "середины квадрата" и другие, если генератор зависит от двух или более предыдущих, как генератор Фибоначчи, то проверка усложняется)
В случае распадения на несколько циклов находится один из них, способа отыскать все без перебора не знаю.

[traffic_lights]

traffic_lights в сообщении #1570713 писал(а):

Инструкция Rdrand (как для IA-32, так и для x86-64) для генерации случайного числа при помощи внутреннего генератора случайных чисел доступна в процессорах Intel, начиная с архитектуры Ivy Bridge, и в процессорах AMD — начиная с модели Ryzen.

Это я про то, что не надо изобретать велосипед, если его уже списали и заменили на мерс. Кроме того, может встать еще одна проблема: генерация больших массивов случайных чисел, особенно в параллельном режиме. Использовать много мегабайтные процессорные кэши в этом случае мало кому под силу и хотя диспетчер задач будет показывать стопроцентную загрузку всех используемых ядер, на самом деле кпд будет не более чем несколько процентов. В этом случае советую использовать пакет Statistical Functions из Intel® Math Kernel Library: очень грамотно реализованная шняга почти на все вкусы.

[Евгений Машеров]

Это несколько иная задача. Rdrand использует аппаратный источник энтропии. Что важно для криптографии, обеспечивая невоспроизводимость, но плохо для отладки программ (впрочем, были претензии и у криптографов). Выбирается две последовательности по 256 бит от аппаратного ГСЧ, которые действительно случайны, но статистические их качества не гарантированы, затем они подаются на вход шифратора AES, после чего полученная 256-битная последовательность, оставаясь случайной, имеет распределение, удовлетворяющее статистическим критериям. Затем она используется как начальная точка для ГПСЧ, выдающего 511 чисел, для дальнейшего вновь запрашивается аппаратный генератор (истинно) случайных чисел.

[traffic_lights]

Евгений Машеров в сообщении #1571428 писал(а):

Это несколько иная задача.

Задача у всех генераторов одна и та же. Остальное про RdRand - это спекуляции (где нет детерминированности, то это непреложный факт: вспоминается недавний мобель за опровержение существования скрытых параметров: а сколько копий было сломано, начиная с Эйнштейна).
Кроме того в задаче TC нужны большие выборки: я поэтому и дополнил свое сообщение, чтобы он долго не мучился: $x_{i+1}=(ax_i+b)\%M$ в Intel MKL тоже есть.

[Евгений Машеров]

Ну, на уровне философских воззрений, может, и одна. А на уровне практики появляются "досадные мелочи". Кстати, а откуда Вы взяли информацию, что "в задаче ТС нужны большие выборки"? Лично я не уверен даже, что это прикладная задача, а не учебная. И не научно-исследовательская "изучение характеристик генератора СЧ".