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

Subject: Re: [boost] Low discrepancy sequences (Boost.Random)
From: Justinas V. D. (jvd_at_[hidden])
Date: 2010-03-31 01:29:44

2010.03.31 01:22, Steven Watanabe rašė:
> AMDG
>
> * You don't need to #include <iostream> (I know the
> current Boost.Random headers do this, but istream and ostream
> are enough.)

I will change that.

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

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

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

>
>>> Would you be willing to write documentation for this as well?
>> I have written the concept part.
>
> * The link that says quasi-random number generator should not
> point to the Pseudo-Random number Generator section. (i.e.
> don't use the prng template)

Right.

> * 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?

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

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

J.