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

Subject: Re: [boost] Low discrepancy sequences (Boost.Random)
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2010-03-31 12:41:36

AMDG

Justinas V. D. wrote:
>> * It might be clearer if you encoded the primitive polynomials in hex
>> instead of decimal.
>
> I don't know whether that would be more clear. Decimals show nice 
> prime property which would be obscured by hex.

Okay.

>> * Is there any hope that the algorithm would work with a 64 bit integer
>> type?
>
> No. Assume P and Q are polynomials. deg(P*Q) = deg(P) + deg(Q), 
> therefore maximum degree in 20th dimension for a polynomial product 
> would be (with signed 64 bit type) ((63 / 6) + 1) * 6 = 66. It is 
> frustrating, but it falls just outside the range of a 64 bit int type, 
> and would require a 66 bit int to encode.
>
> I could STATIC_ASSERT that.

Okay.  It isn't necessarily wrong to have limitations on
the allowed types, but these limitations need to be documented
and checked.

>> I noticed that you're using uint_fast64_t in places, and that makes me
>> wonder whether you're assuming a 32-bit integer type, even though it's
>> templated.
>
> Yes, you are right. The other question would be how would we check the 
> returned random numbers if all libraries support only 32 bit ints?

Very carefully.  The first library to implement anything can't
rely on testing against others...  I think you would just have
to generate lots and lots of random numbers and compare
the discrepancy to the expected discrepancy.  This test should
probably be written anyway.

>> * Is it necessarily correct for QuasiRandomNumberGenerator
>> to be a refinement of PseudoRandomNumberGenerator?
>> For example, the new standard requires several
>> specific seed overloads, which don't make sense for
>> a QuasiRandomNumberGenerator.
>
> Could you, please, provide a link to the exact PRGN interface that is 
> demanded by the C++ standard?

The current working draft of the standard is
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3090.pdf
Note that this is not official yet.

>> * I don't like having two ways to get the same information, i.e.
>> dim and dimension. This is probably a dumb question, but,
>> does the dimension of a quasi-random number generator need
>> to be provided? The number of dimensions of equidistribution
>> is also a property of PRNGs, but they don't explicitly provide it.
>
> Yes, it is immensely important. Specific things like a uniform point 
> generation on a sphere using a chord model would require a quasi 
> random number generator in 4th dimension. In general quasi-Monte Carlo 
> methods formulated to be bound by a [0,1]^s unit hypercube, and 
> dimensionality is an intrinsic part of the generator (and a problem 
> which we have to solve). To put it simply -- you just cannot plug-in 
> whichever s-dimensional generator you want.
>
> X::dimension and X::dim() are pretty much in the vein with 
> X::max_value and X::max().

I guess here's what makes me uncomfortable.
First of all, I don't really like having min_value and max_value either.
I think they seemed like a good idea at the time, but nothing
in the library uses them, and they just add extra complications,
because of the has_static_min dance.

Your description of dimension makes it sound as though
it isn't required.  If it isn't required, then unless there's a way
to detect its presence, it's completely useless in generic code
and should not be part of the concept.  If it is required, then
there's no reason to have dim as well.  If it's not required but
detectable, we have the same interface mess as for min_value/max_value.

>> * Can you define "low-discrepency sequence" when you use it?
>
> Uh... Don't people have to know the definitions before they use 
> something? :-)
>
> Something like this?
> Low discrepancy sequence is a sequence that necessarily has the 
> property that for all values of N, its subsequence x1, ..., xN has a 
> low discrepancy. Roughly speaking, this means that if we have 2D low 
> discrepancy sequence of points falling in a square, this square would 
> be covered uniformly, and the number of points falling to any part of 
> the square, would be proportional to the whole square, i.e., we do not 
> have such a situation when random points lump together or space out.
>
> (This is a very trivial wording that leaves out Lebesgue measures and 
> so on.)

I think it would be enough if you conveyed the intuitive idea that
a low discrepancy sequence is more evenly distributed than a
truly random sequence would be.

In Christ,
Steven Watanabe