Генерация случайных чисел общего назначения

Question

C++ 11 представил значительно превосходящую библиотеку случайных чисел для C's rand(). В C, вы часто видите следующий код:

srand(time(0)); 
rand() % MAX + MIN; 

Потому что time(0) возвращает текущее время в секундах, быстрые последовательные вызовы к программе будут производить ту же последовательность чисел. Быстрое решение это, чтобы обеспечить семя в наносекунд:

struct timeval time; 
gettimeofday(&time,NULL); 
srand((time.tv_sec * 1000) + (time.tv_usec/1000)); 

Конечно, это не меняет того факта, что rand() повсеместно рассматривается как плохие и превосходящих альтернатив либо непереносимой (например, в Linux random()) или полагайтесь на стороннюю библиотеку (например, Boost).

В C++ 11, самая короткая программа я знаю для получения хороших случайных чисел является:

#include <iostream> 
#include <random> 

int main() 
{ 
    std::random_device rd; 
    std::mt19937 mt(rd()); 
    std::uniform_int_distribution<int> dist(1, 10); 
    std::cout << dist(mt); 
} 

std::random_device не является портативным и std::default_random_engine не рекомендуется, поскольку он может выбрать плохой двигатель, например как std::rand. По этой причине std::random_shuffle устарел и std::shuffle является предпочтительным по этой причине. Вообще, я вижу, как люди говорят, чтобы использовать хроно, чтобы обеспечить семя, вместо:

std::chrono::high_resolution_clock::now().time_since_epoch().count() 

Это не только трудно запомнить, но выглядит даже уродливее, когда мы хотим использовать наносекунд вместо:

using namespace std::chrono; 
std::mt19937 mt(duration_cast<nanoseconds>(high_resolution_clock::now() 
             .time_since_epoch()).count()); 

• Подход C выглядит желательным, потому что он не требует большого количества шаблона .

• random_device является самым простым, потому что он не требует уродливого одного вкладыша, хотя он не переносится.

• mt19937 сложнее запомнить, чем default_random_engine.

Каков наилучший подход?

Answer 1

(1) знают, доступные генераторы и выбрать один наиболее подходящими для работы

(2) сварить семена энтропии, нарисовать стандартную меру (например, 256 бит), распечатать его в журнал

(3) превратить ваш стандартный блок семян в seed_seq с размером, соответствующим генератором в вопросе и засеять Genny

Относно (1): генераторы в стандартной библиотеке немного сложно использовать, потому что они все имеют некоторые особенности, и все они отказываются от стандартных тестов PRNG, таких как TestU01систематически. Вы должны знать их особые недостатки, чтобы судить о их применимости. Если этого не случится, возьмите mt19937 или ranlux, залейте их хорошо и надейтесь на лучшее. Используя typedef - ваш собственный - позволяет переключаться и экспериментировать с разными gennies. typeid(rng_t).name() просматривает маскировку и записывает фактическое имя.

Относительно (2): вы не можете передавать сырую, кусковую энтропию в процедуры посева; если вы это сделаете, то небольшие различия семян приведут только к небольшим различиям состояния. Энтропия должна быть приготовлена ​​в приятный гладкий месиво, где каждый бит зависит от 50% вероятности на каждый бит исходного ввода. Это включает в себя входы, такие как 1, 2, 3, ... Принимая фиксированную стандартную сумму суп-долота, все это управляемо, например, печать на экран или журнал, чтобы обеспечить повторность, если это необходимо. Само собой разумеется, если вы используете семенные числа, такие как 1, 2, 42, ... вместо случайных семян, то вы можете распечатать их в журнале, а не в выписке с супом. Использование вашей собственной дробилки означает, что вы не на милость полузаселенных функций посева, а даже «дефицитные» семена, такие как 1, 2, 3 и т. Д., Дают вам совершенно разные состояния (последовательности) генератора.

Относительно (3): некоторые генераторы, такие как mt19937, имеют огромное внутреннее состояние, поэтому вам нужно растянуть 256-битное (или другое) стандартное семя довольно много. К сожалению, стандартная библиотека не содержит генераторов, которые хорошо подходят для этой задачи, и нет адаптеров для превращения генератора в seed_seq.

