Почему 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-е из всех длинных значений может быть получено со случайным генератором
