Boost logo

Boost :

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šė:
> * 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)


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


Boost list run by bdawes at, gregod at, cpdaniel at, john at