Я бы использовал xorshift*, KISS, бегущие (числовые рецепты) или 4x32 Tausworthe (a.k.a. lfsr113), но ни один из них не находится в библиотеке. В библиотеке также нет подходящих функций смешивания (бит шлифовальные машины).

Я разместил код для шумоглушителя - простая и чрезвычайно эффективная функция смешивания бит - в a similar topic; Я даю классический KISS и Tausworthe здесь, так как я не мог найти подходящие чистые ссылки в сети.

struct KISS { uint32_t a, b, c, d; ... }; 

uint32_t KISS::cycle() 
{ 
    a = (a & 0xFFFF) * 36969 + (a >> 16);   // 16-bit MWC, a.k.a. znew() 
    b = (b & 0xFFFF) * 18000 + (b >> 16);   // 16-bit MWC, a.k.a. wnew() 
    c = c * 69069 + 1234567;      // 32-bit LCG, a.k.a. CONG()(
    d ^= d << 13; d ^= d >> 17; d ^= d << 5; // 32-bit XorShift a.k.a. SHR3(), corrected 

    return (((a << 16) | (b & 0xFFFF))^c) + d; // mixing function (combiner) 
} 

Комбинированный Tausworthe:

struct LFSR113 { uint32_t a, b, c, d; ... }; 

uint32_t LFSR113::cycle() 
{ 
    a = ((a^(a << 6)) >> 13)^((a & ~0x01) << 18); // 31 bits 
    b = ((b^(b << 2)) >> 27)^((b & ~0x07) << 2); // 29 bits 
    c = ((c^(c << 13)) >> 21)^((c & ~0x0F) << 7); // 28 bits 
    d = ((d^(d << 3)) >> 12)^((d & ~0x7F) << 13); // 25 bits 

    return a^b^c^d; 
} 

Для использования в качестве первичных генераторов вы должны настроить запрещенные семена (липкие состояния), но для семян растяжения (изготовление seed_seq), это может быть проигнорировано. Существует множество альтернатив, например, использование std :: vector и один из простых генераторов (LCG), чтобы сделать достойный seed_seq, но я предпочитаю проверенные, доверенные & тщательно проанализировал решения с максимальным ударом для наименьшего количества кода.

Два генератора 4x32, показанные здесь, могут быть ступенчато, используя теорему китайского останова, и, наоборот, любое состояние может быть отображено на его уникальную точку в общей последовательности (на данный момент, например, на орбитах). Это делает их и другие аналогичные генераторы привлекательными в качестве первичных генераторов для общего использования, когда не нужны большие пушки, такие как xorshift1024 * (или mt19937).

В любом случае вам понадобится совсем немного кода - например. шаблонов в файле заголовка - чтобы сделать стандартные генераторы <random> легкими, удобными и безопасными в использовании. Но это на 100% стоит усилий. Генераторы не слишком горячие, но они исправны; остальная инфраструктура вполне приличная, и это может значительно помочь решить ваши проблемы.

P.S .: некоторые реализации (VC++) позволяют передавать любой генератор в функции seed(), что делает вещи тривиально легкими. Другие - gcc - не надо, это означает, что вам нужно сделать вещь seed_seq, если вы хотите, чтобы ваш код был переносимым. Если вы хотите, чтобы вещи были очень легкими, просто передайте выбранные семена через murmur_mix(), прежде чем передавать их в seed() и двигаться дальше.

The wages of fear: После того, как вы наполнили свою магию заголовком, фактическое приложение легко.

#include "zrbj/rng_wrapper.hpp" 
#include <random> 
#include <typeinfo> 

int main() 
{ 
    zrbj::seeded<std::mt19937> rng(42); 

    std::cout << typeid(rng.wrapped_rng).name() << " -> " << rng(); 
}  

Это печатает генератор, то 42 и фактические семена к бревну, кроме разбив биты вдребезги и начинку их в mt19937. Код один раз, откиньтесь назад, наслаждайтесь.