Re: [boost] [random] new threefry random engine

Subject: Re: [boost] [random] new threefry random engine
From: Thijs van den Berg (thijs_at_[hidden])
Date: 2014-05-05 10:16:35

After experimenting with random function concepts I’m not pleased with the design options and concept. Instead I’ve decided to complete the threefry random engine I had nearly finished.  I’ve added a couple of extra features base on our discussions. There are a couple of reasons I prefer an random engine over a random function:

* I prefer -as a user of boost random- the random engine concept instead of a new random function interface. Sticking to a random engine interface makes my user code more generic, it will work with any random engine and I don’t need to learn a new concepts. 
* For me there is no benefit of using a random function over the random engine. There were a couple of arguments why a random function could under some circumstances be preferred. 
1) The cost of construction and seeding a random engine. 
2) memory usage, a random function can work on eternal containers and counters.

To address these points I’ve refined my threefry based random engine. I’ve allowed for a [1,2,3, or 4] x 64 bit counter and a [0,1,2,3,4] x 64 bit key. Reducing the size of of the key and counter speeds up the algorithm and lowers the memory usage. I’ve set the default to 1x64 bit counter and a 1x64 bit key. This gives a cycle length of 2^66 (7.3e19) and allows for 2^64 (1.8e19) different seeds and independent streams. For normal usage this is more than enough.  Of-course one can always set the template parameters to 4.
The default setting have low memory usage, higher speed, and  give the exact same result as the original engine if you stay within the counter cycle length (the first 7.4e19 draws) and key bounds. It’s faster than the previous threefry because some operations involving the key that are known to be zero can be dropped. In this case the cost of a seed() is neglect-able: it reduces to setting an int. 

I’ve also renames the random engine template to threefry4x64_engine to ensure that the name is compatible in case we refactor it into a the counter based engine and a random function, or if other developers add additional variants. Personally having this engine available in boost would already solve all my parallel needs. Usage will be like any other engine, i.e.

using namespace boost::random;
normal_distribution nd;
for(size_t i=0; i<atoms.size(); ++i) {
    float boltzmannfactor = sqrt(kT/atoms[i].mass);
    threefry4x64_13 eng(i);
    atoms[i].vx = boltzmannfactor*nd(eng);
    atoms[i].vy = boltzmannfactor*nd(eng);
    atoms[i].vz = boltzmannfactor*nd(eng);
}

Main compile-time options::
* generates 8,16,32 or 64 bit random numbers
* arbitrary number of encryption rounds >=1
* flexible counter size: counter can be 64,128, 192 or 256 bit.
* flexible key size: 0, 64, 128, 192 or 256 bits.

The engine has been fully tested and benchmarked and can be found here:
https://github.com/sitmo/threefry