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

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

    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\},\ $
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 30

      +2

      <del>

        +2
        Еще один повод использовать SecureRandom вместо обычного
          +7
          Зависит от цели. Для криптографии — конечно, но иногда нужно просто получить не слишком предсказуемое число, и желательно быстро, например, в компьютерных играх. В некоторых случаях даже предпочтительно использовать детерминированный источник псевдослучайных чисел — в тех же компьютерных играх при процедурной генерации мира, например.
            +4
            Детерминированный источник псевдослучайных чисел отлично получается из любого потокового шифра с заранее известным ключом. Возьмите ту же ChaCha20 и извлекайте себе сколько нужно псевдослучайных данных. Туда же можно прикрутить какое угодно распределение случайных величин, если нужен перекос в ту или иную сторону
          +13
          Почему-то с мобильного хрома 90% формул не распозналрсь и выглядит так:

          > inline$27^{10} \approx 2.06\cdot10^{14}$inline$

          Если поставить полную пк версию, то норм
            0
            Это формулы в формате MathJax, вернее, Tex. В частности ^ превращает выражение в {} в верхний индекс, \approx соответствует «примерному равенству», \cdot — символ умножения (точка). Почему-то не сработал скрипт MathJax.
              +1

              В мобильной лисе тоже.

                +1
                Давайте позовём сюда Exosphere
                  +1
                  Знаем-знаем, проблема в работе.
                +2

                Стало любопытно, что за рандом зарандомился у топикстартера, за неимением явы спортировал код на сишечку:


                #include <stdio.h>
                
                long seed; 
                void setSeed(long newseed) {
                    seed = (newseed ^ 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;
                }
                
                void main() {
                    setSeed(76880392499L<<11);
                    char alphabet[] = " abcdefghijklmnopqrstuvwxyz";
                    int len=sizeof(alphabet)-1;
                    int n;
                    while ((n = nextInt(len)) > 0)
                        printf("%c", alphabet[n]);
                    printf("\n");
                }

                Запуск (сохранить как r.c):


                make r && ./r
                  0
                  Так я же поставил ссылку на ideone.com/zlY6EI
                    0

                    Я прослепошарил её при первом прочтении. Да и всё равно есть привычка не полагаться на онлайн-сервисы :)

                    +3

                    long в C — это не тот же самый long в Java. Правильнее было бы использовать int64_t.
                    (int)(seed >> (48 - bits)) — неопределённое проведение в 32-битной программе или в программе, собранной в Visual Studio.

                      0

                      Да, вы правы.

                    –1

                    А есть ли у вас код, который генерирует seed для заранее определенной строки (или говорит, что это невозможно)?

                      +5
                      Как раз его созданию и оптимизации статья и посвящена. Если последуете моим советам, то и у вас он тоже будет :)
                        +2

                        Я имел в виду ссылку на репозиторий или хотя бы сниппет — в статье не нашел.

                          +1
                          В ideone.com/ROhmTA замените Long.MIN_VALUE на 0, Long.MAX_VALUE на 79536431L<<17, и строчку random.setSeed(seed); на кусок кода, показанный в конце статьи.
                      0
                      В огнелисе всё нормально с формулами.
                        0
                        Мобильный
                        файрфокс

                        +2

                        boomburum, тут кажется поехала разметка формул.

                          0
                          Уточню, что проблем две:
                          • В мобильной версии формулы не рендерятся вообще
                          • В десктопной версии в формулах исчезают минусы
                            +3
                            cc Meklon

                            Проблемка была в том, что в посте были картинки с latex.codecogs.com, которые почему-то не подтянулись в Хабрасторож, из-за чего что-то там с воркерами случилось — передал коллегам информацию для изучения ) Картинки перезалил вручную и вроде всё нормально стало.
                              0
                              В мобильной версии формулы появились, но почему-то с »> вместо >>>. Отчего так? В десктопной версии c >>> всё в порядке.
                          +1

                          Вот эта картинка
                          image
                          Заставила меня трижды протереть глаза, прежде чемя понял подставу.

                          +2
                          Исправьте, пожалуйста:
                          один шанс из двухста миллионов миллионов

                          Правильно — двухсот (двух нот)

                          Only users with full accounts can post comments. Log in, please.