Генерация случайных чисел большой разрядности


imageОднажды я столкнулся с задачей генерации 128-битных случайных чисел для реализации генетического алгоритма. Из-за большой размерности задачи алгоритм гонялся долго, поэтому были повышенные требования к скорости работы. Я решил написать свой генератор специально для поставленной задачи.

В этом посте речь пойдет о применении линейного конгруэнтного метода для получения псевдослучайных чисел разрядности 64 и 128 бит с пояснением принципа работы и подбора параметров.

Если вам в тягость пользоваться ГСЧ из стандартной библиотеки, у вас к нему нестандартные требования или просто охота держать под контролем весь процесс генерации случайных чисел в своем приложении, добро пожаловать под кат.


Долой стандартный генератор!


Многим известно, что генерация случайных чисел является неотъемлемой частью многих алгоритмов. Кроме математики и статистики случайные числа используются в методах компьютерного моделирования, криптографии, машинного обучения (искусственные нейронные сети), стохастической оптимизации (эволюционные вычисления) и во многих задачах из других сфер, например, в более понятных вещах вроде рендера красивых картинок, работе движков и логики видеоигр.

Все достаточно распространенные языки программирования имеют функции для генерации случайных (или, если быть предельно точным, псевдослучайных) чисел. Однако иногда возникает необходимость реализовать свой собственный генератор случайных чисел (ГСЧ). Хотя ГСЧ «из коробки» обычно достаточно хорош для применения в большинстве случаев, но бывает и так, что слишком крутой генератор вроде бы и не нужен, но встроенный ГСЧ все равно не нравится.

Причины могут быть разные и неочевидные на первый взгляд. Во-первых, стоит отметить, что проблема генерации случайных чисел зачастую включает в себя поиск баланса между скоростью работы и качеством результата. Иногда нужно сделать чуть быстрее или чуть сложнее.

Во-вторых, ГСЧ – не просто каша из арифметических операций, а строго детерминированный алгоритм, характеристики которого могут сильно варьироваться. В некоторых научных экспериментах необходимо полностью описывать условия тестов для гарантии возможности их воспроизведения. Сюда относятся алгоритм и параметры ГСЧ. В этом случае лучше иметь свою реализацию.

Может возникнуть задача, в которой необходима одновременная работа разных ГСЧ. Именно разных, а встроенный генератор обычно один. Можно, конечно, запустить несколько копий с различным начальным зерном, однако в этом случае генераторы будут выдавать элементы одной и той же последовательности (которая циклически повторяется) просто начав из разных мест. Длина цикла огромна, но теоретически это может создать проблемы.

В моем случае нужно было генерировать 128-разрядные числа. В C++ нет функции, которая возвращала хотя бы 64-битные. После продолжительного гугления я обнаружил путаницу в rand() и RAND_MAX в разных компиляторах, набор костылей для генерации 64 бит, и решил отказаться от встроенного ГСЧ. Написание своего генератора показалось мне элементарной задачей – за пару итераций линейного конгруэнтного генератора получить два 64-разрядных числа, а затем склеить их. Это оказалось не так просто. Но обо всем по порядку.


За дело!


Итак, приступим к созданию ГСЧ. За основу возьмем простой и популярный линейный конгруэнтный метод, который работает по формуле:
где xi, xi+1 – текущее и следующее случайные числа; a, c и m – некоторые константы; mod – оператор нахождения остатка от деления.

Константу m часто берут равной 232 или 264 дабы избежать деления в программной реализации. Чтобы в результате получались 64-битные остатки, я использовал m=264. Но где же взять константы a и c? В Википедии была найдена следующая пара: a=6364136223846793005 и c=1442695040888963407. Недолго думая, я написал генератор, использующий эти параметры, и начал тестировать свой генетический алгоритм. Однако он быстро зацикливался. Подозрения пали на ГСЧ. Оказывается, несколько младших разрядов у полученной последовательности 64-битных «случайных» чисел демонстрировали отнюдь не случайное поведение. Значения некоторых двоичных разрядов подряд идущих чисел изображены в виде монохромных картинок:

               
     Значения младших 5-го, 15-го и 20-го разрядов (нумерация с нуля)

Примерно 20-24 младших двоичных разряда оказываются не пригодны для использования. С увеличением номера разряда повышается его случайность. Таким образом, чтобы получить одно 64-битное случайное число, необходимы две итерации линейного конгруэнтного генератора. Результат получается конкатенацией двух 32-битных фрагментов:


