Seed std :: mt19937 из std :: random_device

Многие люди закладывают свои двигатели Mersenne Twister следующим образом:

std::mt19937 rng(std::random_device{}());

Однако это обеспечивает только один unsigned int, т. е. 32 бита в большинстве систем, случайный размер семени, который кажется довольно крошечным по сравнению с пространством состояний 19937 бит, которое мы хотим семенировать. В самом деле, если я узнаю, что первый номер сгенерирован, моему компьютеру (Intel i7-4790K) требуется всего около 10 минут для поиска по всем 32-битным номерам и поиска использованного семени. (Я знаю, что MT не является криптографическим RNG, но я просто сделал это, чтобы понять, насколько маленький 32-разрядный действительно в эти дни.)

Я пытаюсь создать функцию для правильного семени mt19937 и придумал следующее:

#include <algorithm>
#include <iostream>
#include <random>

auto RandomlySeededMersenneTwister () {
    // Magic number 624: The number of unsigned ints the MT uses as state
    std::vector<unsigned int> random_data(624);
    std::random_device source;
    std::generate(begin(random_data), end(random_data), [&](){return source();});
    std::seed_seq seeds(begin(random_data), end(random_data));
    std::mt19937 seededEngine (seeds);
    return seededEngine;
}


int main() {
    auto rng = RandomlySeededMersenneTwister();
    for (int i = 0; i < 10; ++i)
        std::cout << rng() << "\n";    
}

Это выглядит как безопасное решение для меня; однако я узнал, что проблемы с RNG часто бывают весьма незначительными.

Предоставлено std::random_device создает хорошие, случайные данные в моей системе, дает ли код правильно загруженный std::mt19937?

29 голосов | спросил Baum mit Augen 30 +03002015-10-30T17:25:46+03:00312015bEurope/MoscowFri, 30 Oct 2015 17:25:46 +0300 2015, 17:25:46

3 ответа


26
  1. Хорошо, во-первых, почему вы используете std::vector для сравнительно небольшой последовательности известной длины? Необработанный массив или std::array хватает и избегает любого динамического выделения.

  2. Затем избегайте ненужных магических чисел. Используйте std::mt19937::state_size вместо того, чтобы вручную указывать 624.

  3. Почему вы используете лямбда? Простой std::ref(source).

Сеялка сама по себе выглядит отлично, и в вашем коде нет фактической ошибки .

template<class T = std::mt19937, std::size_t N = T::state_size>
auto ProperlySeededRandomEngine () -> typename std::enable_if<!!N, T>::type {
    typename T::result_type random_data[N];
    std::random_device source;
    std::generate(std::begin(random_data), std::end(random_data), std::ref(source));
    std::seed_seq seeds(std::begin(random_data), std::end(random_data));
    T seededEngine (seeds);
    return seededEngine;
}

Вы могли избегать необходимости random_data с помощью подсчета и преобразования итераторов, как описано в разделе « Последовательный итератор? Нет ли в boost? ".

Это не проще, но, возможно, более эффективно:

template<class T = std::mt19937, std::size_t N = T::state_size>
auto ProperlySeededRandomEngine () -> typename std::enable_if<!!N, T>::type {
    std::random_device source;
    auto make_iter = [&](size_t n) {
        return boost::make_transform_iterator(
            boost::counting_iterator<size_t>(n), [&](size_t){return source();});
    };
    std::seed_seq seeds(make_iter(0), make_iter(N));
    return T(seeds);
}

На coliru

ответил Deduplicator 30 +03002015-10-30T17:47:32+03:00312015bEurope/MoscowFri, 30 Oct 2015 17:47:32 +0300 2015, 17:47:32
10

Я могу предложить другую возможность правильной инициализации генератора случайных чисел mt19937:

auto RandomlySeededMersenneTwister () {
    std::mt19937 rng(std::random_device{}());
    rng.discard(700000);
    return rng;
}

В соответствии с этим документ (" генераторы периодов на основе линейных рекуррентностей по модулю 2 ", Ф. Паннетон, П. Л'Экуйер, М. Мацумото в AVM TOMS Volume 32 Issue 1, March 2006 Pages 1-16), особенно фигура 4 в главе 7, можно получить mersenne twister высокого качества, даже если его переменные инициализации имеют только несколько бит, установленных на ненулевое значение. Вы должны выполнить около 700000 генераций случайных чисел (или завихрений) во время /после фазы инициализации.

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

Кроме того, это решение значительно облегчает воспроизведение результатов, так как не требуется сохранять 624 номера, но только один.

Другим преимуществом является тот факт, что вы можете быть уверены, что получите хорошее равное распределение. Исходное решение не гарантирует этого свойства и полагается вместо этого на качество генератора случайных чисел источника и его взаимодействие с mt19937.

ответил Nils_M 2 12015vEurope/Moscow11bEurope/MoscowMon, 02 Nov 2015 13:24:37 +0300 2015, 13:24:37
8

Я написал более или менее точно такую ​​же функцию для собственного использования, поэтому, конечно, я думаю, что это довольно удивительно. ; -)

Две вещи, которые я буду делать по-другому (только стиль, а не безопасность):

  • Не скопируйте магическое число 624. std::mersenne_twister_engine template class имеет static constexpr member word_size code>, который вы можете использовать вместо этого. Аналогично, вместо unsigned, предпочитайте использовать result_type.

  • Рассмотрим возможность создания функции template, чтобы ее можно было использовать для std::mt19937_64 (и, возможно, других совместимых движков).

ответил 5gon12eder 30 +03002015-10-30T17:49:14+03:00312015bEurope/MoscowFri, 30 Oct 2015 17:49:14 +0300 2015, 17:49:14

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132