Насколько хорошо java.util.Random?

Question

Два вопроса:

Получу ли я разные последовательности чисел для каждого семени, которое я в него положу?

Есть ли "мертвые" семена? (Единицы, которые производят нули или повторяются очень быстро.)

Кстати, а какие другие PRNG мне следует использовать?

Решение: Поскольку я собираюсь использовать PRNG для создания игры, мне не нужно, чтобы она была криптографически безопасной. Я еду с Мерсенн Твистер, как по скорости, так и по огромному периоду.

Answer 1

В некоторой степени генераторы случайных чисел - это лошади для курсов. Класс Random реализует LCG с разумно выбранными параметрами. Но он все еще имеет следующие особенности:

• довольно короткий период (2 ^ 48)
• биты не одинаково случайны (см. Мою статью о случайности битовых позиций )
• будет генерировать только небольшую часть комбинаций значений (знаменитая проблема " падения в плоскостях ")

Если эти вещи не имеют значения для вас, тогда Random имеет функцию выкупа, которая предоставляется как часть JDK. Это достаточно хорошо для таких вещей, как казуальные игры (но не для тех, в которые вовлечены деньги). Нет слабых семян как таковых.

Другая альтернатива, это генератор XORShift , который может быть реализован на Java следующим образом:

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

Для некоторых очень дешевых операций это имеет период 2 ^ 64-1 (ноль не разрешен) и достаточно прост, чтобы быть встроенным при повторном генерировании значений. Возможны различные значения сдвига: для получения более подробной информации см. Статью Джорджа Марсальи о генераторах XORShift. Вы можете считать биты в сгенерированных числах одинаково случайными. Одним из основных недостатков является то, что иногда он попадает в «колею», где в числе задается не так много битов, а затем для выхода из этой колеи требуется несколько поколений.

Другие возможности:

• объединяет разные генераторы (например, передает выходной сигнал генератора XORShift в LCG, затем добавляет результат к выходному сигналу генератора XORShift с различными параметрами): это, как правило, позволяет "сгладить" недостатки различных методов и может дать более длительный период, если периоды комбинированных генераторов тщательно выбраны
• добавить «лаг» (чтобы дать более длительный период): по существу, где генератор обычно преобразует последнее сгенерированное число, сохраняет «буфер истории» и преобразует, скажем, (n-1023) th.

Я бы сказал, что избегайте генераторов, которые используют глупое количество памяти, чтобы дать вам период, более длительный, чем вам действительно нужно (у некоторых период больше, чем число атомов во вселенной - вам это обычно не нужно) , И обратите внимание, что «длительный период» не обязательно означает «генератор высокого качества» (хотя 2 ^ 48 все еще немного низок!).

Answer 2

Как сказал zvrba, JavaDoc объясняет нормальную реализацию. Страница Википедии о генераторах псевдослучайных чисел содержит достаточное количество информации и упоминает Mersenne twister , который не считается криптографически безопасным, но очень быстрый и имеет различные реализации в Java . (Последняя ссылка имеет две реализации - я думаю, есть и другие.)

Если вам нужна криптографически безопасная генерация, прочитайте страницу Википедии - доступны различные варианты.

Answer 3

Что касается RNG, то реализация Sun определенно не самая современная , но она достаточно хороша для большинства целей. Если вам нужны случайные числа для целей криптографии, есть java.security.SecureRandom , если вы просто хотите что-то быстрее и лучше, чем java.util.random, легко найти в сети реализации Java Twister Mersenne .

Answer 4

Это описано в документации . Линейные конгруэнтные генераторы теоретически хорошо понятны, и много материалов о них доступно в литературе и в Интернете. Линейный конгруэнтный генератор с одинаковыми параметрами всегда выводит одну и ту же периодическую последовательность, и единственное, что решает начальное число, это то, где начинается последовательность. Итак, ответ на ваш первый вопрос - «да, если вы генерируете достаточно случайных чисел».

Answer 5

Смотрите ответ в моем блоге:

http://code -o-matic.blogspot.com / 2010/12 / как-долго-это-период-оф-хаотических numbers.html

Случайный имеет максимальный период для своего состояния (длинный, то есть 2 ^ 64 период). Это может быть непосредственно обобщено до 2 ^ k - вложите столько битов состояния, сколько хотите, и вы получите максимальный период. 2Мерсенна Твистер имеет очень короткую период , сравнительно (см. Комментарии в сообщении в блоге).

- К сожалению. Random ограничивается 48 битами, вместо того, чтобы использовать полные 64 бита long, поэтому, соответственно, его период равен 2 ^ 48, а не 2 ^ 64.

Answer 6

Если качество ГСЧ действительно имеет для вас значение, я бы рекомендовал использовать свой ГСЧ. Может быть, java.util.Random просто великолепен, в этой версии, в вашей операционной системе и т. Д. Возможно, так и есть. Но это может измениться. Это случилось до того, что в более поздней версии писатель библиотеки усугубил ситуацию.

Очень просто написать свой собственный, и тогда вы точно знаете, что происходит. Это не изменится при обновлении и т. Д. Вот генератор , который вы можете перенести на Java за 10 минут. И если вы начнете писать на каком-то новом языке через неделю, вы сможете снова его портировать.

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

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