Генератор неслучайных чисел

Этот код напечатает случайную последовательность латинских букв, так ведь?

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

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

Здесь $\$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\backslash equiv\_\{2^\{48\}\}((27\backslash cdot\; n+8)\backslash cdot2^\{17\}-11+h)\backslash 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»:

Хотелось бы упростить левую часть, поделив сумму почленно на $\$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\backslash in\backslash \{0,\backslash ldots,\backslash left\backslash lfloor\backslash frac\{2^\{31\}-1\}\{27\}\backslash right\backslash rfloor-1\backslash \},\backslash \; \$inline\$$