[boost] Low discrepancy sequences (Boost.Random)

Subject: [boost] Low discrepancy sequences (Boost.Random)
From: Justinas V. D. (jvd_at_[hidden])
Date: 2010-03-24 16:04:28

I have uploaded Niederreiter's base 2 (NB2) low discrepancy sequence 
generator (as described in Bratley, Fox, Niederreiter, ACM Trans. 
Model. Comp. Sim. 2, 195 (1992)) to Boost Vault. Low discrepancy 
sequences are particularly important for quasi random Monte Carlo 
integration approximations, because they enable algorithms to converge 
approx. the order of magnitude faster.

The implementation is tested against GSL (GNU Scientific Library), and 
generates identical uniform [0, 1) output for all dimensions up to 12 
(GSL does not support more dimensions). The implementation, however, 
supports up to 20 dimensions.

Some notes:
1) Initialization is pretty fast. To initialize NB2 state is a lot of 
work, and some of it is alleviated by (I hope) judicious use of 
metaprogramming. I did not measure really rigorously, but the 
impression is that initialization is about twice as fast.
2) I am not exactly a Boost.Random guru, so I probably missed some 
conceptual requirements, but it works just fine with uniform_01 
template (see dim2demo.cpp).

IMO Boost.Random (and a lot of other Boost libraries) is one of the 
best things after the sliced bread, but it sorely lacks some low 
discrepancy sequence generator, be it Niederreiter's, Sobel's or 
something else equally effective.

J.