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 15:53:21

2010.03.31 19:41, Steven Watanabe rašė:
> AMDG
>

[skipped]

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

I have modified the lattice generation code to use std::bitset. Works 
just fine, so we don't have limitations on IntType anymore. So much 
more power to users. :-)

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

As of now, I have the test suite to check the generated values against 
the values produced by GSL. It checks THE WHOLE range, i.e., 2^31 - 1 
values for each dimension. It is probably an overkill, but we, 
mathematicians, are never happy with just 10001th value, simply 
because it might be a coincidence, a fluke, however unlikely it would 
be. But this "unlikely" would require very careful exploration just to 
answer the question what is the exact probability for two finite state 
automatons to have the same 10001th state (I hasten to add that this 
probability will NOT be equal to 0).

Speaking of other possible niederreiter_base2 typedefs, I don't really 
believe that we have to ensure that it produces proper quasi-random 
values in ALL cases simply because there is a myriad of ways to 
instantiate that template. Users have to know what they are doing and 
thus responsibility is all theirs.

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

Aha. So I have added the discard member function, deleted those 
constants (min_value, max_value, etc.). Seems like we are good to go, 
except for the missing member function template<class Sseq> void 
seed(Sseq& q) and the matching constructor.

My previous take that made you uneasy about the exposed internal data 
was something similar to this, but I don't think I will reimplement 
those until we have SeedSequence concept in Boost.Random. I can see 
the value of such members. They would allow easier experiments with 
seeding and would be left to experts only.

[skipped]

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

The constant is not required because dimensionality can always be 
detected by those templates that expect a dimensional random number 
number generator. Dimensionality itself is very important and is 
required. I can imagine algorithms that want to change the underlying 
result_type but would want a generator that has specific dimension.

Anyway, I removed X::dimension constant and spelled X::dim() as 
X::dimension().

[skipped]

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

I have updated concepts.qbk (diff is in Vault). What do you think?

J.