Например, в java.util.Random используется такой же принцип, хотя из-за того, что m=248, там отбрасываются только 16 младших разрядов при генерации int и long. Это, разумеется, отрицательно влияет на качество случайных чисел.

Вот пример последовательности 64-битных чисел, которая получается при a=6364136223846793005, c=1442695040888963407, m=264, x0=0 описанным на рисунке способом:

  1442695037175000593
  11166244415259155177
  7076646891078057782
  1459328390042580878
  8905969149530007863
  11682375496967736740
  897247724006084730

Насколько случайны эти числа? Примерно на уровне ГСЧ из стандартной библиотеки Java, возможно даже чуть лучше. Расчет каждого числа требует всего две операции умножения.

Если нужны несколько разных генераторов, следует выбрать другие значения констант a и c, рассчитанные на m=264. В статье по этой ссылке приведены примеры трех констант с «хорошими качествами»:
a = 2862933555777941757
c – нечетное, m=264
a = 3202034522624059733
a = 3935559000370003845


128-битные случайные числа


Нет ничего сложного в том, чтобы слепить два 64-разрядных числа в одно, тем не менее, здесь есть один интересный момент: одновременная генерация двух чисел по 64 разряда может быть на 25% быстрее, чем последовательная, при незначительном ущербе для их «случайности».

Идея состоит в том, чтобы обойтись тремя итерациями линейного конгруэнтного генератора вместо необходимых четырех. Этого можно добиться, если отбрасывать только 20 младших бит от результата на каждой итерации вместо 32-х как в предыдущем методе. Как можно видеть на монохромной картинке выше, 20-й разряд уже достаточно случаен, чтобы быть использованным. Оставшиеся разряды позволяют сформировать 128-битное число.



Если вдруг интересно как это выглядит в коде.
class RandomGenerator
{
public:
    RandomGenerator(unsigned long long int seed = 0);
    void next(unsigned long long int *hi, unsigned long long int * lo);

private:
    unsigned long long int currentSeed;
};

RandomGenerator::RandomGenerator(unsigned long long int seed) :
    currentSeed(seed)
{}

void RandomGenerator::next(unsigned long long int *hi, unsigned long long int *lo)
{
    const unsigned long long int a = 6364136223846793005;
    const unsigned long long int c = 1442695040888963407;
    const unsigned long long int x = a * this->currentSeed + c;
    const unsigned long long int y = a * x + c;
    const unsigned long long int z = a * y + c;

    *hi = (x & 0xfffffffffff00000) | (z >> 44);
    *lo = (y & 0xfffffffffff00000) | ((z >> 24) & 0xfffff);

    this->currentSeed = z;
}

Используя те же параметры a, c, m и x0, получаются такие числа:

  26613026195691280501944396807868523054
  136526799440480448897747671965175330512
  26919857327062567305005081067174740455
  151962490054994640693408155996993201355
  16551299175504952598134597160493279376
  67275013191410065527820230898073478166
  72445587156806476974393951227561270647

Этого способа добычи случайных чисел оказалось достаточно, чтобы мое приложение заработало. Получилось быстро и практично. Наверняка информация из статьи кому-нибудь окажется полезной. На этом все, спасибо за внимание. (Картинка с кубиками на обложке взята отсюда.)

Всем счастливых случайностей в новом году!

