Генератор неслучайных чисел
Этот код напечатает случайную последовательность латинских букв, так ведь?
import java.util.Random;
class WTF {
public static void main(String[] args) {
Random r = new Random(76880392499L<<11);
String alphabet = " abcdefghijklmnopqrstuvwxyz";
int n;
while ((n = r.nextInt(alphabet.length())) > 0)
System.out.print(alphabet.charAt(n));
}
}
Можете проверить; вывод кажется совсем не случайным. Как же так вышло?
Прежде всего: какой шанс, что из всех последовательностей латинских букв напечатается именно эта? Сгенерировано 10 случайных чисел, каждое выбиралось из 27 вариантов, значит всего вариантов было $inline$27^{10} \approx 2.06\cdot10^{14}$inline$. Если считать, что все варианты равновероятны, то нам выпал один шанс из двухста миллионов миллионов! Ух!
Второй вопрос: сколько разных последовательностей способен генерировать java.util.Random? Документация объясняет, что хоть конструктор и принимает 64-битный параметр seed, но используются только младшие 48 бит; значит, разных состояний у генератора $inline$2^{48} \approx 2.81\cdot10^{14}$inline$. Оценим, при скольки значениях seed сгенерируется нужная нам последовательность: $inline$\frac{2^{48}}{27^{10}} \approx 1.37$inline$
Теперь уже не кажется поразительным, что существует как минимум одно подходящее значение seed. Тем не менее, остаётся вопрос: как найти такое значение среди почти трёхсот миллионов миллионов возможных?
Для начала можно попробовать искать полным перебором. SO-юзер TwoThe предложил переборщик, загружающий все ядра процессора; я исправил в нём ошибку (вместо перебора от Long.MIN_VALUE до Long.MAX_VALUE достаточно проверять значения от 0 до $inline$2^{48}-1$inline$), добавил индикацию прогресса, и запустил. На моём восьмиядерном i7 этот код проверял 60 млн значений в секунду, т.е. на проверку всех $inline$2^{48}$inline$ значений ушло бы 49 суток непрерывной работы. Это в пределах реального, но хотелось бы побыстрее. В разы.
К счастью, документация для java.util.Random приводит конкретные формулы, используемые методами setSeed, next и nextInt:
void setSeed(long seed) {
this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
}
int next(int bits) {
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
return (int)(seed >>> (48 - bits));
}
int nextInt(int n) {
int bits, val;
do {
bits = next(31);
val = bits % n;
} while (bits - val + (n-1) < 0);
return val;
}
Формулы далеко не самые прозрачные;, но попробуем разобраться, при каких условиях первой сгенерированной буквой станет нужная нам «h».
$$display$$\begin{eqnarray} nextInt (27)&=&8\\ next (31)&\equiv_{27}&8\\ seed_2\mathbin{\texttt{>>>}}(48 — 31)&\equiv_{27}&8\\ seed_2\mathbin{\texttt{>>>}}17&=&27\cdot n+8,\ n\in\{0,\ldots,\left\lfloor\frac{2^{31}-1}{27}\right\rfloor\}\\ seed_2&=&(27\cdot n+8)\cdot2^{17}+h,\ h\in\{0,\ldots,2^{17}-1\}\\ seed_1\cdot25214903917+11&\equiv_{2^{48}}&(27\cdot n+8)\cdot2^{17}+h\\ seed_1\cdot25214903917&\equiv_{2^{48}}&(27\cdot n+8)\cdot2^{17}-11+h \end{eqnarray}$$display$$
Здесь $inline$seed_2$inline$ — значение seed после выполнения next, а $inline$seed_1$inline$ — значение seed после выполнения setSeed. Видно, что 48-битное значение seed делится на 31-битную «видимую» часть, возвращаемую методом nextInt, и 17-битную «скрытую» часть, которая выше обозначена как $inline$h$inline$.
Далее домножим обе части сравнения на 246154705703781 — модульное обращение числа 25214903917:
$$display$$seed_1\equiv_{2^{48}}((27\cdot n+8)\cdot2^{17}-11+h)\cdot246154705703781 $$display$$
Приходим к выводу: если методу setSeed передать параметром значение (((((27*n + 8) << 17)|h) - 11) * 246154705703781L) ^ 0x5DEECE66DL, то nextInt(27) вернёт 8. Легко проверить, что так и происходит.
Это значит, что наш переборщик можно оптимизировать в 27 раз, если перебирать не все подряд значения seed, а — независимо — все значений $inline$n$inline$, и все $inline$2^{17}$inline$ значений $inline$h$inline$. Для этого я в переборщике от TwoThe заменил верхний предел для
seed на 79536431L<<17, а аргумент метода setSeed — на (((((27*(seed>>17) + 8) << 17)|(seed&0x1FFFFL)) - 11) * 246154705703781L) ^ 0x5DEECE66DL. Скорость перебора осталась на уровне 60 млн значений в секунду, но теперь для проверки всех возможных значений мне хватило бы 43 часов непрерывной работы.
Здесь стоит обратить внимание на цикл внутри метода nextInt. Чтобы понять, почему он нужен — представим, что у нас есть кость d12, и при помощи неё мы хотим получить случайное число от 0 до 4 путём взятия остатка от деления на 5. Очевидно, что пять возможных результатов не будут равновероятны, ведь 1 и 2 получаются каждый при трёх исходах броска (1, 6, 11 и 2, 7, 12), тогда как 0, 3 и 4 — только при двух каждый (5 и 10, 3 и 8, 4 и 9). Способ решения этого затруднения, выбранный разработчиками Java — если выпадет 11 или 12, то кость нужно бросить снова. Если и во втором броске выпадет 11 или 12, то нужно повторять броски до тех пор, пока не выпадет подходящее значение. В результате такого (неограниченно длительного) цикла бросков получится с равной вероятностью любое из значений от 1 до 10.
Применительно к нашему случаю это значит, что если первый вызов next вернёт значение от до $inline$2^{31}-1$inline$, то
nextInt вернёт не остаток от его деления на 27, а результат повторного броска — возможно, нужную нам восьмёрку! Это значит, что кроме диапазона нужно проверить ещё и варианты, когда
. К счастью, таких вариантов меньше полутора миллионов, и все они проверяются за долю секунды.
Но 43 часа перебора — это всё равно долго. Можно ли его ускорить ещё сильнее? Давайте посмотрим, при каких условиях второй сгенерированной буквой станет нужная нам «a»:
$$display$$\begin{eqnarray} nextInt (27)&=&1\\ next (31)&\equiv_{27}&1\\ seed_3\mathbin{\texttt{>>>}}17 &\equiv_{27}&1\\ ((seed_2\cdot25214903917+11)\mathbin{\%}{2^{48}})\mathbin{\texttt{>>>}}17&\equiv_{2^{27}}&1\\ ((((27\cdot n+8)\cdot2^{17}+h)\cdot25214903917+11)\mathbin{\%}{2^{48}})\mathbin{\texttt{>>>}}17&\equiv_{2^{27}}&1\\ ((27\cdot2^{17}\cdot25214903917\cdot n+25214903917\cdot h+\qquad\qquad\quad&\\+\;8\cdot2^{17}\cdot25214903917+11)\mathbin{\texttt{>>>}}17)\mathbin{\%}{2^{31}}&\equiv_{2^{27}}&1 \end{eqnarray}$$display$$
Хотелось бы упростить левую часть, поделив сумму почленно на $inline$2^{17}$inline$, но с некоторой вероятностью это приведёт к ошибке, если для каких-то значений $inline$n$inline$ и $inline$h$inline$ в сумме происходит перенос из 16-того бита в 17-тый. Так что оставим выражение как есть, и убедившись в его корректности на тысяче примеров, заменим в нашем переборщике безусловный вызов setSeed на условие:
long seed2 = ((8 + 27*(seed>>17)) << 17) | (seed&0x1FFFFL);
int seed3 = (int)((seed2 * 0x5DEECE66DL) >>> 17) & 0x7FFFFFFF;
if (seed3 % 27 == 1 || seed3 >= 0x7FFFFFF5) {
random.setSeed(((seed2 - 11) * 246154705703781L) ^ 0x5DEECE66DL);
...
}
(Случай seed3 >= 0x7FFFFFF5 соответствует перебросу во втором вызове nextInt.) После добавления этого условия скорость перебора возрастает до 150 млн вариантов в секунду, и перебор всех вариантов завершается меньше чем за день. Значений seed, соответствующих нужной последовательности букв, нашлось два разных.
P.S.: Как минимум в моём Chrome в формулах, отрендеренных хабром в SVG, в зависимости от масштаба экрана могут «проглатываться» минусы. Сравните: формула слева отрендерена хабром, справа — www.codecogs.com/latex/eqneditor.php:
$inline$n\in\{0,\ldots,\left\lfloor\frac{2^{31}-1}{27}\right\rfloor-1\},\ $inline$
