Ищете ясную и краткую веб-страницу, объясняющую, почему младшие биты случайных чисел обычно не настолько случайны

Question

Я создаю внутреннюю вики-страницу, которую должен знать каждый разработчик.

Я видел много обсуждений, касающихся rand() % N, но не было ни одной веб-страницы, которая бы все объясняла.

Например, мне любопытно, связана ли эта проблема только с C- и Linux, или же она относится и к Windows, C ++ ,. Java, .Net, Python, Perl.

Пожалуйста, помогите мне разобраться в этом. Кроме того, насколько неслучайно получают числа? Спасибо!

Answer 1

У меня нет веб-страницы, на которую можно было бы сослаться, но у меня могло бы быть объяснение "оборотной стороны", которое могло бы помочь. Работа простых генераторов случайных чисел заключается в выполнении шагов

1. Используйте последний сгенерированный номер n или начальный номер.
2. Умножьте это число на специальное большое число
3. Добавить еще одно специальное большое число
4. Разделите это на третье специальное большое число и отбросьте остаток
5. Вернуть результат

Теперь, если вы думаете о том, что происходит на всех этапах, кроме шага 4, вы выполняете операции, в которых только младшие биты могут изменять младшие биты результата. Добавление 1001 и 100 ... 00001 закончится в ... 02 (если вы говорите о базе 2, на самом деле эти цифры являются базой 12 для хихиканья.) Независимо от того, что находится в верхнем конце расчета. Точно так же, когда вы умножаете, оно будет заканчиваться на 1, несмотря ни на что.

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

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

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

Для вас вопрос, насколько они могут быть плохими, они могут быть действительно плохими. Самый простой способ увидеть это - сгруппировать отдельные числа в кортежи и построить их график. Так что, если у вас были случайные числа a, b, c, d, ... график (a,b), (c,d), ... и посмотрите на результаты. Это называется спектральным тестом, и Рэнд прекрасно его проваливает. У меня есть ссылка для попытки http://random.mat.sbg.ac.at/results/karl/spectraltest/

Answer 2

Проверьте http://en.wikipedia.org/wiki/Linear_congruential_generator,, который, вероятно, является алгоритмом, используемым для большинства встроенных генераторов случайных чисел.

Прокручивая вниз, ищите абзац, начинающийся с «Еще одна проблема LCG состоит в том, что биты младшего разряда сгенерированной последовательности имеют гораздо более короткий период ...» для некоторого понимания rand() % N.