Комментарии 29

    +5
    Хи-квадрат считали полученного потока?
      0
      Нет, просто такая задача не стояла. К тому же, было бы проблематично его считать для столь больших чисел. Если перегонять в double, будет потеря значащих разрядов. Хотя я согласен, что это было бы интересно.
        –1
        Вот чую, через n месяцев, ТС забудет о том что его велосипед до конца не проверен,
        и подключит его к другому проекту с другими требованиями,
        и начнутся у всех проблемы,
        и помянут топик-стартера не добрым слов,
        и заодно всю программистскую братию,
        и долго код будет правится-дебажится,
        и долго еще будет слышен слог неприличный на просторах паутины,

        Занесло что-то меня — просто всегда был и буду против таких велосипедов.
        Тем паче, что ниже уже привели вполне хорошие велосипеды ГСЧ.
          +1
          А зачем самому мучится — возмите стандартный нист-овый тест для ГСЧ и вперед… Там же документация как и с чем его едят.
            0
            В в реализации NIST, выложенной на их сайте, есть ошибки. Кроме того, их реализация не оптимальна и медлительна. Спектральнный тест основан на эмпирической статистике, при увеличении длины выборки это приводит к ошибкам.
        +5
        1. Для проверки качества генераторов разработаны специальные наборы тестов. Самый известный — Diehard
        2. В C++11 уже встроены несколько генераторов случайных чисел и разных вспомогательных функций. То что у вас — это линейный конгруэнтный генератор. Там есть готовый 64-разрядный вихрь мерсенна. (так что ваша жалоба на отсутствие 64-разрядного устарела)
          0
          Линейный конгруэнтный же вроде как не проходит Diehard полностью. Хотя сравнить с «дефолтным» в ЯП было бы неплохо даже через Diehard. Алсо поддерживаю вас по поводу вихря мерсенна.
          +1
          Тоже как то понадобился свой генератор (но не в java, а в perl). Тоже взял LCG с параметрами 1103515245 и 12345 (выходные биты 30..0).

          Первые грабли на которые наступил — переполнение на 32 машине.

          Вторые — в какой-то задаче где случайные числа использовались для выбора порядка завершения задач в симуляции очереди заданий, в случае если количество параллельных процессов равно степени двойки, приоритезация в очереди заданий совершенно случайно начинала работать как round robin. Учитывая что я как раз писал тест, нужный чтобы убедиться что никакого round robin у меня нет (и в последствии тест должен начать проходить, когда я его реализую), был очень удивлён такой корреляции. Такие вот случайные числа.
            +4
            SecureRandom random = new SecureRandom();
            byte bytes[] = new byte[16];
            random.nextBytes(bytes);
            return new BigInteger(bytes)
              +2
              Тоже не понял сути статьи. Даже в случае чего, можно просто «слепить» несколько случайных чисел побитовым сдвигом.
                0
                Не самая хорошая идея, имхо. Возможно потеряем качество случайных чисел. Линейный конгруентный метод «знаменит» распределением чисел по гиперплоскостям:
                en.wikipedia.org/wiki/Linear_congruential_generator#Advantages_and_disadvantages_of_LCGs
                Что не лучшим образом сказывается в использовании его в 3д графики. А если мы скомбинируем так сдвигом — рискуем получить очень хреновое качество распределения.
              +7
              Очень хороший генератор случайных чисел Метод Фибоначчи с запаздываниями. Почему-то о нем мало что пишут, хотя он очень эффективный и имеет просто огромный период.
              +2
              Мне кажется прирост 25 процентов очень условный.
              • НЛО прилетело и опубликовало эту надпись здесь
                • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  при изучении генераторов в универе оказалось, что встроенный генератор в Java довольно неплох — проходит тесты на равновероятность, независимость и однородность
                  а на С++ для своей реализации сильный и быстроработающий генератор Гёффе / Джиффи
                    0
                    Каким образом получили монохромные картинки?
                      +1
                      Каждая картинка рисуется построчно, цвет каждого пикселя – это значение, к примеру, 5-го двоичного разряда в каждом числе xi, последовательность которых получается по формуле линейного конгруэнтного генератора. Нулевой разряд самый младший. Для картинки 256x256 пикселей нужно рассчитать 65536 чисел и взять из каждого по одному биту с заданной позиции.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        можешь свою длинную арифметику написать
                        мы генерировали 8М бит на питоне, и работало
                          0
                          • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          А почему Вы решили не пользоваться быстрыми криптостойкими хеш-функциями (в режиме счетчика)?
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Верно, скорость была важнее, а криптостойкость не требовалась.
                          • НЛО прилетело и опубликовало эту надпись здесь
                              –1
                              Из контекста, конечно, совершенно понятно, что речь в статье идет именно о псевдослучайных числах.
                              Но в заголовке топика и куче мест по тексту они фигурируют как «случайные», что некорректно (и теоретически может сбить кого-то с толку).

                              По поводу необходимости тестов и применения различных батарей (нист, дайхард, хи-квадрат) тут выше обсуждали…
                              Топик кастер же явно дал понять, что эти всевдослучайности ему нужны для узкоспециализированной задачи, никак не связанной с секурностью, ИБ, криптой и прочими вещами. Так что какие-то четкие требования по качеству последовательности предъявлять (а тем более — проверять) в данном случае бессмысленно.

                              Автору спасибо за топик, всегда приятно встретить на хабре что-то подобной тематики.

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

                              Самое читаемое