Subject: [boost] [random] [tr1] xor_combine min/max
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2011-02-10 12:36:38
Currently these are implemented as
std::min(_rng1.min(), _rng2.min()) and
This is obviously wrong, although it
happens to work for taus88 which is
the only use of xor_combine right now.
I looked at boost/tr1/random.hpp and
it has a more complex implementation.
Unfortunately, I don't think it's
completely right either as computes
min/max(x ^ y) where
(_rng1.min() << s1) <= x <= (_rng1.max() << s1) and
(_rng2.min() << s2) <= y <= (_rng2.max() << s2)
Alas, when a random value is shifted left,
the low order bits are always zero, so
this algorithm may overestimate the bounds.
Also, when the shift causes either
base engine to lose bits, the algorithm
forces the max to std::numeric_limits::max.
This is clearly wrong if _rng1.min/max =
[0x80000000, 0x800000FF], s1 = 1, since this
ends up being equivalent to [0, 0xFF].
So, I have a couple of options
a) Require the base ranges to be something
sane like [0, 2^k-1]. The advantage
of this is that it's easy, and it's
automatically guaranteed that the
combined engine is equidistributed
if the base engines are.
b) Somehow make it work. It would be
nice if it were fully general, but
working out the bit-twiddling for
this will be a pain and the code
will probably end up unintelligible.
I'd rather not do this unless it's
really needed. Are there any algorithms
that need to xor numbers from non
power-of-two ranges? For example,
is xoring the outputs of two LCG's
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk