Случайно длинный, может ли он быть дважды в строке с таким же числом

Мне было интересно с текущей реализацией java 1.7 класса Random, возможно ли, чтобы код ниже генерировал два раза один и тот же случайный длинный?

Я бы ответил на этот вопрос ложным, потому что я думаю, что случайный метод, используемый java, не повторяет одинаковые числа за период 2 ^ 48, поэтому он никогда не будет генерировать два одинаковых числа подряд. Правильно ли это?

Ответы

Ответ 1

Придумать "более длинный" ответ, чем предыдущий:

Вы уже связали реализацию, она выглядит так:

public long nextLong(){
    return ((long) next(32) << 32) + next(32);
}

Итак, очевидно, ОДИН случайное число вызывает 2 раза next(32). Это означает, что 2 случайных числа будут равны, если результаты next(32) в 4 раза ИМЕЕТСЯ ТАК ЖЕ, потому что остальная часть функции "жестко запрограммирована".

Глядя на функцию next(), мы можем видеть следующее:

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

Возвращаемая часть может быть просто проигнорирована, потому что снова: ТОЛЬКО семя будет вести к ИМЕЮЩЕМУ возврату - другое, чем ваш процессор разбит.

Итак, всего: нам нужно только сосредоточиться на линии

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);

если это приведет к ИМЯ семя, для четыре раза, были созданы 2 случайных числа, которые равны.

( Примечание: последовательности, такие как a, b, a, b, могут быть исключены для получения того же результата. Post достаточно длинный, я пропускаю эту часть.)

Во-первых, удалите часть << 48. Что это значит? Число, указанное (1), будет сдвинуто влево 48 раз. Таким образом, двоичный 0...01 превратится в 1000000000000000000000000000000000000000000000000 (48 нулей) то вычитается один, поэтому вы получите 0111111111111111111111111111111111111111111111111 (47 единиц)

Давайте посмотрим на первую часть этого уравнения:

(seed * 0x5DEECE66D[L] + 0xB[L])

Обратите внимание, что окончание [L] приведет к тому, что оно будет длинным, а не целым числом.

поэтому в двоичных словах это означает:

seed * 10111011110111011001110011001101101 + 1011

В конце концов, функция выглядит как

seed = (seed * 10111011110111011001110011001101101 + 1011) & (0111111111111111111111111111111111111111111111111)

(у меня остались первые нули при первых значениях)

Итак, что делает & (0111111111111111111111111111111111111111111111111)?

Побитово-оператор и в основном сравнивает КАЖДОЕ положение двух двоичных чисел. И только если оба из них "1", позиция в результирующем двоичном номере будет равна 1.

это сказано: КАЖДЫЙ бит уравнения (seed * 10111011110111011001110011001101101 + 1011) с позицией БОЛЬШЕ, чем 48 с ПРАВА будет проигнорирован.

49-й бит равен 2^49 или 562949953421312 decimal - это означает, что и (0111111111111111111111111111111111111111111111111) в основном просто говорит что результат MAXIMUM может быть 562949953421312 - 1. Итак, вместо результата 562949953421312 - он снова произведет 0, 562949953421313 будет генерировать 1 и так далее.

Все, что я написал выше, можно легко проверить:

В то время как следующий код создаст случайное seed * 11 *:

private Long seed = 0L;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

Можно перестроить семена, и ALSO получает семя 11 из не-0 семян, используя номер 562949953421312L.

private Long seed = 562949953421312L - 0xBL / 0x5DEECE66DL;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

Итак, вы видите: Семя 562949953421312 равно Семя 0.

Простое доказательство:

Random r = new Random(0L);
Random r2 = new Random(562949953421312L);

if (r.nextLong()==r2.nextLong()){
    System.out.println("Equal"); //You WILL get this!
}

это конечно, конечно:

Random r3 = new Random(1L);
Random r4 = new Random(562949953421313L);

if (r3.nextLong()==r4.nextLong()){
    System.out.println("Equal");
}

Почему это "магическое число" (562949953421312L) важно?

Предполагая, что мы начинаем с Seed 0.

Первое новое семя будет: 0 * 10111011110111011001110011001101101 + 1011 = 1011 (dec: 11)

Следующее семя будет: 1011 * 10111011110111011001110011001101101 + 1011 = 100000010010100001011011110011010111010 (dec: 277363943098)

Следующее семя (вызов 3) будет: 100000010010100001011011110011010111010 * 10111011110111011001110011001101101 + 1011 = 10000100101000000010101010100001010100010011100101100100111101 (dec 2389171320405252413)

Таким образом, максимальное число 562949953421312L превышено, что приведет к тому, что случайное число будет SMALLER, чем указанное выше значение.

Кроме того, добавление 1011 приведет к тому, что результат будет чередоваться между нечетными и четными числами. (Не уверен в реальном значении - добавление 1 могло бы сработать, imho)

Итак, генерация 2 семян (НЕ случайных чисел) гарантирует, что они НЕ равны, потому что выбрана конкретная точка переполнения - и добавление значения MAXIMUM (562949953421312L) НЕ ДОЛЖНО, чтобы достигнуть того же числа в течение 2 поколения.

И когда 2 раза одно и то же семя невозможно, 4 раза также невозможно, а это значит, что функция nextLong() никогда не сможет вернуть одно и то же значение для n и n + 1 поколений.

Я должен сказать, что я хотел доказать обратное. С статистической точки зрения, в 2 раза возможно одно и то же число - но, возможно, это почему-то называется Pseudorandomness:)

Ответ 2

Нет, получение двух одинаковых длин подряд в этом алгоритме невозможно.

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

long int seed = 0;

int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >> (48 - bits));
}
long int nextLong(){
    return ((long int) next(32) << 32) + next(32);
}

int main(int argc, char** argv) {
  long int step = atoi(argv[1]);
  long int i = step << 32;
  long int end = (step+1) << 32;
  while(i < end) {
    seed = i;
    if(nextLong() == nextLong()) {
      printf("Found seed %ld\n", i);
      return 0;
    }
    ++i;
  }
  printf("No seed in %ld\n", step);
  return 1;
}

затем

echo {0..65535} | xargs -n 1 -P 12 ./executable

Ответ 3

Это зависит от того, на какой вопрос вы спрашиваете.

Как говорили другие: Стандартные формулы для генераторов псевдослучайных чисел полностью исследуют свое пространство значений перед повторением.

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

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

Итак: Теоретически, если вы смотрите прямо на выход PRNG, ответ "вероятно, нет". Практически, ответ "не рассчитывайте на это в любом случае".

Ответ 4

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

Однако многие приложения ищут число в определенном диапазоне, что позволяет повторять, так как последующее число может иметь то же значение по модулю диапазона.

РЕДАКТИРОВАТЬ. Поскольку вы включили исходный код next, вы можете видеть, что если бы он возвращал тот же номер, он всегда возвращал бы тот же номер. Следовательно, вы застряли бы в одном из значений.