Однажды во время одной тренировки мы с командой заметили что-то странное. Чуть позже напишу, что именно было. Дело в том, что после конкурса мы решили исследовать поведение c ++ rand () на наших машинах (мы используем Windows). Итак, мы использовали алгоритм Берлекампа – Масси по результатам rand (), взятым по модулю 2.

Результат шокирует — длина линейного повторения составляет всего 527! Нет, результаты не являются циклическими, просто повторение является коротким.

«Круто, но кого это волнует? Просто случайный факт, который я бы не заметил, и это не повлияло бы на меня». — неправильно!

Мы обнаружили это при решении задачи, которая требовала вычисления ранга двоичной матрицы. Мы хотели что-то проверить, поэтому мы просто сгенерировали большую матрицу с помощью rand (), что оказалось плохим решением. Поскольку только первые 527 столбцов были, скажем, независимыми, остальные определялись первыми 527 столбцами, поэтому ранг не превышал 527, и мы потеряли много времени, просто размышляя о том, что происходит.

Более того, если число столбцов четное, ранг составляет всего 496 (конечно, для матриц достаточно больших размеров). Угадайте, какова длина повторения, если мы посмотрим только на каждое второе значение rand ().

Да, вы правы — 496. Можно заметить, что 527 — 496 = 31, а 31 делит 527! Иллюминаты!

Вот несколько полезных ссылок: 1 2.

Если кто-нибудь может точно объяснить, что происходит для четного числа столбцов, это было бы здорово. Кроме того, если кто-нибудь знает, как rand () смотрит внутрь и может сказать несколько слов об этом, это также было бы здорово.