Как генерировать целые числа в диапазоне из случайных битов

#php #random

#php #Случайный

Вопрос:

У меня есть источник случайных битов, которые я хотел бы преобразовать в целые числа различного размера, примерно соответствующие размеру популярных кубиков (1-4, 1-6 и т.д.)

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

Я бы предпочел ответ более сложный, чем простое заполнение функции PHP random() фрагментами моих случайных данных.

1. В вашем распоряжении имеется неопределенное количество случайных битов?

2. И почему использование ваших случайных данных в качестве начального значения неприемлемо?

3. Я бы рискнул предположить, что начинать с чего-то (даже в псевдокоде), а затем спрашивать, действительно ли это или нет, вероятно, было бы более эффективным подходом. 🙂

4. @Oli, по порядку: Да, у меня есть для большинства намерений и задач неограниченное количество случайности. Достаточно, чтобы длиться вечно. Во-вторых, потому что мне дали понять, что заполнение PHP RNG даст число, полученное путем смешивания моей высококачественной случайности с дрянной случайностью системного времени и других детерминированных факторов.

5. Если ваше начальное значение действительно случайное, то результирующая последовательность из RNG будет действительно случайной. (В принципе, если y = f(x) и x является случайным, то y также должно быть случайным.) Однако это не означает, что будущие значения нельзя предсказать на основе прошлых значений…

Ответ №1:

Если у вас есть произвольное количество доступных битов, вы можете выбрать метод отклонения, аналогичный Java Random.nextInt(int) . Псевдокод, взятый оттуда, является:

 public int nextInt(int n) {
     if (n<=0)
         new IllegalArgumentException("n must be positive");

     if ((n amp; -n) == n)  // i.e., n is a power of 2
         return (int)((n * (long)next(31)) >> 31);

     int bits, val;
     do {
         bits = next(31);
         val = bits % n;
     } while(bits - val   (n-1) < 0);
     return val;
 }

next() это функция, которая возвращает указанное количество случайных битов, объединенных в int . Вы могли бы заменить это своим источником случайных битов.

1. Хм, это потенциально может сработать. Я мог бы даже поместить отклоненные биты в конец «стека» случайности, чтобы сохранить, если потребуется.

2. Приму ваш ответ, если эксперимент подтвердит ваше предложение. 🙂

3. Хотя это, кажется, общий алгоритм, он не будет выдавать точно случайные числа. Ошибка увеличивается по мере приближения n к максимальному целому числу.

4. @soid: Что вы подразумеваете под «точно случайным», и почему вы считаете, что ошибка будет увеличиваться?

5. @soid: Вот почему отклонение выполняется в цикле while. Это обеспечивает равномерное распределение.