Эффективная Java-статья 47: Знание и использование ваших библиотек. Пример ошибочного случайного целочисленного метода

Question

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

Метод из книги:

private static final Random rnd = new Random(); 

//Common but deeply flawed 
static int random(int n) { 
    return Math.abs(rnd.nextInt()) % n; 
} 

• Он говорит, что если п малая мощность 2, последовательность случайных чисел, сгенерированных будет повторяться после короткого периода времени. Почему это так? В документации для Random.nextInt() сказано: Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. Так не должно быть, если n - небольшое целое число, тогда последовательность повторится, почему это относится только к степеням 2?
• Далее он говорит, что если n не является силой 2, некоторые числа будут возвращаться в среднем чаще, чем другие. Почему это происходит, если Random.nextInt() генерирует случайные целые числа, которые равномерно распределены? (Он предоставляет фрагмент кода, который наглядно демонстрирует это, но я не понимаю, почему это так, и как это связано с тем, что n является степенью 2).

Answer 1

Вопрос 1: если п является небольшой степенью 2, последовательность случайных чисел, которые генерируются будет повторяться после короткого периода времени.

Это не следствие чего-либо, что говорит Джош; скорее, это просто известное свойство linear congruential generators. Википедия сказать следующее:

Еще одна проблема LCGs в том, что биты более низкого порядка сгенерированной последовательности имеют гораздо более короткий период, чем последовательность в целом, если т установлен в степени 2. В общем случае n-я младшая значащая цифра в базовом b-представлении выходной последовательности, где b ^k = m для некоторого целого k, повторяется с не более чем периодом b ⁿ.

Это также отмечен в Javadoc:

линейных конгруэнтные псевдо-генераторы случайных чисел, такие как тот, реализуемый этот класс, как известны, имеют короткие периоды в последовательности значений их низко- биты заказа.

Другой вариант функции, Random.nextInt(int), работает вокруг этого, используя различные биты в этом случае (курсив мой):

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

Это хорошая причина, чтобы предпочесть Random.nextInt(int) по сравнению с использованием Random.nextInt() и делать свои собственные преобразования диапазона.

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

Есть 2 различных чисел, которые могут быть возвращены с помощью nextInt(). Если вы попытаетесь поместить их в n ведер, используя % n, а n не имеет значения 2, некоторые ведра будут иметь больше чисел, чем другие. Это означает, что некоторые результаты будут происходить чаще, чем другие, хотя исходное распределение было однородным.

Давайте рассмотрим это с помощью небольших цифр. Скажем nextInt() вернулся четыре равновероятных исходов, 0, 1, 2 и 3. Давайте посмотрим, что произойдет, если мы применили % 3 к ним:

0 maps to 0 
1 maps to 1 
2 maps to 2 
3 maps to 0 

Как вы можете видеть, алгоритм будет возвращать 0 в два раза чаще, чем это было бы возвращать каждый из 1 и 2.

Этого не происходит, когда n является степенью двух, так как одна степень из двух делится на другую. Рассмотрим n=2:

0 maps to 0 
1 maps to 1 
2 maps to 0 
3 maps to 1 

Здесь, 0 и 1 происходит с той же частотой.

Дополнительных ресурсы

Вот некоторые дополнительные - если только тангенциально отношение - ресурсы, связанные с LCGs:

• Спектральных тестов статистическими тестов, используемые для оценки качества LCGs. Подробнее here и here.
• A collection of classical pseudorandom number generators with linear structures имеет довольно красивые диаграммы рассеяния (генератор, используемый в Java, называется DRAND48).
• На crypto.SE есть интересный discussion о прогнозировании значений из генератора Java.

Answer 2

1) Когда n является степенью 2, rnd % n эквивалентен выбором несколько младших бит оригинала. Известно, что младшие биты чисел, генерируемые типом генераторов, используемых java, «менее случайны», чем более высокие бит. Это просто свойство формулы, используемой для генерации чисел.

2) Представьте себе, что наибольшее возможное значение, возвращаемое random(), равно 10 и n = 7. Теперь n % 7 отображает числа 7, 8, 9 и 10 в 0, 1, 2, 3 соответственно. Поэтому, если исходное число равномерно распределено, результат будет сильно смещен в сторону более низких чисел, поскольку они будут отображаться вдвое чаще, чем 4, 5 и 6. В этом случае это происходит независимо от того, является ли n мощностью два или нет, но если вместо 10 мы выбрали, скажем, 15 (что равно 2^4-1), то любое n, то есть сила двух, приведет к равномерному распределению, поскольку не будет «избытка» «числа, оставшиеся в конце диапазона, чтобы вызвать смещение, потому что общее количество возможных значений будет точно делиться на количество возможных остатков.