General Purpose Random Number Generation

Question

C ++ 11 introduced a significantly higher random number library for C rand() . In C, you often see the following code:

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

Since time(0) returns the current time in seconds, quick consecutive calls to the program will call the same sequence of numbers. A quick fix is ​​to provide seeds in nanoseconds:

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

Of course, this does not change the fact that rand() universally regarded as bad, and excellent alternatives are either not portable (e.g. Linux random() ), or rely on a third-party library (e.g. Boost).

In C ++ 11, the shortest program I know for creating good random numbers is:

 #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 not portable, and std::default_random_engine discouraged because it can choose a bad engine, for example std::rand . In fact, std::random_shuffle is deprecated and std::shuffle is preferred for this reason. Actually, I see what people say to use chrono to provide seed instead:

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

Not only is this hard to remember, but it looks even more ugly if we want to use nanoseconds instead:

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

• C approach seems desirable because it doesn't require as much boilerplate.

• random_device easiest because it does not require an ugly single-line, although it is not portable.

• mt19937 harder to remember than default_random_engine .

What is the best approach?

Answer 1

(1) know the available generators and choose the most suitable for work

(2) generate seed entropy, draw a standard measure (e.g. 256 bits), print it in a journal

(3) turn the standard seed block into seed_seq of size suitable for the generator in question and the genny seeds

Regarding (1): the generators in the standard library are a bit complicated to use, because they all have some features, and they all cannot run standard PRNG tests, such as TestU01 systematically. You must know their special flaws in order to judge their applicability. If this does not happen, take mt19937 or ranlux, fill them well and hope for the best. Using typedef - your own - allows you to switch and experiment with different gennies. typeid(rng_t).name() looks through the disguise and writes the actual name.

Regarding (2): you cannot transfer raw, lumpy entropy to the sowing procedures; if you do, then small differences in seeds will only lead to small differences in condition. Entropy should be cooked in a nice smooth mess, where each bit depends on a 50% probability for each bit of the original input. This includes inputs such as 1, 2, 3, ... By accepting a fixed standard amount of soup chisel, this is all controllable, such as printing onto a screen or magazine, to ensure repetition if necessary. It goes without saying that if you use seed numbers such as 1, 2, 42, ... instead of random seeds, then you can print them in a journal and not in a statement with soup. Using your own bit crusher means that you are not at the mercy of the semi-serial sowing functions, and even "scarce" seeds, such as 1, 2, 3, etc., give you completely different states (sequences) of the generator.

Regarding (3): some generators - for example, mt19937 - have a huge internal state, so you need to stretch the 256-bit (or other) standard seed quite a lot. Unfortunately, the standard library does not contain generators that are well suited for this task, and there are no adapters for turning the generator into seed_seq.

I would use xorshift * , KISS, mileage (numerical recipes) or 4x32 Tausworthe (aka lfsr113 ), but none of them are in the library. The library also lacks suitable mixing functions (bit grinders).

I posted the code for the murmur mixer - a simple and extremely efficient bit mixing function - in a similar topic ; I give the classic KISS and Tausworthe here, since I could not find suitable, clean links on the net.

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

Combined 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; } 

For use as primary generators, you will have to configure forbidden seeds (sticky states), but to stretch the seeds (create seed_seq) this can be safely ignored. There are many alternatives, such as using std :: vector and one of the simple generators (LCG) to make seed_seq worthy, but I prefer tried, tested and carefully analyzed solutions with maximum impact for the least amount of code.

The two 4x32 generators shown here can be stepped using the Chinese stop theorem, and vice versa, any state can be mapped to its unique point in the general sequence (shading over things like orbits at the moment). This makes them and other similar generators attractive as primary generators for general use when large guns such as xorshift1024 * (or mt19937) are not needed.

In any case, you will need very little code - for example. templates in the header file - to make standard <random> generators easy, convenient and safe to use. But it is 100% worth the effort. The generators are not too hot, but they are working; the rest of the infrastructure is quite decent, and this can significantly help solve your problems.

PS: some implementations (VC ++) allow you to pass any generator into seed () functions, which makes things trivially easy. Others - gcc - are not necessary, this means that you need to do the seed_seq thing if you want your code to be portable. If you want things to be very light, just pass the selected seeds through murmur_mix () before passing them to seed () and move on.

Pay for fear: after you fill your magic with a title, the actual application is easy.

 #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(); } 

This prints the generator, 42 and the actual seed in the log, except for the beaten bits and knocks them in mt19937. Code once, sit back, enjoy.