Re: [boost] Low discrepancy sequences (Boost.Random)

Subject: Re: [boost] Low discrepancy sequences (Boost.Random)
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2010-03-25 13:50:05

AMDG

Justinas V. D. wrote:
> 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.

For validation, Boost.Random uses the 10,000th value produced by a default
constructed generator.

> 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.

This is fine.  Generators should not generally be initialized very often.

> 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).

A few things that you could add
a) non-default seeding.
b) stream operators.

> 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.

Would you be willing to write documentation for this as well?

In Christ,
Steven Watanabe