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Å¡Ä:
> 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
>> 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
> 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.
> 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
> 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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk