9

I have legacy C++ code that I wrote to generate uniform random numbers and a Gaussian distribution. It implements algorithms by Dr. George Marsaglia that are extremely fast. (I was using them to generate skazillions of samples for Monte Carlo high-dimensional integration.)

I think it would be a good idea to re-factor the generator and distribution to work with the new C++11 std::random scheme.

Can anyone point me to a tutorial or a good reference for std::random that includes the necessary info for how to extend it? Example code would be ideal.

UPDATE. Thanks for everyone's help. I have now written a drop-in replacement for the std::normal_distribution that ships with Visual C++ 2010. On my machine, the replacement is 26% faster when fed by the default engine. I am a little disappointed that the difference is not bigger, but hey, that's my problem. :-)

Jive Dadson
  • 16,680
  • 9
  • 52
  • 65
  • Something [like this](http://stackoverflow.com/a/8185813/596781) perhaps? Here's a [useful article](http://www.johndcook.com/cpp_TR1_random.html). – Kerrek SB Jul 30 '12 at 07:58
  • See [here](http://en.cppreference.com/w/cpp/numeric/random) for a reference. – Some programmer dude Jul 30 '12 at 08:00
  • @Kerrek SB: I need to write substitutes for mt19937 and uniform_int_distribution. I do not know what all is required. – Jive Dadson Jul 30 '12 at 08:01
  • @JiveDadson: Why would you want to substitute the engine? Anyway, see the references in the other links for other types of distributions; the normal distribution is included. – Kerrek SB Jul 30 '12 at 08:03
  • 2
    @Kerrek SB: As I said in the question, the reason I want to do it is that Dr. Marsaglia's algorithms are extraordinarily fast. – Jive Dadson Jul 30 '12 at 08:05
  • @JiveDadson: Then why do you want to use the C++11 generators? Also, make sure you understand the separation that C++11 uses: *Generators* produce streams of uniformly distributed integers, and *distributions* produce randomly distributed value sampled from a given distribution. Perhaps you only want to integrate one part of that with your code? – Kerrek SB Jul 30 '12 at 08:08
  • 2
    @Kerrek SB: I know what the generators and distributions do. I want to refactor one of each to be compatible with std::random. Never mind why. Thanks for your help. – Jive Dadson Jul 30 '12 at 08:12
  • @JiveDadson: OK, sure. There's a documented set of interface requirements for engines and distributions, which you might like to imitate, I suppose. – Kerrek SB Jul 30 '12 at 08:13
  • 2
    The requirements for random number engines are in the standard, in sections §26.5.1.3 and §26.5.1.4. The requirements for distributions are in §26.5.1.6. You can find a standard draft document here: https://github.com/cplusplus/draft/blob/master/papers/n3337.pdf – R. Martinho Fernandes Jul 30 '12 at 09:06

2 Answers2

5

N3376 is the latest draft C++ standard (this is post C++11, but is an excellent snapshot of C++11).

Everything C++11-random is in: 26.5 Random number generation [rand]

26.5.1.4 Random number engine requirements [rand.req.eng] has all of the requirements your uniform random number generator would need to fulfill.

26.5.1.6 Random number distribution requirements [rand.req.dist] has all of the requirements your Gaussian distribution would need to fulfill.

26.5.8.5.1 Class template normal_distribution [rand.dist.norm.normal] is the section describing the std-defined Gaussian distribution.

The C++11 <random> is very STL-like in that it sets up requirements for random number generators (containers), and random distributions (algorithms), and then the client can mix and match the two. It's a really very cool design.

Sorry, I don't know of a good tutorial. The C++ standard is an excellent reference and a lousy tutorial. However you are obviously well educated in the domain of random numbers. So assuming you know a thing or two about C++, the C++ standard may not be too bad.

Open source implementations of <random> are available if you want to peruse their source (for an example). One example is libc++. All they ask is that you retain their copyright notices if you reuse any of their code.

Edit

You are uniquely qualified to write this tutorial. :-)

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • I would like to be able to read the code for libc++. I will not use it, but it might be of value in figuring things out. I looked on the web page, and there appears to be no easy way to grab the include-files. (I am stranded in Windows Land.) – Jive Dadson Jul 31 '12 at 05:06
  • Duh. I found where to browse libc++. http://llvm.org/svn/llvm-project/libcxx/trunk/include/ – Jive Dadson Jul 31 '12 at 05:13
1

You can learn a lot by reading boost library sources, since many proposals in C++11 were adopted from boost.

Take a look at the interface of an example rng engine here:

http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine

I would start by implementing the min max seed and operator() functionalities to see if it passes as a valid engine for C++11

nurettin
  • 11,090
  • 5
  • 65
  • 85