Почему Random.nextLong не генерирует все возможные длинные значения в Java?

Javadoc метода nextLong() класса Random указывает, что

Поскольку класс Random использует семя только с 48 бит, этот алгоритм не будет возвращать все возможные длинные значения. (Случайный javadoc)

Реализация:

return ((long)next(32) << 32) + next(32);

То, как я вижу это, заключается в следующем: чтобы создать любое возможное долгое время, мы должны сгенерировать любую возможную битовую схему из 64 бит с равной вероятностью. Предполагая, что вызовы next(int) дают нам 32 случайных бита, тогда объединение этих битов будет последовательностью из 64 случайных бит, и, следовательно, мы генерируем каждый 64-битный шаблон с равным правдоподобием. И поэтому все возможные длинные значения.

Я полагаю, что человек, который написал javadoc, знает лучше и что мои рассуждения как-то порочны. Может ли кто-нибудь объяснить, где мои рассуждения неверны и какие долготы будут возвращены?

Ответ 1

Так как Random является псевдослучайным, мы знаем, что с учетом того же семени он вернет те же значения. Принимая документы по их слову, есть 48 бит семени. Это означает, что не более 2 ^ 48 уникальных значений, которые можно распечатать. Если бы было больше, это означало бы, что некоторое значение, которое мы использовали ранее в позиции < 2 ^ 48 дает нам другое значение на этот раз, чем в прошлый раз.

Если мы попытаемся объединить два результата, что мы видим?

|a|b|c|d|e|f|...|(2^48)-1|

Выше приведены некоторые значения. Сколько пар есть? a-b, b-c, c-d,... (2 ^ 48) -1-a. Есть также 2 ^ 48 пар. Мы не можем заполнить все значения 2 ^ 64 только парами 2 ^ 48.

Ответ 2

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

Ответ 3

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

Предположим, что запись 48-битного генератора записывается в двоичном формате. Таким образом, мы получаем 2 ^ 48 * 48 бит. И теперь мы можем точно сказать, сколько 64-битных последовательностей мы можем получить, просмотрев список и отметив следующие 64 бита (завершая их при запуске, когда это необходимо). Это точно количество бит, которое у нас есть: 13510798882111488. Даже если предположить, что все эти 64-битные последовательности попарно различны (что совершенно не очевидно), нам предстоит пройти долгий путь до 2 ^ 64: 18446744073709551616.

Я снова пишу цифры:

18446744073709551616 pairwise different 64 bit sequences we need
   13510798882111488 64 bit sequences we can get with a 48 bit seed.

Это доказывает, что писатель джавадока был прав. Только 1/1844-е из всех длинных значений может быть получено со случайным генератором