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

Ответ 1

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

private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) - 1;

Множитель работает примерно до 2 ^ 34 и меняется, маска 2 ^ 48 - 1, а добавление довольно близко к 0 для этого анализа.

Когда вы создаете Random с семенем, конструктор вызывает setSeed:

synchronized public void setSeed(long seed) {
    seed = (seed ^ multiplier) & mask;
    this.seed.set(seed);
    haveNextNextGaussian = false;
}

Вы получаете семя довольно близко к нулю, поэтому исходное начальное значение, которое устанавливается, имеет значение multiplier, когда оба OR вместе. Во всех тестах с семенами, близкими к нулю, семена, которые используются внутри, составляют примерно 2 ^ 34; но легко видеть, что даже если вы предоставили очень большие количества семян, подобные семена, предоставленные пользователем, дадут похожие внутренние семена.

Последняя часть - это метод next(int), который на самом деле генерирует случайное целое число запрошенной длины на основе текущего семени, а затем обновляет семя:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

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

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

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

Ответ 2

Я бы не назвал это "проблемой".

А также, знаете ли вы, следует ли избегать этой проблемы только для первого значения (или первых нескольких значений), или если оно более общее и использование закрытых семян?

Корреляционные шаблоны между последовательными числами - общая проблема с некриптовыми PRNG, и это всего лишь одно проявление. Корреляция (строго автокорреляция) присуща математике, лежащей в основе алгоритма (ов). Если вы хотите это понять, вам, вероятно, следует начать с изучения соответствующей части книги Knuth Art of Computer Programming Chapter 3.

Если вам нужна непредсказуемость, вы должны использовать (истинное) случайное семя для Random... или позволить системе выбрать "довольно случайный" для вас; например используя конструктор no-args. Или еще лучше, используйте реальный источник случайных чисел или PRNG криптовариантного качества вместо Random.

Для записи:

• В javadoc (Java 7) не указывается, как сами семантики Random().
• Реализация Random() на Java 7 для Linux высевается из наносекундных часов, XORed с последовательностью "uniquifier". Последовательность "uniquifier" представляет собой LCG, который использует разный множитель и состояние которого статично. Это сделано для того, чтобы избежать автоматической корреляции семян...

Ответ 3

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

Поведение происходит из-за математической формы PRNG - Java использует линейный конгруэнтный генератор, поэтому вы просто видите результаты, запускающие семя через один раунд линейного конгруэнтного генератора. Этого недостаточно, чтобы полностью перепутать все битовые шаблоны, поэтому вы видите похожие результаты для похожих семян.

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

Ответ 4

Производя случайные семена (например, используя некоторые математические функции в System.currentTimeMillis() или System.nanoTime() для генерации семян), вы можете получить лучший случайный результат. Также можно посмотреть здесь для получения дополнительной информации