22.12.2020 05:30
tyomitch 30 14300 Источник
Этот код напечатает случайную последовательность латинских букв, так ведь?

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 вариантов, значит всего вариантов было $27^{10} \approx 2.06\cdot10^{14}$. Если считать, что все варианты равновероятны, то нам выпал один шанс из двухсот миллионов миллионов! Ух!

Второй вопрос: сколько разных последовательностей способен генерировать java.util.Random? Документация объясняет, что хоть конструктор и принимает 64-битный параметр seed, но используются только младшие 48 бит; значит, разных состояний у генератора $2^{48} \approx 2.81\cdot10^{14}$. Оценим, при скольки значениях seed сгенерируется нужная нам последовательность: $\frac{2^{48}}{27^{10}} \approx 1.37$

Теперь уже не кажется поразительным, что существует как минимум одно подходящее значение seed. Тем не менее, остаётся вопрос: как найти такое значение среди почти трёхсот миллионов миллионов возможных?

Для начала можно попробовать искать полным перебором. SO-юзер TwoThe предложил переборщик, загружающий все ядра процессора; я исправил в нём ошибку (вместо перебора от Long.MIN_VALUE до Long.MAX_VALUE достаточно проверять значения от 0 до $2^{48}-1$), добавил индикацию прогресса, и запустил. На моём восьмиядерном i7 этот код проверял 60 млн значений в секунду, т.е. на проверку всех $2^{48}$ значений ушло бы 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».

$\begin{eqnarray} nextInt(27)&=&8\\ next(31)&\equiv_{27}&8\\ seed_2\mathbin{\textt{>>>}}(48 - 31)&\equiv_{27}&8\\ seed_2\mathbin{\textt{>>>}}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}$


Здесь $seed_2$ — значение seed после выполнения next, а $seed_1$ — значение seed после выполнения setSeed. Видно, что 48-битное значение seed делится на 31-битную «видимую» часть, возвращаемую методом nextInt, и 17-битную «скрытую» часть, которая выше обозначена как $h$.

Далее домножим обе части сравнения на 246154705703781 — модульное обращение числа 25214903917:

$seed_1\equiv_{2^{48}}((27\cdot n+8)\cdot2^{17}-11+h)\cdot246154705703781 $


Приходим к выводу: если методу setSeed передать параметром значение (((((27*n + 8) << 17)|h) - 11) * 246154705703781L) ^ 0x5DEECE66DL, то nextInt(27) вернёт 8. Легко проверить, что так и происходит.

Это значит, что наш переборщик можно оптимизировать в 27 раз, если перебирать не все подряд значения seed, а — независимо — все значений $n$, и все $2^{17}$ значений $h$. Для этого я в переборщике от 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 вернёт значение от до $2^{31}-1$, то nextInt вернёт не остаток от его деления на 27, а результат повторного броска — возможно, нужную нам восьмёрку! Это значит, что кроме диапазона нужно проверить ещё и варианты, когда . К счастью, таких вариантов меньше полутора миллионов, и все они проверяются за долю секунды.

Но 43 часа перебора — это всё равно долго. Можно ли его ускорить ещё сильнее? Давайте посмотрим, при каких условиях второй сгенерированной буквой станет нужная нам «a»:

$$display$$\begin{eqnarray} nextInt(27)&=&1\\ next(31)&\equiv_{27}&1\\ seed_3\mathbin{\textt{>>>}}17 &\equiv_{27}&1\\ ((seed_2\cdot25214903917+11)\mathbin{\%}{2^{48}})\mathbin{\textt{>>>}}17&\equiv_{2^{27}}&1\\ ((((27\cdot n+8)\cdot2^{17}+h)\cdot25214903917+11)\mathbin{\%}{2^{48}})\mathbin{\textt{>>>}}17&\equiv_{2^{27}}&1\\ ((27\cdot2^{17}\cdot25214903917\cdot n+25214903917\cdot h+\qquad\qquad\quad&\\+\;8\cdot2^{17}\cdot25214903917+11)\mathbin{\textt{>>>}}17)\mathbin{\%}{2^{31}}&\equiv_{2^{27}}&1 \end{eqnarray}$$display$$


Хотелось бы упростить левую часть, поделив сумму почленно на $2^{17}$, но с некоторой вероятностью это приведёт к ошибке, если для каких-то значений $n$ и $h$ в сумме происходит перенос из 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:
$n\in\{0,\ldots,\left\lfloor\frac{2^{31}-1}{27}\right\rfloor-1\},\ $